[clean-list] Help with list comprehension

Marko van Eekelen marko@cs.kun.nl
Tue, 05 Jun 2001 15:09:18 +0200


Jerzy Karczmarczuk wrote:
>I believe you should understand some algorithm first.
>
>Here you have one, split into two stages.
>A. A function (insrt x l) which inserts "non-deterministically" an object
>    x into a list l. The non-determinism here means: find *all* solutions
>    of the insertion problem, insert in all possible places. Say, insrt x
>    into [a,b,c] should yield [[x,a,b,c],[a,x,b,c],[a,b,x,c],[a,b,c,x]].
>
>    insrt x [] = [[]]
>    insrt x l=:[y:yq] = [[x:l] : [[y:s] \\ s<-insrt x yq]]
>
>B. A permutation of N elements is the result of inserting one element
>    into a permutation of (N-1) remaining.
>
>    perm [] = [[]]
>    perm [x:xq] = flatten [insrt x l \\ l<-perm xq]
>
>You might try to rewrite this in a more clever way, but this is essentially
>the simplest algorithm I use.

Another way of putting it is (using removeMember from StdList):

permute :: [a] -> [[a]] | == a
permute []   = [[]]
permute list = [[e: permrest] \\ e <- list, permrest <- permute 
(removeMember e list)]

However, this is only valid if all elements are different and == is defined 
on them).

Marko van Eekelen.