Shuffle generation
Rajeev Raman
raman at cs.rochester.edu
Fri May 17 01:54:02 AEST 1991
>In article <1bQCYz#6lHOhh7Jxk2b4WjLh65vrXpL=eric at snark.thyrsus.com>
>eric at snark.thyrsus.com (Eric S. Raymond) writes:
> In one of my programs, I have a requirement to generate random shuffles
> of arbitrary size. I am using the obvious method, as follows:
> [exchange a random pair of elements]
Persi Diaconis and Mehrdad Shahshahani (Z. Wahrscheinlichkeitstheorie
und verwandte Gebiete, 57:159-179, (1981)) show the following:
Let T_k(P) be the probability that permutation P is generated
after k such random transpositions.
Let D_k = \sum_{all permutations P} | T_k(P) - 1/n! |
Let k = cn + (n ln n)/2. Then
D_k <= b e^{-2c}, for some constant b.
A remark from their paper:
"The problem studied here arose from two independent sources. The first
source involved computer generation of a random permutation. [Knuth (1969)
pp 124--126 shows that the method mentioned on the net involving n-1
transpositions produces exactly a uniform distribution.] One of us had
a programmer who used the measure [T_k] to generate random permutations.
It is not hard to see that for n > 2, [T_k] is never exactly uniform.
A discussion arose about how large k should be to make [T_k]
exactly uniform."
Another remark (which they also make) to achieve a close to uniform
distribution, the algorithm should do the following: pick i and j
at random, and transpose regardless of whether i=j or not. (Ie, count
as a transposition even the identity transposition.) Otherwise, for
even k you get only even permutations, &c. This also can be used
to prove that after k transpositions (even k) the probability that
you get an even permutation is 1/2 (+/-) some finite quantity, for
n > 2. Thus the distribution is never exactly uniform.
Rajeev.
--
Rajeev Raman
ARPA: raman at cs.rochester.edu
UUCP: ...!rutgers!rochester!raman
More information about the Comp.lang.c
mailing list