On Sun, Nov 30, 2008 at 9:06 AM, Jake Mcarthur wrote:

-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1

On Nov 30, 2008, at 9:03 AM, Andrew Coppin wrote:

...

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

Seems a bit easy, I think.

Data.List.permutations . nub

That is not what he meant. Given: [1,1,2,2] The results should be: [1,1,2,2] [1,2,2,1] [2,2,1,1] [1,2,1,2] [2,1,2,1] [2,1,1,2] Assuming I didn't miss any... Luke

-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On Nov 30, 2008, at 10:17 AM, Luke Palmer wrote:

On Sun, Nov 30, 2008 at 9:06 AM, Jake Mcarthur wrote:

...

Seems a bit easy, I think.

Data.List.permutations . nub

That is not what he meant. Given:

[1,1,2,2]

The results should be:

[1,1,2,2] [1,2,2,1] [2,2,1,1] [1,2,1,2] [2,1,2,1] [2,1,1,2]

Heh, after a couple more seconds of thought, reversing the two composed functions fixes it: nub . permutations Of course, neither my previous nonsolution nor this solution are efficient for long lists, but I think it serves as a decent reference implementation at least. - - Jake -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.8 (Darwin) iEYEARECAAYFAkkyv2wACgkQye5hVyvIUKmjBwCfSYebuPUNSqENppJG9sVxy+wB ehYAoJjEY9M2o8ZqgN7R5pQ9x2PF54Ew =ipuT -----END PGP SIGNATURE-----

Jake Mcarthur wrote:

Seems a bit easy, I think.

Data.List.permutations . nub

Damnit, I specifically looked through Data.List to see if a permutation function exists... how did I miss that?! o_O (Hoogle didn't find it either.) Well either way, it's still entertaining to find ways to implementing it yourself. ;-)

Daniel Fischer wrote:

Am Sonntag, 30. November 2008 17:29 schrieb Andrew Coppin:

...

Jake Mcarthur wrote:

...

Seems a bit easy, I think.

Data.List.permutations . nub

Damnit, I specifically looked through Data.List to see if a permutation function exists... how did I miss that?! o_O

(Hoogle didn't find it either.)

Seems to be new, Data.List in 6.8.3 doesn't have it.

Ah, I see. That'll be why my copy of GHC 6.8.2 doesn't have it! :-D

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

Miguel Mitrofanov wrote:

eqPerms [] = [[]] eqPerms xs = [x:xt | x <- nub xs, xt <- eqPerms $ delete x xs]

Well, that's one way... ;-) I'm still not precisely sure why the first line must exist, but it seems no matter which way round you do it, that line is needed. Probably due to some subtlety of the list monad... I'm not sure how efficient using the delete function is, but this version definitely has the virtues of brevity and readbility.