A practical alternative of the method of random perumtation of Fisher & Yates

[Mok-Kong Shen]

For performing (pseudo-)random permutations the algorithm of Fisher &
Yates is theoretically perfect (i.e. disregarding the imperfectness of
the PRNG involved) but requires for dealing with a list of n elments
n-1 PRNs to generate one permutation. There are however cases in
practice where a couple of PRNs are available from the beginning due to
other reasons and thus it could be of some interest to see whether one
couldn't simply make use of such PRNs for random permutations as well
instead of specially acquiring the n-1 PRNs that are needed to do the
F&Y processing.

To avoid misunderstanding, it should be stated that the practical
situation we'll treat is one where n is moderately large (albeit not
too small) and that the number of random permutations to be generated,
while substantial, is nonetheless small in comparison to the
factorial of n, i.e. one doesn't need all, or almost all, of the
possible permutations of n elements.

Through experiments I found that the following function shuffle()
(written in Python), which requires only 2 PRNs in each invocation,
appears to be a viable candidate in the above mentioned context:

# in-shuffle
def riffle(cards,n):
newcards=[]
nh=n//2
for i in range(nh):
newcards.append(cards[nh+i])
newcards.append(cards[i])
if nh*2<n:
newcards.append(cards[n-1])
return(newcards)

# Shuffle n cards with 2 PRNs ur and us in [0,n-1].
def shuffle(cards,ur,us,n):
if us<ur:
t=ur
ur=us
us=t
newcards=cards[ur:n]+cards[0:ur] #1
newcards=riffle(newcards[us:n],n-us)+riffle(newcards[ur:us],us-ur)\
+riffle(newcards[0:ur],ur) #2
newcards=newcards[ur:n]+newcards[0:ur]
newcards=riffle(newcards[us:n],n-us)+riffle(newcards[ur:us],us-ur)\
+riffle(newcards[0:ur],ur) #2
newcards=newcards[ur:n]+newcards[0:ur] #1
return(newcards)

To explain the code in terms of a card deck: In the three statements
marked with #1 one does a "cut" at the position of ur. In the two
statements marked with #2 the 2 PRNs are used to separate the deck into
3 parts, which are individually subjected to a riffle shuffling and
then put in the reversed order, i.e. the 1st and 3rd part are exchanged.

For three chosen values of n, I took the list [0, 1, 2, ... n-1]
(hereafter termed the standard configuration) and applied shuffle() as
well as F&Y 10000000 times repeatedly. After each step the Hamming
distance (H-D) of the resulting permutation with respect to the
standard configuration is computed, with its frequency distribution
obtained in a typical run listed below, where the expected values
(rounded) and the computing times are also shown:

n=20 n=52 n=100

H-D shuffle() F&Y H-D shuffle() F&Y H-D shuffle()
F&Y Expected

0-9 0 0 0-41 0 0 0-89 0
0 0
10 1 2 42 0 2 90 3
2 1
11 10 12 43 7 12 91 13
9 10
12 96 100 44 93 90 92 97
100 91
13 743 714 45 720 742 93 760
753 730
14 5042 5144 46 5218 5108 94 4965
5099 5109
15 30792 30616 47 30775 30638 95 30999
30438 30657
16 153360 152709 48 153147 153195 96 152854
153881 153283
17 613189 611347 49 614813 613352 97 612850
612319 613132
18 1840137 1840471 50 1839321 1837951 98 1841054
1838083 1839397
19 3679788 3675790 51 3677310 3677840 99 3677166
3680107 3678794
20 3676842 3683095 52 3678596 3681070 100 3679239
3679209 3678794

Time 363.4 692.0 572.1 1800.4 888.5
3486.4


Further for a number of values of n I ran the two schemes 100000 times
and computed the number of those permutations generated that have
various numbers of duplicates as follows:

0 dupl. 1 dupl. 2 dupl. 3 dupl. 4 dupl. 5 dupl. 6
dupl. >6 dupl.

shuffle() 757779 104866 9872 678 30 2 0
0
F&Y n=10 759264 104475 9600 678 50 3 1
0

shuffle() 999303 349 0 0 0 0 0
0
F&Y n=15 1000001 0 0 0 0 0 0
0

shuffle() 999999 1 0 0 0 0 0
0
F&Y n=20 1000001 0 0 0 0 0 0
0

shuffle() 1000001 0 0 0 0 0 0
0
F&Y n=25 1000001 0 0 0 0 0 0
0

shuffle() 999979 11 0 0 0 0 0
0
F&Y n=30 1000001 0 0 0 0 0 0
0

shuffle() 1000001 0 0 0 0 0 0
0
F&Y n=40 1000001 0 0 0 0 0 0
0

shuffle() 1000001 0 0 0 0 0 0
0
F&Y n=50 1000001 0 0 0 0 0 0
0

shuffle() 1000001 0 0 0 0 0 0
0
F&Y n=60 1000001 0 0 0 0 0 0
0

Taking consideration also of the fact that the PRNGs used in practice
are not perfect, the function shuffle() thus seems to have fairly well
fulfilled its intended purpose. (The function has been used in a
software of mine in http://s13.zetaboards.com/Crypto/topic/6925232/1/)

M. K. Shen