A friend mine, new to functional programming, was entertaining himself by writing different combinatorial algorithms in Haskell. He asked me for some help so I sent him my quick and dirty solutions for generating variations and permutations:
inter x [] = [[x]] inter x yys@(y:ys) = [x:yys] ++ map (y:) (inter x ys)
perm [] = [[]] perm (x:xs) = concatMap (inter x) (perm xs)
vari 0 _ = [[]] vari _ [] = [] vari k (x:xs) = concatMap (inter x) (vari (k-1) xs) ++ vari k xs
After that I found out that nowadays there is a permutation function in the Data.List module:
permutations :: [a] -> [[a]] permutations xs0 = xs0 : perms xs0 [] where perms [] _ = [] perms (t:ts) is = foldr interleave (perms ts (t:is)) (permutations is) where interleave xs r = let (_,zs) = interleave' id xs r in zs interleave' _ [] r = (ts, r) interleave' f (y:ys) r = let (us,zs) = interleave' (f . (y:)) ys r in (y:us, f (t:y:us) : zs)
I was surprised to find that not only my version is much simpler from the one in Data.List but it also performs better. Here are some numbers from my rather old ghc 6.8.1 running ubuntu on my box: *Main> length $ permutations [1..10] 3628800 (10.80 secs, 2391647384 bytes) *Main> length $ perm [1..10] 3628800 (8.58 secs, 3156902672 bytes) I would like to suggest to change the current implementation in Data.List with the simpler one. Also, it would be nice to add variations and combinations in the Data.List module. Cheers. -- Slavomir Kaslev