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$

closed as unclear what you're asking by David Richerby, FrankW, D.W., Yuval Filmus, Juho Jun 14 '14 at 7:21

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

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