6
$\begingroup$

The problem:

  • To generate a list of size $n$,
  • Containing unique integers,
  • Sampled uniformly in the range $\left[0,m\right)$,
  • In $O(n)$ time, except that:
    • Assuming $m$ is bounded by some word-size, $\left|m\right|$, the specific time should be $O(n\cdot\left|m\right|)$, as one cannot do better than this.

Apologies if this is a duplicate, if you find one, feel free to point it out.


EDIT: to clarify, the question implies that we are concerned the complixity in terms of bit-operations. (See logarithmic cost model).

$\endgroup$
  • 2
    $\begingroup$ What are your thoughts on the problem? $\endgroup$ – Yuval Filmus Jan 31 '16 at 21:22
  • $\begingroup$ Your problem is easy if $n = O(\sqrt{m})$ (a random sample will work with constant probability) or $n = \Omega(m)$ (compute a random permutation and take the first $n$ elements). $\endgroup$ – Yuval Filmus Jan 31 '16 at 21:26
  • $\begingroup$ @YuvalFilmus I have a complicated answer that gets it to $O(n\cdot |m|^2)$, but it feels way too complicated, and doesn't reach $O(n\cdot |m|)$. I intend on posting it after a few hours, but basically it creates an |m| deep trie, and weights the branches based on the count of integers already chosen; the weights are cheap to maintain and can be used to calculate a uniform random path to the bottom that will never hit a previous result. $\endgroup$ – Realz Slaw Jan 31 '16 at 21:30
4
$\begingroup$

Here is a solution in $O(n\log n)$ (with high probability). We consider two cases: $n\log n \geq m$ and $n\log n \leq m$. In the first case, we choose a random permutation of $[0,m)$ and take only the first $n$ elements. This takes time $O(m) = O(n\log n)$. In the second case, we maintain a balanced binary search tree (or equivalent), adding to it random elements from $[0,m)$ one by one, checking for duplicates each time. In expectation we need to try at most $1/\log n = o(1)$ extra times for each element, so the expected running time of this algorithm is $O(n\log n)$. In fact, the running time is $O(n\log n)$ also with high probability.

We can obtain an expected $O(n)$ solution by replacing the balanced binary search tree with a hash table, and changing the cutoff to $n \geq m/2$ versus $n \leq m/2$.

$\endgroup$
  • $\begingroup$ For the first case (of larger $n$), we can actually bound it lower can't we? $\endgroup$ – Realz Slaw Feb 1 '16 at 14:50
  • $\begingroup$ For the second case, we can use some sort of hash-set to get $O(n\cdot|m|)$, no? $\endgroup$ – Realz Slaw Feb 1 '16 at 14:50
  • $\begingroup$ You are right about the first case – it should be $O(n)$. In the second case $n = O(m)$, so $O(n\log n)$ is better than $O(n\log m)$. $\endgroup$ – Yuval Filmus Feb 1 '16 at 16:04
  • $\begingroup$ (The last comment depends on the computation model.) $\endgroup$ – Yuval Filmus Feb 1 '16 at 16:10
  • $\begingroup$ Aha, can you elaborate on the different possibilities of computation models and the resulting times for something like a hash-set? $\endgroup$ – Realz Slaw Feb 1 '16 at 20:06
4
$\begingroup$

Another approach is to use format-preserving encryption (e.g., a Feistel cipher) to build a pseudorandom permutation on the domain $\{0,1,\dots,m-1\}$, then encrypt the sequence $0,1,\dots,n-1$ and output the encrypted sequence. The randomness of this will be dependent upon cryptographic assumptions, and it might or might not perform as well as the other alternatives in practice.

If we use the Feistel cipher construction, then I would expect the running time of each encryption to be $O(|m|)$, so the running time to generate the full sequence to be $O(n \cdot |m|)$. However, expressing asymptotic runtime in this way might be a bit misleading, as it assumes one can build a PRF on $\{0,1,\dots,m-1\}$ whose running time is $O(|m|)$. That is indeed possible under suitable cryptographic assumptions (e.g., that AES is secure), but it does require those unproven assumptions. So while this is an approach you could try if you want this for a practical purpose, it might not be very useful if your goal is to prove a theorem about computational complexity.

$\endgroup$
  • $\begingroup$ Can we compute the cost of computing a domain in terms of $m$? $\endgroup$ – Realz Slaw Feb 1 '16 at 14:46
  • $\begingroup$ @RealzSlaw, done -- see last paragraph of the answer. $\endgroup$ – D.W. Feb 1 '16 at 16:36
  • $\begingroup$ So you expect AES-like ciphers to be secure with a constant number of rounds? $\endgroup$ – Yuval Filmus Feb 1 '16 at 21:40
  • $\begingroup$ @YuvalFilmus, yes: the Luby-Rackoff theorem proves that the Feistel construction is secure with 4 rounds, if each round uses a PRF. (Here the assumption that AES is secure is used to build a PRF, that can be used in each round.) (As a minor comment, I wouldn't call a Feistel cipher AES-like.) $\endgroup$ – D.W. Feb 2 '16 at 7:23
  • $\begingroup$ Your PRF is AES-like, so again, do you expect your AES-like PRF to be secure using a constant number of rounds? The designers of AES don't seem to think so. $\endgroup$ – Yuval Filmus Feb 2 '16 at 7:27
4
$\begingroup$
  1. Make a binary tree/trie, starting with nothing in the trie
  2. Pick a uniform random number over $\left[0,m\right)$
  3. Pad the number to $|m|$ bits, adding leading zeros if necessary
  4. Insert the number into the binary tree/trie, one bit at a time where a 0 bit means "left" and a 1 bit means "right", inserting nodes as necessary:

  5. Every node in the binary tree/trie will keep track of the number of nodes underneath it in the binary tree/trie; it should be easy to maintain these tracking/values with no added complexity:

  6. Based on the previous step, it is possible to compute how many unused-numbers are possible under each branch in the tree: Given the depth of the node and the height of the tree, and the "number of nodes underneath it" from the previous step, it is possible to calculate the number of "unused numbers" on each branch:

  7. Using those numbers as weights, the next number should be computed by a weighted random selection of the branches. If a branch has a "unused numbers" weight of 0, then it will have zero chance of being selected, ensuring uniqueness.

  8. Go to step 3 and repeat until $n$ numbers are selected.

Complexity (feel free to correct):

  • Each insertion is $O(|m|)$, the depth of the binary tree/trie
  • Maintaining the weights adds no complexity
  • Choosing the random branches/bits would itself require a weighted random selection, for each branch/bit
  • A simple weighted random selection could take $O(|m|)$ time, given a $O(1)$ fair coin tossing method
  • Computing each number would therefore take |m| bit selections * O(|m|) time per selection * n integers = $O(n\cdot \left|m\right|^2)$
$\endgroup$
  • 1
    $\begingroup$ This potentially runs in $O(n\log m)$. You have to be careful with the tree, making it "lazy", not expanding all nodes unless they are required. This way the tree only has $O(n\log m)$ nodes. $\endgroup$ – Yuval Filmus Feb 1 '16 at 21:52
  • $\begingroup$ @YuvalFilmus I added a section on complexity $\endgroup$ – Realz Slaw Feb 1 '16 at 21:59

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.