Let $f(n):\mathbb N \to\mathbb N$, be a function randomly gives a integer from $0$ to $n-1$. How can I generate a random sequence of integer with $n$ element which contain every integer from $0$ to $n-1$.
My thought is to begin with a sequence $0,1,2,…,n-1$, randomly choose 2 elements to swap, i.e. the $f(n)$th and $f(n)$th element, and repeat this many times. But this method cannot ensure every element will be swapped. So is there any more efficient method that truly generate a random sequence? Thank you.
Best Answer
One standard proceudre is as follows:
For $i=0,\ldots, n-1$, let $x$ be a random integer uniformly selected from $\{0,\ldots,i\}$ and if $x=i$, let $A[i]=i$, else let $A[i]=A[x]$ and $A[x]=i$.
The resulting array $A[0\ldots n-1]$ is arandom permutation of $0,\ldots,n-1$.