Other Directory Sites: SeekWonder | Directory Owners Forum
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:15:22
Alex Alten (Alten@home.com)
Wed, 28 Oct 1998 22:10:08 -0800
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
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:15:22