Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

The ideal random permutation algorithm of Fisher and Yates (Algorithm P in Knuth vol.2) for a sequence of $n$ objects requires $n-1$ random numbers.

In some card games one first does a "cut" and then a ripple shuffle. The cutting point is a random value, the subsequent shuffling could be considered as deterministic. That is, only one random number is being used to generate the permutation, which understandably can't be ideal. On the other hand, theoretical perfection isn't always necessary in practice. I like hence to know whether, if one keeps the constraint of using one random number in a run, the quality of randomness of the permutation obtained couldn't eventually be improved through certain appropriate modifications of the procedure commonly employed in card games, if one is willing to take the trade-off of more work/time, inconvenience, etc. Such trade-offs may not be acceptable for real games, but I suppose there may be other practical applications that could advantageously exploit the same idea, thus without being required to acquire, e.g. via a chosen PRNG, the larger number of random numbers needed for executing the algorithm of Fisher and Yates.

share|improve this question
1  
    
@PålGD: Thanks for the link. But my concern is not with processing time etc. I like to (simply) use only one random number to determine the result of permutation of a given sequence in a cryptographical context such that both communication partners obtain the same result and that the permutation is nonetheless sufficiently highly random. –  Mok-Kong Shen Jan 27 '13 at 11:40
    
In that case you only need to share the seed. –  Karolis Juodelė Jan 27 '13 at 12:01
    
@KarolisJuodelė: Certainly what I mentioned is only a desideratum not a necessity. That random number may under circumstances already be present and it seems fine conceptually simply to use it as such and not to choose additionally a PRNG to obtain lots of PRNs to do the processing IMHO. –  Mok-Kong Shen Jan 27 '13 at 12:24
1  
@Mok-KongShen did you read the accepted answer? What do you need that's not there? –  Pål GD Jan 27 '13 at 13:47

2 Answers 2

Regardless of the algorithm you use, if you have $i$ bits of random data, you can generate a maximum of $2^i$ possible permutations. If $i$ is smaller than $log_2(n!)$, then there will be some permutations which cannot be produced, and you will have, in effect, decided which permutations those are when you encode your algorithm. (You may not be able to predict which permutations they are, but you have nonetheless determined that fact.) [1]

$log_2{52!}$ is about 225.6, so with a single 64-bit random number, you can only generate one out of every 4372488437452686306097090522819848184377442426979 permutations. With four 64-bit random numbers, you'd have no trouble generating all of them. $log_2{64!}$ is just under 296, so it would require five 64-bit numbers.

Since your permutation-generator is deterministic, you cannot invent more possibilities by manipulating the algorithm. The best you can do is to ensure that it is a homomorphism; that every random number is mapped onto a different permutation. Beyond that, you could investigate whether the one-in-4372488437452686306097090522819848184377442426979 sample of the universe of permutations exhibits any biases. For example, is each individual permutation position in the same evenly distributed? Is there a correlation between two (or more) positions? I sincerely doubt that trying to emulate a physical shuffle will improve these statistics more than the simple mathematical approach outlined below.

As xkcd reminds us, there is no such thing as an intrinsically random value. The only meaningful question we can answer is whether a sequence of pseudorandomly generated values is "random-like".

So let's first figure out how to transform the $i$ bits of randomness into $2^i$ distinct permutations. The following generic procedure should work:

  1. Predefine some function $f$ which maps $[0, 2^i)$ onto $[0, n!)$.

  2. For each permutation, given a random number $x$, compute ${q_0,...,q_{n-1}}$ and ${r_0,...,r_{n-1}}$ as follows:

    • $q_0 = f(x)$

    • $r_i = q_i \mod (n-i)$

    • $q_{i+1} = {{q_i - r_i}\over{n - i}}$

  3. Perform a Fisher-Yates shuffle using ${r_0,...,r_{n-1}}$ as the "random numbers".

(Aside from expanding the initial seed into the range $[0,n!)$, this is precisely the solution proposed by Yuval, just written out in more detail.)

Then you could start to measure the "randomness" of a proposed function $f$ by measuring the distribution of the values of each $r_i$ over the range of $f$. The next step might be to look at the distribution of $<r_i, r_j>$ for each pair $0 <= i < j < n$

One really simple definition of $f$ is:

$$f(x)=\lfloor x * {n!\over2^i} \rfloor$$

