2
$\begingroup$

We all know Fisher-Yates takes an array and shuffles it as per the output of a PRNG.

My question is in relation to what would be the "correct" implementation to select multiple sets (e.g. n sets of k lottery numbers). Is the answer :

  1. Re-initialise array to default state, shuffle and pick ; or
  2. Assuming the array is long enough, continue picking along array; or
  3. Re-shuffle already shuffled array and pick; or
  4. It does't make any difference as long as Fisher-Yates and PRNG are correctly implemented.

At the moment, I'm leaning towards number four. But then I know that "crypto is hard" and that I am merely a learning beginner when it comes to cryptography!

$\endgroup$
4
  • $\begingroup$ Do you want different sets to be able to contain the same numbers? $\endgroup$
    – otus
    Nov 25, 2016 at 15:24
  • $\begingroup$ I'm not sure if this question really falls within our scope here on crypto.SE: as long as you assume the existence of a secure pseudorandom number generator (i.e. one computationally indistinguishable from a true random number source), this is a pure combinatorics problem with no crypto-specific elements, and might be better suited for Computer Science, Stack Overflow or even Mathematics. Still, given that it's not blatantly off-topic here, I'm tempted to just give an answer here and let the mods migrate this question if it's judged to be off-topic. $\endgroup$ Nov 25, 2016 at 15:51
  • $\begingroup$ @IlmariKaronen Borderlining... I think it "could" find a nice home as CS, but I'm not absolutely sure about that. (Mainly because I haven't been visiting CS for a while now.) OTOH, we did answer some of these questions (from a crypto point of view) in the past here too. Personally, I'ld tend to keep it until/unless someone decides to actually flag this for migration. $\endgroup$
    – e-sushi
    Nov 25, 2016 at 16:52
  • $\begingroup$ @otus They should be different accross the selection "instance" (e.g. in my given example of lottery, there's not much point picking 5 sets of the same numbers in a given "run" of the generator). $\endgroup$ Nov 25, 2016 at 19:36

1 Answer 1

6
$\begingroup$

Let me start by trying to rephrase your question in more precise terms. (Please let me know if this rephrasing doesn't match what you intended to ask.)

Let $\textsf{random}$ be a (pseudo)random number generator that, given a positive integer $n$, returns a random integer uniformly sampled from the set $\{0, 1, 2, \dots, n-1\}$. I assume that the output of this generator is computationally indistinguishable from that of a true source of independent uniformly distributed random numbers. (Constructing such a generator is the only cryptographically challenging part here. Everything else is just combinatorics.)

Let me introduce the following helper procedure, which essentially performs one step of the Fisher–Yates shuffle:

$\text{procedure }\textsf{rand_swap}(A, n, i): \\ \quad j \leftarrow i + \textsf{random}(n-i); \\ \quad (A_i, A_j) \leftarrow (A_j, A_i). $

That is, given an array $A = (A_0, A_1, A_2, \dots, A_{n-1})$ of (at least) $n$ elements, and a base index $0 \le i < n$ into this array, $\textsf{rand_swap}(A,n,i)$ picks a random second index $i \le j < n$ and swaps the array elements $A_i$ and $A_j$ (which might be the same, if $j = i$).

Using this helper function, the Fisher–Yates shuffle for an $n$-element array $A$ can be implemented as:

$\text{procedure }\textsf{shuffle}(A, n): \\ \quad \text{for each } i \text{ from } 0 \text{ to } n-1: \\ \quad\quad \textsf{rand_swap}(A, n, i). $

Also, the same algorithm can be used to implement a partial shuffle:

$\text{procedure }\textsf{partial_shuffle}(A, n, k): \\ \quad \text{for each } i \text{ from } 0 \text{ to } k-1: \\ \quad\quad \textsf{rand_swap}(A, n, i). $

After such a partial shuffle, the sub-array $A^{(k)} = (A_0, A_1, A_2, \dots, A_{k-1})$ contains a randomly shuffled uniform sample of $k$ values drawn without replacement from the original array $A$.


Now, we finally get to your question. Specifically, as I understand it, you wish to repeatedly draw a random sample of $k \le n$ elements from an $n$-element array $A$, and ask which of the following methods will do:

Method 1:

For each sample, initialize $B$ as a copy of the array $A$, call $\textsf{partial_shuffle}(B,n,k)$ and let the sample be the first $k$ elements of $B$.

Method 2:

Let $s$ be the total number of elements sampled so far. For each new $k$-element sample, while $s + k \le n$, run the following continued partial shuffle:

$\text{for each } i \text{ from } s \text{ to } s+k-1: \\ \quad \textsf{rand_swap}(A, n, i). $

and let $(A_s, A_{s+1}, \dots, A_{s+k-1})$ be the sample. After sampling, increment $s$ by $k$.

Method 3:

Same as method 1, except that we repeatedly (partially) shuffle the same array instead of reinitializing it every time. That is, for each sample, call $\textsf{partial_shuffle}(A,n,k)$ and let the sample be the first $k$ elements of $A$, retaining the shuffled array $A$ for the next iteration.


The answer is that, as long as our pseudorandom number generator is indeed indistinguishable from a truly random source of uniform independent random integers, methods 1 and 3 are equivalent. They both generate a sequence of independent random $k$-element samples from the original array, where the elements within each sample are drawn without replacement, but where different samples are fully independent.

This equivalence follows from the observation that, regardless of the initial order of the array $A$, after each call to $\textsf{rand_swap}(A,n,i)$ within $\textsf{partial_shuffle}$, $A_i$ will be uniformly sampled from among the elements of $A$ not already chosen during earlier iterations.

(If the pseudorandom number generator is not perfect, method 3 may be somewhat better at disguising some of its flaws, especially if a full shuffle is used instead of a partial one. This is because retaining the state of the array $A$ between iterations effectively maintains a large partially hidden state that carries forward some of the randomness from previous shuffles. This is the main reason why e.g. physically shuffling a previously used deck of playing cards often yields adequately random-looking results after only a few iterations, whereas a new or deliberately sorted deck of cards needs to be much more thoroughly shuffled before it loses all traces of its original order.)

Method 2, however, does something very different: in effect, it draws individual random elements from the original array without replacement, returning these in blocks of $k$ elements. In particular, if a given element appears in one $k$-element sample, it cannot appear in any other sample drawn from the same array using this method.

Of course, if the array size $n$ is very large compared to the total number of elements sampled from it (squared, due to the birthday paradox), then the probability of ever seeing the same element twice even with methods 1 or 3 is negligible, and so all the methods are effectively indistinguishable. But in that case, you might as well not bother with shuffling at all, but simply pick random elements from the original array with replacement, since that will also yield only a negligible chance of ever seeing the same element twice.

$\endgroup$
0

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.