1
$\begingroup$

I want to find out a function or algorithm, whichever is suitable, which can provide me a random sequence. Like

Input: 3

Output: {1,2,3} or {1,3,2} or {2,1,3} or {2,3,1} or {3,1,3} or {3,2,1}

Same as if I will enter a number N, output will be a random permutation of the set {1,2,...N}

How can a I write this type of algorithm. Actually I want to find out the logic behind it.

Edit: I don't want to use any buffer to to save anything.

  • 0
    [Cross posted](http://crypto.stackexchange.com/questions/3674/random-sequence-generator-function) on crypto.SE.2012-08-29

2 Answers 2

1

I think the original idea how to do this in linear time is due to Knuth, but I'm not sure. To randomize an array in linear time and constant space, do the following.

for i := 1 to length(A)-1 do:

 Select randomly an index k from i to length(A)`  exchange A[i] and A[k]` 

The selection of $k$ can be done with any random number generator.

Edit: for the newly formulated question, first create the array $A$ in order, i.e. assign initially A[i]=i. Then apply the above permutation and print the result.

  • 0
    @RahulTaneja so start with array $A$ having all integers $1,...,N$ in order, apply the above permutation logic and print the result.2012-08-29
1

The first $O(n)$ shuffle or random permutation generator was published by Richard Durstenfeld in 1964. This algorithm came to the notice of programmers because it was included in Knuth's TAOCP, Vol 2, 1969, page 125, as Algorithm P. A succinct statement of the algorithm is:

\begin{equation} \text{for }\ k \leftarrow n,n-1,\ldots,2\ \text{ do } \begin{cases} \text{Choose at random a number}\ \ r \in [1,k] \\ \text{Interchange }\pi[r] \text{ and }\pi[k],\ \end{cases} \end{equation} where $\pi[1\ldots n]$ is the array to be shuffled or randomly permuted.

See my notes for more information here:RPGLab

  • 0
    commonly known as [Fisher–Yates shuffle](http://en.wikipedia.org/wiki/Fisher–Yates_shuffle)2012-08-29