Choosing random permutations in "strict" polynomial time

Question

This question compares "strict" polynomial time, as opposed to "expected" polynomial time.

Let $S = \{1,2,…,n\}$, and let $O$ be an ordering on elements of $S$ (the number of orderings is $n!$).

A probabilistic algorithm can easily select a random ordering in "strict" polynomial time (in $1^n$), as follows:

Let O = {}, T = S
For i = 1 To n
    Let e be a random element from T
    Let T = T - {e}
    Let O = O ∪ {(i,e)}

The algorithm assumes that sampling a random element from $T$ can be performed in strict polynomial time. (More precisely, we assume that in strict polynomial time, we can uniformly sample from any set whose size is polynomial in $n$.)

Now let's consider the following problem:

Choose $m$ distinct random permutations over $S$, where $m$ = poly($n$) < $n!$.

One naive way of doing this is to repeat the above algorithm, keep a record of permutations selected thus far. If the algorithm returns a "redundant" permutation, throw it away, and start over.

The above approach works in "expected" polynomial time, rather than "strict" polynomial time.

Is there a strict polynomial time which does the job?

Edit: Here's a reference for those who want to know more on "strict vs. expected" issue: On Expected Probabilistic Polynomial-Time Adversaries: A Suggestion for Restricted Definitions and Their Benefits.

Answer 1

If the only randomness you can obtain is sampling from a set of polynomial size, you are not going to be able to get two random permutations, because the probability of any particular pair of random permutations is $$ \frac{2}{n! (n! - 1)} $$ and $n!-1$ doesn't necessarily factor into polynomial-size numbers.

Answer 2

I believe the answer is that it is possible in polynomial time as follows:

Each permutation of $N$ can be expressed as a function $f(x)$ which maps an input index to the corresponding output index. Each such function can be expressed as a string $f(1) + f(2) + f(3) + ... + f(N)$, where $+$ is the concatentaion operator. Thus there is a natural lexicographic ordering on the permutations. The idea is to pick the permutations in lexicographic order.

The probability $p_{i,1}$ that permutation $P_i$ will be the first permutation (in lexicographic order) from a set of $M$ permutations of $N$ elements chosen uniformly at random will be $$p_{i,1} = \frac{\binom{N-i}{M-1}}{\binom{N}{M}}.$$

By making a random choice from this probability distribution we determine the first permutation in our set. Let's assume that this permutation is indexed by $x_1$. We now need to choose the permutation which is second lowest in lexicographic order. Clearly, this is the same problem as before, but now we need to choose according to the probability distribution $$p_{i,2} = \frac{\binom{N-x_1-i}{M-2}}{\binom{N-x_1}{M-1}}.$$

For an arbitrary ranking $k$ the probability distribution will be given by $$p_{i,k} = \frac{\binom{N-i-\sum_{j=1}^{k-1} x_j}{M-k}}{\binom{N-\sum_{j=1}^{k-1}x_j}{M-k+1}}.$$

This process is repeated until we have chosen all $M$ permutations. As there is no possibility of collision, the process terminates after exactly $M$ such choices, and hence is an exact polynomial time computation assuming the random choice can be made in time $\mbox{poly}(N)$.

---

UPDATE: Kaveh points out in the comments below that I have not shown how to find the $i$th permutation in time polynomial in $n$, so here is one way.

We can turn an permutation into an integer by taking $I_P = \sum_{k=0}^{n-1} \frac{n!}{(n-i)!} (y_k-1)$. Here $y_k$ is defined as follows: Let $S_0$ be the set of integers from 1 to $N$, and take $S_k = S_0 / \{f(x)\}_{x=1}^k$. Then $y_k$ is the lexicographic index of $f(k+1)$ in $S_k$. Note that $y_k$ is always an integer between 1 and $n-k$. Thus you obtain a unique integer between 0 and $n!-1$ for every permutation. To reverst this and find the $i$th permutation is trivial, since $y_0 = (I_P \mbox{ mod } n)+1$, $y_1 = ((I_P-y_0)/n \mbox{ mod } n)+1$ etc., and once all $y_k$ have been calculated, $f(x)$ can be calculated by taking $f(1) = y_0$, which allows you to calculate $S_1$, which in turn gives you $f(2)$, etc.

Thus you have a polynomial time algorithm for converting a permutation of $n$ items into a unique integer between $0$ and $n!-1$ and back.

---

This answer makes an assumption that it is possible to generate probabilities of the necessary form, which is not necessarily granted in the question. See the answer for Peter Shor for why this can be a problem.

Answer 3

Here is a much simpler solution to the one posted in my previous answer, inspired by Kaveh's comment, which reuses the trick of changing a permutation to a unique integer and back which I quote below (in case an edit to the other answer removes or changes it). Conveniently this new approach does not require you to specify $m$ ahead of time.

We can turn a permutation into an integer by taking $I_P = \sum_{k=0}^{n-1} \frac{n!}{(n-k)!} (y_k-1)$. Here $y_k$ is defined as follows: Let $S_0$ be the set of integers from 1 to $N$, and take $S_k = S_0 / \{f(x)\}_{x=1}^k$. Then $y_k$ is the lexicographic index of $f(k+1)$ in $S_k$. Note that $y_k$ is always an integer between 1 and $n-k$. Thus you obtain a unique integer between 0 and $n!-1$ for every permutation. To reverse this and find the $i$th permutation is trivial, since $y_0 = (I_P \mbox{ mod } n)+1$, $y_1 = ((I_P-y_0)/n \mbox{ mod } n)+1$ etc., and once all $y_k$ have been calculated, $f(x)$ can be calculated by taking $f(1) = y_0$, which allows you to calculate $S_1$, which in turn gives you $f(2)$, etc.

Thus you have a polynomial time algorithm for converting a permutation of $n$ items into a unique integer between $0$ and $n!-1$ and back.

To pick a new permutation $P_j$, pick a uniformly random integer $x_j$ between $0$ and $n! - j$. Let $A_j = S_0 / \{P_i\}_{i=1}^{j-1}$. Take $P_j$ to be the permutation indexed by the $x_j$ in $A_j$. Repeat as often as necessary (i.e. $m$ times). As $A_j$ only includes the remaining non-redundent permutations, and each permutation is drawn uniformly at random from it, this produces the desired stream of random non-redundent permutations in exact polynomial time.

---

This answer makes an assumption that it is possible to generate probabilities of the necessary form, which is not necessarily granted in the question. See the answer for Peter Shor for why this can be a problem.