random permutations

[George Russell]

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.