Choosing random permutations in "strict" polynomial time 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$) &lt; $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.
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.