Marcin 'Qrczak' Kowalczyk wrote:
Henning Thielemann <iakd0@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@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