[Haskell-cafe] Linear shuffle
Benjamin.Rudiak-Gould at cl.cam.ac.uk
Sat Jan 15 11:38:41 EST 2005
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
More information about the Haskell-Cafe