[Haskell-cafe] Progress on shootout entries

Bertram Felgenhauer bertram.felgenhauer at googlemail.com
Wed Jan 4 06:16:24 EST 2006

> And for sanity's sake, I wish one of the entries would have documentated
> a clear way to understand the permutation generator.   The PHP and Lua
> versions are almost legible.

Here's a neat Haskell version:

-- rotate initial n elements of the list left by one place
rotate n (x:xs) = rot' n xs where
    rot' 1 xs     = x:xs
    rot' n (x:xs) = x:rot' (n-1) xs

permutations l = foldr perm' [l] [2..length l] where
    perm' n l = l >>= take n . iterate (rotate n)

Combined with Jan-Willem Maessen's ideas (i.e. the single-pass flop)
this runs about 85 times faster than the current shootout entry.


More information about the Haskell-Cafe mailing list