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.