Marcin 'Qrczak' Kowalczyk wrote:
>Henning Thielemann <[EMAIL PROTECTED]> 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 <[EMAIL PROTECTED]> 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
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
