Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 3 down vote accepted

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$.

share|cite|improve this answer
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
@ℝⁿ: Wikipedia describes this as the "inside-out" variant of Fisher-Yates. – Henning Makholm Feb 9 '13 at 22:37

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.