About being able to sample a permutation of a finite set uniformly at random I was looking at this question. 


So if I understand the above discussion right then it concludes that if say one had access to an oracle which can uniformly at random sample from a finite set then one can't using this uniformly at random sample a permutation of another finite set (chosen may be adversarially) and also have the algorithm be guaranteed to halt. 

Is the above summary right?
Is there a reference to a proof of the above? 
Is there a fundamental understanding of this impossibility? 
If one is allowed say (1) exponential space or (2) the oracle was picking the numbers with some bias then can we get across this impossibility? 
What are the consequences if hypothetically one could do the above?
Claim. Given access to finitely many samples of the uniform distribution over $\{1,\ldots,N\}$, you can sample uniformly from $\{1,\ldots,M\}$ iff $M \mid N^k$ (read: $M$ divides $N^k$) for some $k$.

Proof. Suppose first that $M \mid N^k$ for some $k$. Combine $k$ samples of $\{1,\ldots,N\}$ to get a uniform sample $x$ of $\{1,\ldots,N^k\}$, and return $x \pmod{M}$, which is understood to return a value in $\{1,\ldots,M\}$ rather than the more usual $\{0,\ldots,M-1\}$. There are exactly $N^k/M$ preimages of each $y \in \{1,\ldots,M\}$, namely $y,y+M,y+2M,\ldots,y+(N^k/M-1)M$. Therefore $x \pmod{M}$ is a uniform sample from $\{1,\ldots,M\}$.

Suppose next that using $k$ samples you can sample uniformly from $\{1,\ldots,M\}$. As before, we can think of the $k$ samples as a uniform sample from $\{1,\ldots,N^k\}$. Let $A$ be the preimage of $1$, that is the set of $x \in \{1,\ldots,N^k\}$ which cause the algorithm to return $1$. Since the algorithm returns $1$ with probability $1/M$, we must have $|A|/N^k = 1/M$ and so $|A| = N^k/M$, which can only happen if $M \mid N^k$. $\qquad\square$

Sampling a permutation on $M$ elements is the same as sampling a number in the range $\{1,\ldots,M!\}$. This is possible using finitely many samples from $\{1,\ldots,N\}$ if and only if $M! \mid N^k$ for some $k$.

This proof is quite elementary, so you can probably find many references, though none are really needed.