# [clean-list] help

Jerzy Karczmarczuk karczma@info.unicaen.fr
Fri, 02 Mar 2001 09:43:28 +0000

```> ZhangRuoyu wrote:
>
> I am a newer for Clean, and I am reading the tutorial (Functional
> Programming in CLEAN) now.
> Some Exercises in the books troubled me, here is one,
>
> Write a list comprehension for generating all permutations of some
> input list.

Since this is not a question for a Real Guru, I might perhaps
help. This is a typical non-deterministic problem, solved by
simulating of backtracking. First, define a function which inserts
an object *anywhere* in a list.

Then, a permutation is the result of inserting the n-th object into
a permutation of (n-1). Here is the entire code. I didn't test it,
because I am right now struggling with making Clean on my Sparc,
which should be trivial, but isn't, apparently because my system
does not appreciate filenames with spaces inside [I should put some
smileys here, but this is not so funny, after all...]

====
module permtest

import StdEnv

insrt x [] = [[x]]
insrt x (l=:[y:ls]) = [ [x:l] : [[y:r] \\ r<-insrt x ls] ]

permut [] = [[]]
permut [x:ls] = flatten [insrt x p \\ p <- permut ls]

Start = permut [1,2,3,4]    // or something else...

Jerzy Karczmarczuk
Caen, France

```