in reply to Is this a fair shuffle?

I think i can address why this shuffle isnt fair. (sort of)

To simplify things, i am going to pretend that the built in sort uses a bubble sort (i honestly dont know what algorithm is used behind the scenes), but similar arguments can be applied to whatever sort() really uses.

So, recall that the 'largest' element will be bubbled to the last element in the array after 1 iteration, the second largest after the second iteration, and so on.

For this example, regardless of what happens prior to the final 2 elements being compared on the first iteration, when the final 2 elements are compared, there is a 50-50 chance that the final element will stay in place - provided rand() is fair.

If the final element is bubbled back, then on the second iteration it has a 50-50 chance of staying in the second last position. And after the 50-50 of staying in the final position, that makes a 25% chance of staying in the second last place. And so on and so on.

The chance of various other elements ending up in various places could be similarly calculated.

That said, recall that i assumed a bubble sort. I leave it as an exercise to the reader to perform similar analysis on other sort algorithms

(how cocky of me!)

Replies are listed 'Best First'.
Re^2: Is this a fair shuffle?
by Roy Johnson (Monsignor) on Apr 01, 2005 at 22:14 UTC
    It's certainly true that the sort algorithm used would affect the fairness. For bubblesort, it would seem that the random probability of a swap would need to be adjusted. Possibly (N-1)/N would be right, or possibly it would have to change with each pass.

    But Perl uses mergesort, which doesn't find an element's place and then never look at it again. Or you can select quicksort, which actually does take an element and stick it somewhere in the middle, after which it never moves again.

    Caution: Contents may have been coded under pressure.
[reply]

In Section Seekers of Perl Wisdom