<p>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.</p>

CC BY-SA 3.0
2016-03-22T20:42:30.270Z
It seems obvious that there exist arbitrarily large $n$ for which $n!-1$ is not polynomially smooth, but do you have a proof of that?
David Eppstein
CC BY-SA 3.0
2016-03-22T21:47:41.333Z
@David Eppstein: No, I don't. I can offer experimental evidence, for what it's worth: $n!-1$ is [prime](https://oeis.org/A002982) for 3, 4, 6, 7, 12, 14, 30, 32, 33, 38, 94, 166, 324, 379, 469, 546, 974, 1963, 3507, 3610, 6917, 21480, 34790, 94550, 103040, 147855.
Peter Shor 
CC BY-SA 3.0
2016-03-23T03:35:49.773Z
Despite my previous answers, I completely agree with this. The previous answers assume make an assumption about the randomness that can be generated which may be incorrect for the setting. I guess it is implicit in the question that the only randomness comes from uniform choices from poly-sized sets. I didn't read it that way, probably in part because the example in the question seems to directly choose a permutation, but of course this could be achieved by making choices from a collection of smaller sets. In retrospect, this appears to be the correct interpretation of the question.
Joe Fitzsimons
CC BY-SA 3.0
2016-03-23T05:47:24.983Z
It seems at some point my past self tried to argue that the probabilities could be chosen using uniform choices from poly sized sets in the comments of one of the answers. Clearly this was wrong.
Joe Fitzsimons
CC BY-SA 3.0
2016-03-22T20:27:50.447Z
2016-03-22T21:49:21.610Z
2016-03-22T21:49:21.610Z
Peter Shor 
<p>I believe the answer is that it is possible in polynomial time as follows:</p>

<p>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. </p>

<p>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}}.$$</p>

<p>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}}.$$</p>

<p>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}}.$$</p>

<p>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)$.</p>

<hr>

<p>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.</p>

<p>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.</p>

<p>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.</p>

<hr>

<p>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.</p>

CC BY-SA 3.0
2011-06-08T04:35:14.870Z
Given $1 \leq i \leq n!$, can we find the $i$th permutation over $[n]$ in the lexicographic ordering in time polynomial in $n$? Probably this is trivial but I don't see it.
Kaveh
CC BY-SA 3.0
2011-06-08T04:39:12.750Z
If we can enumerate the subsets of size $m$ of a set (of size $N=n!$), we can just pick a random number $0 \leq i < {N \choose m}$ and it will give the required $m$ permutations. And mapping $i$ to the corresponding $m$ permutation in time polynomial in $n$ and $m$ seems to be similar to that of computing the $i$th permutation in time polynomial in $n$.
Kaveh
CC BY-SA 3.0
2011-06-08T12:45:05.800Z
@Kaveh: Good question! Yes, it is indeed possible to find the $i$th permutation in polynomial time. It is a bit long to fit in a comment so I have appended it to the answer above. As regards your second comment, $\binom{N}{m}$ is potentially huge, so you'd have to fix $m$ and choose only from these combinations, but that might well be another way to go.
Joe Fitzsimons
CC BY-SA 3.0
2011-06-08T16:19:29.077Z
@Kaveh: Do you want to post your comment as an answer? If so I can remove my other answer, which is quite close to it (and extremely derivative!).
Joe Fitzsimons
CC BY-SA 3.0
2011-06-08T16:21:03.443Z
@Joe, no, I don't, but thanks for asking. :)
Kaveh
CC BY-SA 3.0
2011-06-07T17:40:08.563Z
2016-03-23T05:43:22.650Z
2016-03-23T05:43:22.650Z
Joe Fitzsimons
<p>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.</p>

<blockquote>
  <p>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.</p>
  
  <p>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.</p>
</blockquote>

<p>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.</p>

<hr>

<p>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.</p>

