Heinrich Apfelmus wrote:

Jon Fairbairn wrote:

...

Heinrich Apfelmus writes:

...

The answer is a resounding "yes" and the main idea is that shuffling a list is *essentially the same* as sorting a list; the minor difference being that the former chooses a permutation at random while the latter chooses a very particular permutation, namely the one that sorts the input.

For the full exposition, see

http://apfelmus.nfshost.com/random-permutations.html I haven't been following the thread, but my initial reaction would have been something like use System.Random.randoms to get a list rs and then do (roughly)

randomPerm = map snd . sortBy (compare `on` fst) . zip rs

How bad is that? I mean, how unfair does it get?

It's fair, but may duplicate elements, i.e. it doesn't necessarily create a permutation. For example, rs could be something like

rs = [5,3,3,3,2,4]

How about using random doubles? randomPerm xs = fmap (map snd . sort . flip zip xs) rs where rs = fmap (randoms . mkStdGen) randomIO :: IO [Double]

Paul Johnson writes:

See http://okmij.org/ftp/Haskell/perfect-shuffle.txt

I should have read that first time round! -- Jón Fairbairn Jon.Fairbairn@cl.cam.ac.uk http://www.chaos.org.uk/~jf/Stuff-I-dont-want.html (updated 2009-01-31)

Felipe Lessa wrote:

Heinrich Apfelmus wrote:

...

It's fair, but may duplicate elements, i.e. it doesn't necessarily create a permutation. For example, rs could be something like

rs = [5,3,3,3,2,4]

But our sort doesn't discard values when the keys are the same. For example,

[1,2,3,4] == map snd . sortBy (compare `on` fst) . zip (repeat 1) $ [1,2,3,4]

Nothing gets duplicated. Or did I miss something?

Oops, right, elements won't be duplicated by sortBy . I was thinking of randomPerm xs = zipWith (!!) xs rs But you do loose fairness. After all, you are mapping n^n possibilities for rs to n! permutations and because the latter does not divide the former, there is no way to make that balanced for general n . For instance, when the sorting algorithm is stable and you want to permute say "abcde", then 'a' is more likely to be in front of 'b' because of those cases where both 'a' and 'b' are zipped to the same number. Regards, apfelmus -- http://apfelmus.nfshost.com