2
$\begingroup$

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 riffle 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.

$\endgroup$
12
  • 1
    $\begingroup$ Random permutation with $O(1)$ random numbers at Stack Overflow. $\endgroup$
    – Pål GD
    Jan 27, 2013 at 11:09
  • $\begingroup$ @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. $\endgroup$ Jan 27, 2013 at 11:40
  • $\begingroup$ In that case you only need to share the seed. $\endgroup$ Jan 27, 2013 at 12:01
  • $\begingroup$ @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. $\endgroup$ Jan 27, 2013 at 12:24
  • 1
    $\begingroup$ @Mok-KongShen did you read the accepted answer? What do you need that's not there? $\endgroup$
    – Pål GD
    Jan 27, 2013 at 13:47

3 Answers 3

8
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$ Jan 28, 2013 at 7:58
  • $\begingroup$ [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. $\endgroup$ Jan 28, 2013 at 8:12
  • $\begingroup$ If you're interested in manually shuffling cards, seven good riffle shuffles are usually enough according to Van Zuylen, A.; Schalekamp, F. (2004) $\endgroup$
    – adrianN
    Jan 28, 2013 at 9:56
  • $\begingroup$ @Mok-KongShen Please edit your question with the new information! "Nobody" reads the comments in order to make sense of your question. $\endgroup$
    – Raphael
    Jan 28, 2013 at 10:25
  • $\begingroup$ @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. $\endgroup$
    – rici
    Jan 28, 2013 at 16:09
4
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ 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? $\endgroup$ Jan 27, 2013 at 21:08
  • 1
    $\begingroup$ 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? $\endgroup$ Jan 27, 2013 at 21:49
  • $\begingroup$ 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. $\endgroup$ Jan 27, 2013 at 22:08
  • 1
    $\begingroup$ 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. $\endgroup$ Jan 27, 2013 at 22:19
  • $\begingroup$ 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). $\endgroup$ Jan 27, 2013 at 22:28
2
$\begingroup$

There is a method by Ivan Stojmenovic, which uses only a single (pseudo-)random number in $[0,1]$ to uniformly (unbiasedly) generate any random permutation needed.

1.13 UNRANKING WITHOUT LARGE INTEGERS

Following the work by Stojmenovic 38, "ON RANDOM AND ADAPTIVE PARALLEL GENERATION OF COMBINATORIAL OBJECTS", this section describes functions mapping the interval [0...1) into the set of combinatorial objects of certain kind, for example, permutations, combinations, binary and t-ary trees, subsets, variations, combinations with repetitions, permutations of combinations, and compositions of integers. These mappings can be used for generating these objects at random, with equal probability of each object to be chosen. The novelty of the technique is that it avoids the use of very large integers and applies the random number generator only once. The advantage of the method is that it can be applied for both random object generation and dividing all objects into desirable sized groups.

The method works similarly to picking a random index from $[0,n!-1]$ and unranking the corresponding permutation (or other combinatorial object of interest), but with a twist. With appropriate manipulation of combinatorial relations one can use simply a random number (essentialy a probability that a specific permutation has been selected, uniformly) and do all computations using float-point arithmetic without ever using big integer arithmetic. This also leads to using one single random number, so it leads to a kind of fisher-yates-knuth shuffle algorithm with minimum number of PRNGs used, one.

generate random permutation algorithm (from above reference)

enter image description here

($n$ is the size of the permutation and $g$ is the random number in $[0,1]$)

The drawbacks of this approach are related to floating-point calculations and their accuracy, although the performance cited is decent and in accord with other approaches (that have similar issues, e.g using multiple PRNG's which after a while do not meet uniformity criteria depending on number of items $n$ in permutation, and so on..).

[..]The method gives theoretically correct result. However, in practice the random number $g$ and intermediate values of $p$ are all truncated. This may result in computational imprecision for larger values of $m$ or $n$. The instance of a combinatorial object obtained by a computer implementation of above procedure may differ from the theoretically expected one. However, the same problem is present with other known methods (as noted in the previous section) and thus this method is comparable with others in that sense. Next, in applications, randomness is practically preserved despite computational errors.

(ps similar fast and efficient methods are extensively researched and used for my custom combinatorial library for node/JS Abacus, in progress)

$\endgroup$
3
  • $\begingroup$ This seems against the spirit of the question. In effect, you're saying, "Well, you only need one random number: it's just gonna have to have a whooooole lotta bits." This seems to be exploiting an imprecision in the question (which should really be asking about a limited number of random bits) rather than providing a real answer. Also, Yuval has already posted an answer exposing this loophole. $\endgroup$ Dec 19, 2015 at 16:16
  • $\begingroup$ No dont think so. There are a limited number of random bits in a floating-point number and indeed there can be imprecisions with this method (as the reference exactly mentions), but no more severe than other approaches (like unrankling from random index in $[0,n!-1]$). The question tolerates minor imprecision, plus it has the added benefit of not needing computation with big integer arithmetic. $\endgroup$
    – Nikos M.
    Dec 19, 2015 at 16:21
  • $\begingroup$ The method instead of unranking a random index in $[0,n!-1]$ uses a float random number in $[0,1]$ as the probability of a permutation, and then expolits this fact to unrank using simpler floating-point ariuthmetic. In this sense it is an alternative to unranking a permutation from a random index (again only one random number is used) $\endgroup$
    – Nikos M.
    Dec 19, 2015 at 16:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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