Data.List permutations

[Daniel Fischer]

Am Dienstag 04 August 2009 19:48:25 schrieb Slavomir Kaslev:
> 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)

But you compare *interpreted* code here, that's not what counts.

Prelude Perms> length $ perm [1 .. 10]
3628800
(1.20 secs, 1259105892 bytes)
Prelude Perms> length $ permutations [1 .. 10]
3628800
(0.56 secs, 551532668 bytes)
Prelude Perms> length $ perm [1 .. 11]
39916800
(13.18 secs, 14651808004 bytes)
Prelude Perms> length $ permutations [1 .. 11]
39916800
(4.30 secs, 5953485728 bytes)

Apparently the library code is more amenable to the optimiser (note that the actual 
library is faster still:

Prelude Data.List> length $ permutations [1 .. 10]
3628800
(0.49 secs, 551532812 bytes)
Prelude Data.List> length $ permutations [1 .. 11]
39916800
(3.73 secs, 5953485816 bytes)

I have no idea why).

>
> 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.