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

[Ketil Malde]

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