# Random Sequence Generator function

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.

-
You might get a fine answer here. If not, you could try to migrate the question to crypto.stackexchange.com. Over there they are good at stuff like that. – Thomas Aug 29 '12 at 17:09
If you are just looking to get the job done, there should be a pseudorandom number generator in the library of whatever language you're using. – Austin Mohr Aug 29 '12 at 17:11
Actually my aim is to find out all the records randomly. I am not talking about any language etc. I want just the logic to retrieve all the records without any repetition, which can be shown by my question. – Rahul Taneja Aug 29 '12 at 17:14
@Thomas: thanx, I have posted it on crypto.stackexchange.com – Rahul Taneja Aug 29 '12 at 17:19
Have you looked up random permutation generation on google? – Max Aug 29 '12 at 17:20

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.

-
Please check the edited question – Rahul Taneja Aug 29 '12 at 17:29
@RahulTaneja so start with array $A$ having all integers $1,...,N$ in order, apply the above permutation logic and print the result. – gt6989b Aug 29 '12 at 17:52

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:

$$\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}$$ where $\pi[1\ldots n]$ is the array to be shuffled or randomly permuted.