[Haskell-cafe] Linear shuffle

[Ben Rudiak-Gould]

Marcin 'Qrczak' Kowalczyk wrote:

 >Henning Thielemann <iakd0 at clusterf.urz.uni-halle.de> writes:
 >
 >>I did some shuffling based on mergesort [...]
 >
 >I think it doesn't guarantee equal probabilities of all permutations.

It doesn't (proof: it has a bounded runtime, which can't be true of a 
perfect shuffling algorithm based on coin flips). But it looks pretty 
good. I think that iterating this algorithm n times is equivalent to 
assigning a random n-bit number to each list element and sorting, which 
is equivalent to Chris Okasaki's approach with one iteration and an 
array of size 2^n.

Henning Thielemann <iakd0 at clusterf.urz.uni-halle.de> writes:

 >It even works for infinite lists.

In the sense that it doesn't diverge if you evaluate any finite prefix 
of the list, yes. In the sense that it does a good job of shuffling the 
list, no.

-- Ben