[Haskell-cafe] How to do the "permutation and combination" thing?

Magicloud Magiclouds magicloud.magiclouds at gmail.com
Mon Mar 15 04:00:10 EDT 2010


I realized I fell into the trap of wrong way. Thank you.

On Fri, Mar 12, 2010 at 4:16 PM, Ketil Malde <ketil at malde.org> wrote:
> Casey Hawthorne <caseyh at 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 at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>



-- 
竹密岂妨流水过
山高哪阻野云飞


More information about the Haskell-Cafe mailing list