Re: [Haskell-cafe] How to do the permutation and combination thing?
Sorry, I did not make it clear, since I did not know how to say this in technical terms. With comprehension, I could get all the possibilities that draw one elem from each list and put them together. But consider this: for example, there are two types of pet, dog and cat. And there are two persons, him and her. So how many kinds of matches are there (orderless)? The answer is two: him with dog and her with cat, him with cat and her with dog. So f [a, b, c] [d, e, f] [g, h, i] = [ [ (a, d, g), (b, e, h), (c, f, i) ] , [ (a, d, g), (b, e, i), (c, f, h) ] , [ (a, d, h), (b, e, i), (c, f, g) ] , [ (a, d, h), (b, e, g), (c, f, i) ] , [ (a, d, i), (b, e, g), (c, f, h) ] , [ (a, d, i), (b, e, h), (c, f, g) ] ... ] On Mon, Mar 15, 2010 at 4:38 AM, Richard O'Keefe o...@cs.otago.ac.nz wrote: The first question is what does 'all the combinations' actually MEAN? We are told that f [a,b,c] [d,e,f] [g,h,i] = [[(a,d,g),(b,e,h),(c,f,i)], ...] in which the first element of the result is just zip3 [a,b,c] [d,e,f], [g,h,i]. But what are the other elements? Why is all the combinations a list of lists of tuples rather than a list of tuples? At first I thought you were after f xs ys zs = [(x,y,z) | x - xs, y - ys, z - zs] because that's what I would mean by all the combinations, but the example shows that's not so. When you can explain clearly what you mean by all the combinations, the code won't be far away. -- 竹密岂妨流水过 山高哪阻野云飞 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] How to do the permutation and combination thing?
I realized I fell into the trap of wrong way. Thank you. On Fri, Mar 12, 2010 at 4:16 PM, Ketil Malde ke...@malde.org wrote: Casey Hawthorne cas...@istar.ca writes: For example, I have this: list1 = [a, b, c] list2 = [d, e, f] list3 = [g, h, i] Think in abstract terms what you want to accomplish. A bit more specifically, let's say the input is a list of lists, and you want to produce all combinations of drawing one element from each of the input lists¹: perms :: [[a]] - [[a]] You need to consider two cases, when the input is empty, and when the input contains at least one list of elements: perms (l:ls) = ... perms [] = ... The second case shouldn't be so hard. Now, if you pretend that 'perms' is already implemented, then you can use it to generate all permutations for the tail of the input list. The first case boils down to combining the first input list with all permutations of the rest of the lists: perms (l:ls) = ... l ... perms ls Does this help? -k ¹ Using tuples is harder to generalize for length, but nicer typewise, since you'd get something like 'perms :: ([a],[b],..[x]) - [(a,b,..,x)] -- If I haven't seen further, it is by standing in the footprints of giants ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe -- 竹密岂妨流水过 山高哪阻野云飞 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] How to do the permutation and combination thing?
Am Montag 15 März 2010 08:37:20 schrieb Magicloud Magiclouds: Sorry, I did not make it clear, since I did not know how to say this in technical terms. With comprehension, I could get all the possibilities that draw one elem from each list and put them together. But consider this: for example, there are two types of pet, dog and cat. And there are two persons, him and her. So how many kinds of matches are there (orderless)? The answer is two: him with dog and her with cat, him with cat and her with dog. So f [a, b, c] [d, e, f] [g, h, i] = [ [ (a, d, g), (b, e, h), (c, f, i) ] , [ (a, d, g), (b, e, i), (c, f, h) ] , [ (a, d, h), (b, e, i), (c, f, g) ] , [ (a, d, h), (b, e, g), (c, f, i) ] , [ (a, d, i), (b, e, g), (c, f, h) ] , [ (a, d, i), (b, e, h), (c, f, g) ] ... ] In both, your verbal example and the pseudo-code example, all the groups have the same number of members (equal to the number of groups, which may or may not be coincidental). Is that a precondition, that all groups have the same number of members? If so, would the desired result for three groups of two members each be f3 [a,b] [c,d] [e,f] = [ [ (a,c,e), (b,d,f) ] , [ (a,c,f), (b,d,e) ] , [ (a,d,e), (b,c,f) ] , [ (a,d,f), (b,c,e) ] ] and for two groups of three members each f2 [a,b,c] [d,e,f] = [ [ (a,d), (b,e), (c,f) ] , [ (a,d), (b,f), (c,e) ] , [ (a,e), (b,d), (c,f) ] , [ (a,e), (b,f) , (c,d) ] , [ (a,f), (b,d), (c,e) ] , [ (a,f), (b,e), (c,d) ] ] ? In that case, look at Data.List.permutations and the zipN functions. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] How to do the permutation and combination thing?
Oh, that is not a precondition. So the answer of yours are correct. I am working on permutations. I used it in a wrong way. On Mon, Mar 15, 2010 at 4:39 PM, Daniel Fischer daniel.is.fisc...@web.de wrote: Am Montag 15 März 2010 08:37:20 schrieb Magicloud Magiclouds: Sorry, I did not make it clear, since I did not know how to say this in technical terms. With comprehension, I could get all the possibilities that draw one elem from each list and put them together. But consider this: for example, there are two types of pet, dog and cat. And there are two persons, him and her. So how many kinds of matches are there (orderless)? The answer is two: him with dog and her with cat, him with cat and her with dog. So f [a, b, c] [d, e, f] [g, h, i] = [ [ (a, d, g), (b, e, h), (c, f, i) ] , [ (a, d, g), (b, e, i), (c, f, h) ] , [ (a, d, h), (b, e, i), (c, f, g) ] , [ (a, d, h), (b, e, g), (c, f, i) ] , [ (a, d, i), (b, e, g), (c, f, h) ] , [ (a, d, i), (b, e, h), (c, f, g) ] ... ] In both, your verbal example and the pseudo-code example, all the groups have the same number of members (equal to the number of groups, which may or may not be coincidental). Is that a precondition, that all groups have the same number of members? If so, would the desired result for three groups of two members each be f3 [a,b] [c,d] [e,f] = [ [ (a,c,e), (b,d,f) ] , [ (a,c,f), (b,d,e) ] , [ (a,d,e), (b,c,f) ] , [ (a,d,f), (b,c,e) ] ] and for two groups of three members each f2 [a,b,c] [d,e,f] = [ [ (a,d), (b,e), (c,f) ] , [ (a,d), (b,f), (c,e) ] , [ (a,e), (b,d), (c,f) ] , [ (a,e), (b,f) , (c,d) ] , [ (a,f), (b,d), (c,e) ] , [ (a,f), (b,e), (c,d) ] ] ? In that case, look at Data.List.permutations and the zipN functions. -- 竹密岂妨流水过 山高哪阻野云飞 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] How to do the permutation and combination thing?
On Mar 15, 2010, at 8:37 PM, Magicloud Magiclouds wrote: Sorry, I did not make it clear, since I did not know how to say this in technical terms. Technical terms are not necessary, but absent those, clear examples are. With comprehension, I could get all the possibilities that draw one elem from each list and put them together. But consider this: for example, there are two types of pet, dog and cat. And there are two persons, him and her. So how many kinds of matches are there (orderless)? The answer is two: him with dog and her with cat, him with cat and her with dog. Why can't they _both_ have cats, or _both_ have dogs? I _think_ you mean that there is one man and one woman and not two _types_ of pets, but one dog and one cat. So if the man gets the dog, there is no dog left for the woman to get. Let me offer you a building block: select :: [t] - [(t,[t])] Given a list, select lazily returns a list of (item,rest) pairs, where item is an element of the original list, and rest is everything else in the original list, in the original order. select xs = choices xs [] where choices (x:xs) before = (x,reverse before++xs) : choices xs (x:before) choices [] _ = [] Example: select [1,2,3] = [(1,[2,3]),(2,[1,3]),(3,[1,2])] Now suppose you have any number of people and any number of pets and want to match up each person with a unique pet (but don't care if any pets are left over): matchings :: [a] - [b] - [[(a,b)]] matchings [] _ = [[]] matchings (h:hs) ps = [(h,p) : m | (p,ps') - select ps, m - matchings hs ps'] Example: matchings [him,her] [bug,cat,dog] = [ [(him,bug),(her,cat)], [(him,bug),(her,dog)], [(him,cat),(her,bug)], [(him,cat),(her,dog)], [(him,dog),(her,bug)], [(him,dog),(her,cat)] ] It should now be obvious how to extend this to more than two lists. It should also be obvious that this can be expensive. If there are N items in both xs and ys, then matchings xs ys has N! elements. More generally, if xs has M elements and ys has N elements and M = N, matchings xs ys has M-to-the-falling-N = M!/(M-N)! elements (if I've got this right). You want to consider whether there are other constraints on acceptable solutions that should be applied early to reduce the number of candidates. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] How to do the permutation and combination thing?
The first question is what does 'all the combinations' actually MEAN? We are told that f [a,b,c] [d,e,f] [g,h,i] = [[(a,d,g),(b,e,h),(c,f,i)], ...] in which the first element of the result is just zip3 [a,b,c] [d,e,f], [g,h,i]. But what are the other elements? Why is all the combinations a list of lists of tuples rather than a list of tuples? At first I thought you were after f xs ys zs = [(x,y,z) | x - xs, y - ys, z - zs] because that's what I would mean by all the combinations, but the example shows that's not so. When you can explain clearly what you mean by all the combinations, the code won't be far away. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] How to do the permutation and combination thing?
Casey Hawthorne cas...@istar.ca writes: For example, I have this: list1 = [a, b, c] list2 = [d, e, f] list3 = [g, h, i] Think in abstract terms what you want to accomplish. A bit more specifically, let's say the input is a list of lists, and you want to produce all combinations of drawing one element from each of the input lists¹: perms :: [[a]] - [[a]] You need to consider two cases, when the input is empty, and when the input contains at least one list of elements: perms (l:ls) = ... perms [] = ... The second case shouldn't be so hard. Now, if you pretend that 'perms' is already implemented, then you can use it to generate all permutations for the tail of the input list. The first case boils down to combining the first input list with all permutations of the rest of the lists: perms (l:ls) = ... l ... perms ls Does this help? -k ¹ Using tuples is harder to generalize for length, but nicer typewise, since you'd get something like 'perms :: ([a],[b],..[x]) - [(a,b,..,x)] -- If I haven't seen further, it is by standing in the footprints of giants ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] How to do the permutation and combination thing?
Hi, Give a try to this library: http://hackage.haskell.org/package/permutation You can construct the combinations with list of indices and then apply it to your sets. []s Victor On Fri, Mar 12, 2010 at 5:16 AM, Ketil Malde ke...@malde.org wrote: Casey Hawthorne cas...@istar.ca writes: For example, I have this: list1 = [a, b, c] list2 = [d, e, f] list3 = [g, h, i] Think in abstract terms what you want to accomplish. A bit more specifically, let's say the input is a list of lists, and you want to produce all combinations of drawing one element from each of the input lists¹: perms :: [[a]] - [[a]] You need to consider two cases, when the input is empty, and when the input contains at least one list of elements: perms (l:ls) = ... perms [] = ... The second case shouldn't be so hard. Now, if you pretend that 'perms' is already implemented, then you can use it to generate all permutations for the tail of the input list. The first case boils down to combining the first input list with all permutations of the rest of the lists: perms (l:ls) = ... l ... perms ls Does this help? -k ¹ Using tuples is harder to generalize for length, but nicer typewise, since you'd get something like 'perms :: ([a],[b],..[x]) - [(a,b,..,x)] -- If I haven't seen further, it is by standing in the footprints of giants ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe -- GNU/Linux user #446397 - http://counter.li.org ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] How to do the permutation and combination thing?
There is also polyomino.f2s: http://www.polyomino.f2s.com/david/haskell/combinatorics.html Iirc correctly there is some stuff here that is not on hackage but probably could/should be. 2010/3/12 Victor Mateus Oliveira rhapso...@gmail.com: Hi, Give a try to this library: http://hackage.haskell.org/package/permutation You can construct the combinations with list of indices and then apply it to your sets. []s Victor On Fri, Mar 12, 2010 at 5:16 AM, Ketil Malde ke...@malde.org wrote: Casey Hawthorne cas...@istar.ca writes: For example, I have this: list1 = [a, b, c] list2 = [d, e, f] list3 = [g, h, i] Think in abstract terms what you want to accomplish. A bit more specifically, let's say the input is a list of lists, and you want to produce all combinations of drawing one element from each of the input lists¹: perms :: [[a]] - [[a]] You need to consider two cases, when the input is empty, and when the input contains at least one list of elements: perms (l:ls) = ... perms [] = ... The second case shouldn't be so hard. Now, if you pretend that 'perms' is already implemented, then you can use it to generate all permutations for the tail of the input list. The first case boils down to combining the first input list with all permutations of the rest of the lists: perms (l:ls) = ... l ... perms ls Does this help? -k ¹ Using tuples is harder to generalize for length, but nicer typewise, since you'd get something like 'perms :: ([a],[b],..[x]) - [(a,b,..,x)] -- If I haven't seen further, it is by standing in the footprints of giants ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe -- GNU/Linux user #446397 - http://counter.li.org ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] How to do the permutation and combination thing?
Hi, For example, I have this: list1 = [a, b, c] list2 = [d, e, f] list3 = [g, h, i] Now I want: [ [(a, d, g), (b, e, h), (c, f, i)] , ... ] -- a list that contains all the combinations. How to do it pretty? Thanks. -- 竹密岂妨流水过 山高哪阻野云飞 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] How to do the permutation and combination thing?
This sounds like homework. Think in abstract terms what you want to accomplish. Start with the simplest case first, usually the base case. On Fri, 12 Mar 2010 14:02:02 +0800, you wrote: Hi, For example, I have this: list1 = [a, b, c] list2 = [d, e, f] list3 = [g, h, i] Now I want: [ [(a, d, g), (b, e, h), (c, f, i)] , ... ] -- a list that contains all the combinations. How to do it pretty? Thanks. -- Regards, Casey ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] How to do the permutation and combination thing?
All I could get is to use permutations and concatMap. But it looks really ugly. On Fri, Mar 12, 2010 at 2:09 PM, Casey Hawthorne cas...@istar.ca wrote: This sounds like homework. Think in abstract terms what you want to accomplish. Start with the simplest case first, usually the base case. On Fri, 12 Mar 2010 14:02:02 +0800, you wrote: Hi, For example, I have this: list1 = [a, b, c] list2 = [d, e, f] list3 = [g, h, i] Now I want: [ [(a, d, g), (b, e, h), (c, f, i)] , ... ] -- a list that contains all the combinations. How to do it pretty? Thanks. -- Regards, Casey ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe -- 竹密岂妨流水过 山高哪阻野云飞 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
