[Haskell-cafe] Permutations

[Daniel Fischer]

Am Sonntag, 30. November 2008 16:03 schrieb Andrew Coppin:
> OK, so here's something just for fun:
>
> Given a list of items, find all possible *unique* permutations of that
> list. (E.g., the input list is explicitly _allowed_ to contain
> duplicates. The output list should not contain any duplicate permutations.)
>
> I've found one simple way to do this, but I'm sure there are multiple
> valid approaches. So let's see what people come up with. ;-)
>
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]

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

The (group . sort) part could be done with just an Eq constraint, but much 
less efficiently.