Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.



A practical alternative of the method of random perumtation of Fisher & Yates
Posted:
Jun 22, 2013 8:08 AM


[I apologize for creating a new thread instead of putting the following stuffs into a recent thread initiated by me. This is done for avoiding confusions, since a modified computer code is to be dealt with here.]
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 n1 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 n1 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:
# inshuffle 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[n1]) return(newcards)
# Shuffle n cards with 2 PRNs ur and us in [0,n1]. 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],nus)+riffle(newcards[ur:us],usur)\ +riffle(newcards[0:ur],ur) #2 newcards=newcards[ur:n]+newcards[0:ur] newcards=riffle(newcards[us:n],nus)+riffle(newcards[ur:us],usur)\ +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, ... n1] (hereafter termed the standard configuration) and applied shuffle() as well as F&Y 10000000 times repeatedly. After each step the Hamming distance (HD) 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
HD shuffle() F&Y HD shuffle() F&Y HD shuffle() F&Y Expected
09 0 0 041 0 0 089 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



