Is there such a beast as a "perfect" shuffle? :)

[Christos Georgiou]

On Fri, 10 May 2002 16:09:18 -0400, in comp.lang.python you wrote:

>Tim Peters <tim.one at comcast.net> wrote:
>> [Christos Georgiou]
>>> ...
>>> Apart from that, which is just a naive approach, any hints / clues for
>>> building good, uniform random numbers in the range 52! ?
>>
>> This is difficult.  Here's one way:
>>
>> http://www.faqts.com/knowledge_base/view.phtml/aid/4406/fid/546

This seems to be what I want, as long as it works.  Thanks, tim_one.

>The basic principle is to make sure that you run through them all and
>give opportunity for them to get swapped into any position.
>
>The unbiased way is not quite intuitive...
>
>- You run through from position 1 to position 52
>
>- For each position, select a random location from [present] to
>  the end of the list.
>
>- Swap what's in the current location with the contents of that other
>  random location.
>
>The nonintuitive part is that the random range shrinks as you move
>along.  If you leave the range open, there's a bit of a bias.  It's a
>significant bias, if there are only 3 cards.  It's not nearly so
>significant with 52.
>
>You could do far worse than running through the 52 locations and, for
>each one, swap it with a randomly selected location.  That will
>certainly shuffle things about pretty decently.

Christopher,

We all have reinvented the wheel at some point of our lives; most of us
have been school(boys|girls|whatevah) at times when net access was not
as common as it is now, and money was given to us as lunch-money, and
not Knuth-books-money :)).  The algorithm I always[1] used for shuffling
a sequence / array was the one you describe in your last paragraph, and
I am not that sure about the effectiveness of the 'non-intuitive'
modification, but I have not a reason to doubt you, apart from my
programmer's stubbornness :).
The only problem is that, *whatever* the algorithm to shuffle, if the
PRNG has a period of, say, 10**13, then there is no way to produce more
than 10**13 permutations at best.  That is why I was looking for a PRNG
with a period of more than 10**68.  Tim's reply shows that I didn't do
my homework very well (I didn't look in python.faqts !)

[1] for values of 'always' that are close to 18 years

and if I may add,

wishing-python-was-there-when-I-started-programming-ly y'rs,
-- 
TZOTZIOY, I speak England very best,
Real email address: 'dHpvdEBzaWwtdGVjLmdy\n'.decode('base64')