CC BY-SA 3.0
2011-06-09T18:31:39.293Z
Maybe I'm understanding something wrong, but let me give my comment anyway. "pick a uniformly random integer $x_j$ between 0 and $n!−j$": This seems impossible for a poly-time algorithm, since $n!-j$ is too large when $j << n!$. Moreover, while computing $I_P$, you need to compute $\frac{n!}{(n-i)!}$. Firstly, I think this must be $\frac{n!}{(n-k)!}$, and secondly, it will be superpolynomial in $n$ if $k=n/2$.
Sadeq Dousti
CC BY-SA 3.0
2011-06-09T18:43:38.657Z
@Sadeq @Joe: $\frac{n!}{(n-i)!}$ is clearly computable in $n-i$ steps, and can be written in polynomially many bits ($\log n!$ is polynomial in $n$), so I don't see a problem there. but picking a number between $n! -j$ and $0$ seems problematic: it's easy to do in expected $O(\log n!)$ time with rejection sampling, but I don't know about "strict polynomial time".
Sasho Nikolov
CC BY-SA 3.0
2011-06-09T20:17:44.120Z
@Sasho: Thanks for the clarification. Regarding the random choice in strict poly-time, I think the OP has assumed that this is possible.
Sadeq Dousti
CC BY-SA 3.0
2011-06-09T20:22:45.373Z
@Sadeq: that's debatable; he says we can assume a uniform random integer from $[n]$ can be picked in poly time. if the assumption were that for any number $M$, we can assume an subroutine that returns a uniform random integer from $[M]$ and runs in time $\mathsf{poly}(\log M)$, then we'd be good. the whole thing, restriction and assumption, seem a little artificial to me.
Sasho Nikolov
CC BY-SA 3.0
2011-06-09T21:12:10.277Z
@Sasho: He actually assumes that uniformly sampling a set possible, if the size of the set is polynomial in n. This assumption is not restricted to the set [n].
Sadeq Dousti
CC BY-SA 3.0
2011-06-09T21:22:57.880Z
@Sadeq I do not see that anywhere. he says, "assume sampling an element of $T \subseteq [n]$ can be done in strict polynomial time."
Sasho Nikolov
CC BY-SA 3.0
2011-06-09T23:29:25.847Z
@Sasho: Read the rest: "More precisely, we assume that in strict polynomial time, we can uniformly sample from any set whose size is polynomial in n."
Sadeq Dousti
CC BY-SA 3.0
2011-06-10T00:08:40.450Z
@Sadeq: Indeed, but this is enough to pick an integer between $1$ and $n!$ uniformly at random, as follows: For $k=0$ to $k=n-1$ pick $y_k$ uniformly at random between $0$ and $k$. Then compute $R_n = \sum_{k=0}^{n-1} y_k \frac{n!}{(k+1)!}$. The result is a uniformly random number between $0$ and $n!-1$. However, this may not work for $j\neq 0$. I must admit I missed the requirement that the set be polynomial in $n$.
Joe Fitzsimons
CC BY-SA 3.0
2016-03-23T05:29:08.920Z
As Peter Shor points out, this doesn't work for probabilities beyond the first, so there is a problem if you are restricted to pick probabilities in this way for m>1.
Joe Fitzsimons
CC BY-SA 3.0
2011-06-08T14:48:17.480Z
2016-03-23T05:44:43.217Z
2016-03-23T05:44:43.217Z
Joe Fitzsimons
<p>This question compares &quot;strict&quot; polynomial time, as opposed to &quot;expected&quot; polynomial time.</p>
<p>Let <span class="math-container">$S = \{1,2,…,n\}$</span>, and let <span class="math-container">$O$</span> be an ordering on elements of <span class="math-container">$S$</span> (the number of orderings is <span class="math-container">$n!$</span>).</p>
<p>A probabilistic algorithm can easily select a random ordering in &quot;strict&quot; polynomial time (in <span class="math-container">$1^n$</span>), as follows:</p>
<pre>
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)}
</pre>
<p>The algorithm assumes that sampling a random element from <span class="math-container">$T$</span> 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 <span class="math-container">$n$</span>.)</p>
<p>Now let's consider the following problem:</p>
<blockquote>
<p>Choose <span class="math-container">$m$</span> <strong>distinct</strong> random permutations over <span class="math-container">$S$</span>, where <span class="math-container">$m$</span> = poly(<span class="math-container">$n$</span>) &lt; <span class="math-container">$n!$</span>.</p>
</blockquote>
<p>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 &quot;redundant&quot; permutation, throw it away, and start over.</p>
<p>The above approach works in &quot;expected&quot; polynomial time, rather than &quot;strict&quot; polynomial time.</p>
<blockquote>
<p>Is there a strict polynomial time which does the job?</p>
</blockquote>
<p>Edit: Here's a reference for those who want to know more on &quot;strict vs. expected&quot; issue:
<a href="https://doi.org/10.1007/s00145-009-9050-5" rel="nofollow noreferrer">On Expected Probabilistic Polynomial-Time Adversaries: A Suggestion for Restricted Definitions and Their Benefits</a>.</p>

CC BY-SA 3.0
2011-06-07T12:23:38.577Z
i m not sure but i think you are asking if we can derandomize the algorithm in polynomial time?
singhsumit
CC BY-SA 3.0
2011-06-07T12:58:06.547Z
Do you want to generate m distinct permutations uniformly at random or just m permutations uniformly at random?
Robin Kothari
CC BY-SA 3.0
2011-06-07T13:43:00.513Z
"The algorithm assumes that sampling a random element from $T$ can be performed in strict polynomial time."

