[104811] in Cypherpunks
Re: Shuffling
daemon@ATHENA.MIT.EDU (Alex Alten)
Thu Oct 29 02:10:44 1998
Date: Wed, 28 Oct 1998 22:10:08 -0800
To: Jim Gillogly <jim@acm.org>, coderpunks@toad.com
From: Alex Alten <Alten@home.com>
In-Reply-To: <3637B331.39704F90@acm.org>
Reply-To: Alex Alten <Alten@home.com>
At 04:13 PM 10/28/98 -0800, Jim Gillogly wrote:
>Anonymous asks:
>> In the following snippet of pseudo-code, what should the value of
>> SWAP_TIMES be to make the array A[] random, assuming ...
>>
>> for(i=0;i<SWAP_TIMES;i++){
>> x=getrand();
>> y=getrand();
>> swap(A[x],A[y]);
>> }
>
>Indeterminate -- it could be a long time before you pick every number to
>swap with something. Instead use Knuth's "Algorithm P" from Seminumerical
>Algorithms (Vol. 2 of The Art of Computer Programming), which is linear
>in the length of the table and uses only one random number per swap.
>
The concept of swapping to get a random string of bits is very interesting.
From what I understand when one shuffles a deck of 52 cards 7 or more times
the card order becomes unpredictable e.g. random. The shuffle must be
what is called a "near perfect" shuffle. In other words the cards can't
strictly alternate from each hand (with a half deck each), but must be
slightly random, in the sense that sometimes 2 or 3 cards may drop from a
hand before a card drops from the other hand. An amateur shuffle, like
the one I perform, where the cards clump as they drop, may require 100's
of iterations before the order becomes totally unpredictable. BTW, if
I remember correctly the number of people in the world who can execute a
perfect shuffle at a professional rate (about 8 times a minute?)
consistently is somewhat less than 30.
- Alex
--
Alex Alten
Alten@Home.Com
Alten@TriStrata.Com
P.O. Box 11406
Pleasanton, CA 94588 USA
(925) 417-0159
