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

Thomas Hartman tphyahoo at gmail.com
Fri Mar 12 17:45:10 EST 2010


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 <rhapsodyv at 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 <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
>>
>
>
>
> --
> GNU/Linux user #446397 - http://counter.li.org
> _______________________________________________
> 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