[Haskell-cafe] Permutations

[Bertram Felgenhauer]

Daniel Fischer wrote:
> Needs an Ord constraint:
> 
> inserts :: [a] -> [a] -> [[a]]
> inserts [] ys = [ys]
> inserts xs [] = [xs]
> inserts xs@(x:xt) ys@(y:yt) = [x:zs | zs <- inserts xt ys] 
> 				++ [y:zs | zs <- inserts xs yt]

Heh, I came up with basically the same thing.

I'd call this function 'merges' - it returns all possibilities for
merging two given lists.

> uniquePermutations :: Ord a => [a] -> [[a]]
> uniquePermutations = foldr (concatMap . inserts) [[]] . group . sort

Which can also be written as

  uniquePermutations = foldM merges [] . group . sort

Bertram