5
$\begingroup$

Are there any existing efficient algorithms for lazily computing a random permutation of the positive integers in a given range (e.g. the range offered by an unsigned integer type in a CPU)?

What I mean is this:

An algorithm that, given a source of randomness and a positive integer range (for simplicity it could be restricted to starting at 0 and ending at n), can be asked to produce the next value in that range. This can be repeated n times, and a different number is provided by the algorithm each time.

If the caller were to push all of the values retrieved from the algorithm into a queue the resulting ordering would be just as random as if the result had been generated with the Fisher–Yates shuffle.

The naïve implementation would be to pick a random number in the range, check to see if it has already been selected, and choose again if so. This algorithm starts efficient enough, but has increasing complexity for subsequent calls -- too expensive for real-world applications. To really be useful it would have to be O(1) for each trial, though a good logarithmic time might be applicable.

It has to be lazy because with large ranges (such as a 64 bit unsigned integer) it would take Exabytes of storage to precompute the whole permutation, and it is unlikely that a real-world application is going to actually need all of the range; merely it needs that the entire range was considered in values it is actually going to use.

Essentially the problem is just lazily generating a mapping between the integers in a range and a random permutation of those same integers, though being able to access the mapping at arbitrary points instead of just sequentially is but a bonus.

$\endgroup$
  • 1
    $\begingroup$ If $n$ is very large then you would hardly see any duplicates, and so using a hash table the entire process would be $O(1) $ per element, though for $m$ elements you would need $O(m) $ space. If $m\ll \sqrt n$ then you aren't going to see any duplicates at all with high probability, so there is no need to store the preceding values at all, reducing the space requirements to $O(1)$. $\endgroup$ – Yuval Filmus Sep 10 '14 at 23:05
5
$\begingroup$

Yes. Use a block cipher with a small block size. This is extremely efficient and requires extremely little state.

A block cipher is a map $E : K \times X \to X$ such that, for every $k \in K$, $E(k,\cdot)$ is a permutation on $X$ (a bijective function $X\to X$). Moreover, if $k$ is chosen uniformly at random, then $E(k,\cdot)$ acts in a way that is computationally indistinguishable from a function chosen uniformly at random from all permutations on $X$.

Thus, a simple solution is to let $X$ be the set of possible values of an unsigned integer, e.g., $X=\{0,1,2,\dots,2^{64}-1\}$, let $x$ denote a counter ($x \in X$) and $k$ a random key. The state of your pseudorandom generator is $x$ and $k$. When you want a new random number, you output $E(k,x)$ and then increment $x$. This requires very little memory, is extremely efficient, and is provably good (if the block cipher is secure, which is a reasonable assumption given the state of modern cryptography).

You can find information on how to build a block cipher with a small block size here:

$\endgroup$
  • $\begingroup$ And you get random access as a bonus. This seems to be an ideal solution. $\endgroup$ – Techrocket9 Sep 14 '14 at 19:04
2
$\begingroup$

Place your numbers as the leaves of a balanced binary tree, and assign each non-leaf node a number representing how many leaves are below it.

To choose a new number, randomly descend the tree, at each step moving left or right proportional to the leaf counts of the left and right child nodes. Then when you finally get to a leaf, that is the next number in the permutation and cannot be used again. Cross it off, and propagate a $-1$ to the leaf counts back up the tree.

For example, with 8 numbers you would have: enter image description here

For the first number, you randomly descend the tree going each way with left/right probability 50% at each node until you reach the a leaf (say, you got the leaf representing the number 4)

enter image description here

The first part of your permutation is this leaf's number: $$p = (4,\dots)$$

Now you remove the leaf you got from the tree, and propagate the new leaf counts back up the tree.

enter image description here

Now you have the new tree, enter image description here

which you can descend, except with modified probabilities at each node (say you end up with the second number being 8):

enter image description here

The beginning of your permutation is now, $$p = (4,8,\dots)$$

Then delete the leaf you got, and propagate the leaf count correction back up the tree.

enter image description here

You can just repeat this process until you have as many numbers in the permutation as you need.

The initial values in the tree are all known based on the tree height, so you can lazily build the tree as you go rather than constructing it beforehand.

$\endgroup$
  • $\begingroup$ I like the simple elegance of this algorithm, although recursing up the tree is going to be Ω(lg N). Still, 64 operations isn't totally unreasonable in a real-world scenario. I will wait till the weekend to accept an answer after I have time to study D.W.'s reply. $\endgroup$ – Techrocket9 Sep 12 '14 at 4:16
  • $\begingroup$ Just noticed a little bit of an improvement - you can avoid traversing up the tree if you subtract $1$ from nodes as you go down the tree instead. Should make implementation of the lazy tree easier. $\endgroup$ – Nick Alger Sep 12 '14 at 4:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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