This assumption isn't true (when $T$ is not a power of 2), so why do you continue after this statement?
Tyson Williams
CC BY-SA 3.0
2011-06-07T14:28:20.590Z
@singhsumit: No, the resulting algorithm is still probabilistic; it just runs in strict rather than expected time. @Robin: thanks, corrected. @Tyson: I know. That's exactly why I made that assumption. That is, **IF** you assume sampling $T$ is possible in strict polynomial time, can we solve the rest?
Rahab
CC BY-SA 3.0
2011-06-07T14:31:52.200Z
there is a standard transformation that will give you an algorithm which fails with small probability and runs always in polynomial time: run the algorithm that has expected polynomial time $T$ for $T/\delta$ steps, and if it hasn't halted yet, output fail. by markov, the fail prob. is $\delta$.
Sasho Nikolov
CC BY-SA 3.0
2011-06-07T14:36:48.277Z
@Sasho: I'm afraid failure of the algorithm is not an option for me. I want it to work correctly all the time, and never run over a certain (polynomial) time.
Rahab
CC BY-SA 3.0
2011-06-07T16:20:52.983Z
If $m=1$, then you are trying to pick an element from a set uniformly at random, which, as we already agreed, cannot be done (unless the size of the set is a power of 2).
Tyson Williams
CC BY-SA 3.0
2011-06-07T16:55:15.263Z
@Rahab: Do you need an exactly uniform distribution? If you can settle for an approximation which is $\epsilon$ close, then it seems there is an easy exact poly time algorithm, since you just repeat $k$ is you generate a redundant permutation, you just retry up to a maximum of $k$ times, and then return permutation $P$, where $P$ is the lowest non-redundant permutation according to some fixed ordering. Since $P$ is always less than $M+1$ this permutation can be found in polynomial time
Joe Fitzsimons
CC BY-SA 3.0
2011-06-07T19:45:47.300Z
@Joe: Unfortunately, the hard part is to pick it **exactly** uniformly. In fact, the problem I'm solving is very sensitive to this.
Rahab
CC BY-SA 3.0
2011-06-07T20:44:09.217Z
@Rahab: See my answer below. It gives an exact distribution. I wrote the previous comment before realising that there was an exact method.
Joe Fitzsimons
<ds.algorithms><permutations><polynomial-time>
Choosing random permutations in "strict" polynomial time
Rahab
# Choosing random permutations in "strict" polynomial time

(Asked by: username_0 on 2011-06-07)

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.

**Tags:** ds.algorithms, permutations, polynomial-time

> **Comments:**
> **username_1**: i m not sure but i think you are asking if we can derandomize the algorithm in polynomial time?  
> **username_2**: Do you want to generate m distinct permutations uniformly at random or just m permutations uniformly at random?  
> **username_3**: "The algorithm assumes that sampling a random element from $T$ can be performed in strict polynomial time."  This assumption isn't true (when $T$ is not a power of 2), so why do you continue after this statement?  
> **username_0**: @username_1: No, the resulting algorithm is still probabilistic; it just runs in strict rather than expected time. @Robin: thanks, corrected. @Tyson: I know. That's exactly why I made that assumption. That is, **IF** you assume sampling $T$ is possible in strict polynomial time, can we solve the rest?  
> **username_4**: there is a standard transformation that will give you an algorithm which fails with small probability and runs always in polynomial time: run the algorithm that has expected polynomial time $T$ for $T/\delta$ steps, and if it hasn't halted yet, output fail. by markov, the fail prob. is $\delta$.  
> **username_0**: @Sasho: I'm afraid failure of the algorithm is not an option for me. I want it to work correctly all the time, and never run over a certain (polynomial) time.  
> **username_3**: If $m=1$, then you are trying to pick an element from a set uniformly at random, which, as we already agreed, cannot be done (unless the size of the set is a power of 2).  
> **username_5**: @username_0: Do you need an exactly uniform distribution? If you can settle for an approximation which is $\epsilon$ close, then it seems there is an easy exact poly time algorithm, since you just repeat $k$ is you generate a redundant permutation, you just retry up to a maximum of $k$ times, and then return permutation $P$, where $P$ is the lowest non-redundant permutation according to some fixed ordering. Since $P$ is always less than $M+1$ this permutation can be found in polynomial time  
> **username_0**: @Joe: Unfortunately, the hard part is to pick it **exactly** uniformly. In fact, the problem I'm solving is very sensitive to this.  
> **username_5**: @username_0: See my answer below. It gives an exact distribution. I wrote the previous comment before realising that there was an exact method.  

---

## 3 answers

### Answer by username_6 on 2016-03-22. Score: 11

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.

