Re: [Haskell-cafe] Linear shuffle

Marcin 'Qrczak' Kowalczyk wrote:

Henning Thielemann 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 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