0
$\begingroup$

Is there a way to generate a random permutation of the numbers 1 to N such that I can find the k-th element of the permuted list without needing to either 1) store the entire permuted list, or 2) compute the elements 1..k-1?

$\endgroup$
  • 1
    $\begingroup$ If you're not going to store the entire permutation, in what sense are you generating a random permutation? If all you need to know is the $k$th element of a random permutation, then just take a uniformly random element – the distribution is the same. $\endgroup$ – Yuval Filmus Jun 13 '14 at 6:12
  • $\begingroup$ I'm going to be using a selection of elements from the permutation, but not neccessarily the entire permutation. $\endgroup$ – user19349 Jun 13 '14 at 6:15
  • 3
    $\begingroup$ Can you specify your problem completely? Let us know what operations this data structure should support. $\endgroup$ – Yuval Filmus Jun 13 '14 at 6:15
  • 1
    $\begingroup$ Agree with @YuvalFilmus. If it's a random permutation, what's the difference between 1st and kth permutation? $\endgroup$ – Omer Iqbal Jun 13 '14 at 18:47
1
$\begingroup$

Problem statement

Your question is unclear, but here is how I interpret it:

Input: a positive integer $n$, and $k$ distinct values $x_1,\dots,x_k \in \{1,2,\dots,n\}$ Output: the values $\pi(x_1),\pi(x_2),\dots,\pi(x_k)$, where $\pi$ is a random permutation on $\{1,2,\dots,n\}$

You are looking for an efficient algorithm to solve this problem.

An efficient solution

If that is indeed what you are looking for, there is a very efficient way to solve this problem. Basically, all you need to do is randomly choose $k$ distinct integers from the set $\{1,2,\dots,n\}$. This is sampling without replacement. Here is a simple algorithm:

  • Initialize $S$ to be the empty set.

  • For $i=1,2,\dots,k$:

    • Pick $r$ uniformly at random from $\{1,2,\dots,n\}$. If $r\in S$, pick a new $r$ (and keep repeating until $r \notin S$).

    • Set $x_i$ to $r$, and add $r$ to $S$.

You can use any number of data structures for storing the set $S$; it could be a bitvector of length $n$, or a hashtable. (A bitvector is probably better if $k$ is not too much smaller than $n$, say $k \ge n/64$ or so; a hashtable is probably more efficient if $k$ is small compared to $n$.)

Performance analysis

If $k \le n/2$, the expected running time is linear in $n$, so this is very efficient.

If $k \ge n/2$, there are better algorithms. For instance, once you reach $i \ge n/2$, then rather than choosely uniformly, you can choose uniformly at random from $\overline{S}$ (the complement of $S$). If you use the right data structures, you can make the expected running time be linear in $n$. (Basically, once $i\ge n/2$, you compute $\overline{S}$ and throw away $S$. In each step, you choose a random element of $\overline{S}$, then remove it from $\overline{S}$. Choosing a random element of a set can be done in $O(1)$ expected time.)

$\endgroup$
-1
$\begingroup$

If you rank all the n! Permutaions in some order, such as the lexicographic order, then you can unrank a number to a permutation. The procedure is simple. So given a random number in [1..n!], you can compute a random permutation.

$\endgroup$
  • $\begingroup$ The poster doesn't want just a random permutation, they want the kth element of a random permutation without storing the permutation or calculating the first k-1 values, Also why rank N! permutations when you can just shuffle the list of numbers 1 to N, ranking all permutations just to pick one random one seems convoluted and time consuming? $\endgroup$ – lPlant Jun 13 '14 at 16:17

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