[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 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:
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/)