Assuming you calculate this with precise rational arithmetic, this gives a surprisingly reasonable set of individual $r_i$ distributions for a 52-shuffle given a 64-bit random number. [2] You'll have to decide whether that's good enough for you. If it turns out to not be, there are other possible transformations which might do better. Another simple one would be replacing the above with:

$$f(x)=\lfloor x * {n!\over2^i} \rfloor + p \mod n!$$

where $p$ is some large prime.


[1] This information-theoretic argument is based on the permutation-generation algorithm being stateless. If each random number is in some way combined with all previously generated random numbers without losing (too much) information, then the universe of possible permutations could be much larger. (This condition is not satisfied by simply combining the two random numbers with some arithmetic or bitwise operation whose value has the same number of bits as each of the arguments.) I think that's a reasonable assumption because the original question was cast in the context of a client-server architecture; in such systems maintaining co-ordinated state between the disconnect components is generally more complicated than exchanging a few more bits in each transaction.

[2] I didn't do much more than look at some histograms and a couple of correlations and a chi-square or two, but it was all really simple python, so I'm sure you could reproduce my limited research in a few minutes.

share|improve this answer
    
Thank you for the valuable informations. However, it's my fault that I had not properly formulated what I actually desire in my OP. Here is another formulation: The common card games are done manually without the help of PRNGs etc. Are there "practical" possibilities of somehow improving the quality of randomness of the permutations obtained, if one could accept the disadvantages of having to do much more work, being more inconvenient, very slow, etc. etc.? As to performance, i.e. a measure of randomness, I "guess" one probably could use some tests that are commonly used to test PRNGs. –  Mok-Kong Shen Jan 28 '13 at 7:58
    
[Addendum] Of course a number of repetitions of what is commonly done now in the games intuitively would surely improve the randomness. But I am wondering whether the current shuffling procedures themselves couldn't be somewhat modified (even if a bit awkward, inconvenient, etc. etc.) to gain improvements. –  Mok-Kong Shen Jan 28 '13 at 8:12
    
If you're interested in manually shuffling cards, seven good riffle shuffles are usually enough according to Van Zuylen, A.; Schalekamp, F. (2004) –  adrianN Jan 28 '13 at 9:56
    
@Mok-KongShen Please edit your question with the new information! "Nobody" reads the comments in order to make sense of your question. –  Raphael Jan 28 '13 at 10:25
    
@Mok-KongShen, I edited my answer to try to make it clearer that my analysis of the "randomness" of the permutations is purely information-theoretic, and that you cannot improve the information output of an deterministic homomorphic transform without increasing the information input. In other words, the algorithm itself does not invent entropy, so trying to model physical shuffling cannot compensate for a lack of input entropy. –  rici Jan 28 '13 at 16:09

If you can get a random number in the range $\{0,\ldots,n!-1\}$, you can generate a permutation on $n$ elements using the Fisher-Yates algorithm. The idea is to think of this number as encoding the numbers used in the Fisher-Yates algorithm, using "mixed-base" notation.

share|improve this answer
    
What I desire is an alternative to employing Fisher-Yates that does not require the generation of lots of PRNs (for a large sequence to be permuted) and that is nonetheless not too bad in the quality of the randomness of the permutation obtained. Sorry I may have misunderstood you. Wouldn't I need a very huge random number? –  Mok-Kong Shen Jan 27 '13 at 21:08
1  
If you want to generate a uniformly random permutation, you need $\log_2(n!)$ random bits. Even if you want something which is just close to random, you need roughly as much. It may be that for your purposes, you don't really need a random permutation. What do you want your random permutation for? –  Yuval Filmus Jan 27 '13 at 21:49
    
The question was actually meant to be general. But one tiny particular application that interests me involves a random permutation of 52 or 64 elements, where it happens to be rather easy to obtain a presumably fairly good PRN in [0,51] and [0,63] respectively. These elements form an alphabet for encryption purposes. –  Mok-Kong Shen Jan 27 '13 at 22:08
    
If you're using it for encryption, don't cut any corners! That will enable an attacker to read your traffic. Use the Fisher-Yates algorithm, which produces an almost-random permutation. –  Yuval Filmus Jan 27 '13 at 22:19
    
There is certainly the "No Free Lunch Principle". If one wants higher security, one has to pay a higher cost (including complexity of code etc.). In the case involved, one employs a combination of a few simple techniques and "believes" (surmises) that that would suffice for the intended applications (certainly not for encryption of messages that are at the top level of national security). –  Mok-Kong Shen Jan 27 '13 at 22:28

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.