1
$\begingroup$

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.

$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ Commented Feb 9, 2013 at 16:27
  • $\begingroup$ @ℝⁿ: Wikipedia describes this as the "inside-out" variant of Fisher-Yates. $\endgroup$ Commented Feb 9, 2013 at 22:37

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.