[clean-list] Help with list comprehension

[Jerzy Karczmarczuk]

Frantisek Fuka:
 
> ... I'm stumped by exercise:
> 
> "Write a list comprehension for generating all permutations of some
> input list."
> 
> The list of length "len" has "len!" permutations so it seems to me that
> the comprehension (generating list of lists) should look like this:
> 
> [[...generate one permutation...] \\ i <- [1..len], j <- [1..len-1], k
> <-[1..len-2] ... z <- [1..2]
> 
> But I don't know how to create a comprehension with variable number of
> generators or how to create a recursion inside the comprehension...

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.

Jerzy Karczmarczuk
Caen, France