Take the 2-minute tour ×
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.

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|improve this question

1 Answer 1

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

 
discard

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.