# Algorithm to generate a random sequence.

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.

-

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$.
The proof of correctness is via induction, yes? // I was going to suggest initializing an array to $[0...n-1]$ in order and doing the Fisher-Yates shuffle, but this is nicer. – Rahul Feb 9 '13 at 16:27