> **Comments:**
> **username_7**: It seems obvious that there exist arbitrarily large $n$ for which $n!-1$ is not polynomially smooth, but do you have a proof of that?  
> **username_6**: @username_7: No, I don't. I can offer experimental evidence, for what it's worth: $n!-1$ is [prime](https://oeis.org/A002982) for 3, 4, 6, 7, 12, 14, 30, 32, 33, 38, 94, 166, 324, 379, 469, 546, 974, 1963, 3507, 3610, 6917, 21480, 34790, 94550, 103040, 147855.  
> **username_5**: Despite my previous answers, I completely agree with this. The previous answers assume make an assumption about the randomness that can be generated which may be incorrect for the setting. I guess it is implicit in the question that the only randomness comes from uniform choices from poly-sized sets. I didn't read it that way, probably in part because the example in the question seems to directly choose a permutation, but of course this could be achieved by making choices from a collection of smaller sets. In retrospect, this appears to be the correct interpretation of the question.  
> **username_5**: It seems at some point my past self tried to argue that the probabilities could be chosen using uniform choices from poly sized sets in the comments of one of the answers. Clearly this was wrong.  

---

### Answer by username_5 on 2011-06-07. Score: 10

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: username_8 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 username_6for why this can be a problem.

> **Comments:**
> **username_8**: Given $1 \leq i \leq n!$, can we find the $i$th permutation over $[n]$ in the lexicographic ordering in time polynomial in $n$? Probably this is trivial but I don't see it.  
> **username_8**: If we can enumerate the subsets of size $m$ of a set (of size $N=n!$), we can just pick a random number $0 \leq i < {N \choose m}$ and it will give the required $m$ permutations. And mapping $i$ to the corresponding $m$ permutation in time polynomial in $n$ and $m$ seems to be similar to that of computing the $i$th permutation in time polynomial in $n$.  
> **username_5**: @username_8: Good question! Yes, it is indeed possible to find the $i$th permutation in polynomial time. It is a bit long to fit in a comment so I have appended it to the answer above. As regards your second comment, $\binom{N}{m}$ is potentially huge, so you'd have to fix $m$ and choose only from these combinations, but that might well be another way to go.  
> **username_5**: @username_8: Do you want to post your comment as an answer? If so I can remove my other answer, which is quite close to it (and extremely derivative!).  
> **username_8**: @Joe, no, I don't, but thanks for asking. :)  

---

### Answer by username_5 on 2011-06-08. Score: 5

Here is a much simpler solution to the one posted in my previous answer, inspired by username_8'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 username_6for why this can be a problem.

> **Comments:**
> **username_9**: Maybe I'm understanding something wrong, but let me give my comment anyway. "pick a uniformly random integer $x_j$ between 0 and $n!−j$": This seems impossible for a poly-time algorithm, since $n!-j$ is too large when $j << n!$. Moreover, while computing $I_P$, you need to compute $\frac{n!}{(n-i)!}$. Firstly, I think this must be $\frac{n!}{(n-k)!}$, and secondly, it will be superpolynomial in $n$ if $k=n/2$.  
> **username_4**: @Sadeq @Joe: $\frac{n!}{(n-i)!}$ is clearly computable in $n-i$ steps, and can be written in polynomially many bits ($\log n!$ is polynomial in $n$), so I don't see a problem there. but picking a number between $n! -j$ and $0$ seems problematic: it's easy to do in expected $O(\log n!)$ time with rejection sampling, but I don't know about "strict polynomial time".  
> **username_9**: @Sasho: Thanks for the clarification. Regarding the random choice in strict poly-time, I think the OP has assumed that this is possible.  
> **username_4**: @Sadeq: that's debatable; he says we can assume a uniform random integer from $[n]$ can be picked in poly time. if the assumption were that for any number $M$, we can assume an subroutine that returns a uniform random integer from $[M]$ and runs in time $\mathsf{poly}(\log M)$, then we'd be good. the whole thing, restriction and assumption, seem a little artificial to me.  
> **username_9**: @Sasho: He actually assumes that uniformly sampling a set possible, if the size of the set is polynomial in n. This assumption is not restricted to the set [n].  
> **username_4**: @Sadeq I do not see that anywhere. he says, "assume sampling an element of $T \subseteq [n]$ can be done in strict polynomial time."  
> **username_9**: @Sasho: Read the rest: "More precisely, we assume that in strict polynomial time, we can uniformly sample from any set whose size is polynomial in n."  
> **username_5**: @Sadeq: Indeed, but this is enough to pick an integer between $1$ and $n!$ uniformly at random, as follows: For $k=0$ to $k=n-1$ pick $y_k$ uniformly at random between $0$ and $k$. Then compute $R_n = \sum_{k=0}^{n-1} y_k \frac{n!}{(k+1)!}$. The result is a uniformly random number between $0$ and $n!-1$. However, this may not work for $j\neq 0$. I must admit I missed the requirement that the set be polynomial in $n$.  
> **username_5**: As username_6points out, this doesn't work for probabilities beyond the first, so there is a problem if you are restricted to pick probabilities in this way for m>1.  

---

