Andreas wrote
Well, sorting is a special case of permuting, so my idea was to use the library routine
List.sortBy :: (a -> a -> Ordering) -> [a] -> [a]
passing it a comparison function which ignores its arguments and simply returns a random bit when invoked, e.g.
permute = sortBy $ \_ _ -> if random() then GT else LT
Unfortunately, this one-line hack is impossible since random numbers rely on state and sortBy is not prepared for use with a monad.
No this is an extremely bad way of doing it, since some permutations will come up more than others. (Consider what happens with a three-element list.) I think Ralf Hinze's method is the best presented so far. I would write it slightly differently though. In pseudo-code I would proceed as follows: (1) write the values to an array a[1]..a[n] (2) for i from n to 2 do j <- random integer between 1 and i swap a[i] and a[j] At the end the elements of a will be a random permutation. In Haskell you can of course use an STArray for this. Ralf Hinze's method requires you to do n multiplications and n divisions to compute the factorial and then compute a random number. I have to compute n random numbers rather than a single random number, on the other hand I don't have to do the multiplications and divisions. Indeed, since you need more random bits to compute a random big number than a random little number, I don't think in theory my method requires much more work from the random number generator than Ralf Hinze's.