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
    You might get a fine answer here. If not, you could try to migrate the question to http://crypto.stackexchange.com/. Over there they are good at stuff like that.2012-08-29
  • 0
    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.2012-08-29
  • 0
    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.2012-08-29
  • 0
    @Thomas: thanx, I have posted it on crypto.stackexchange.com2012-08-29
  • 0
    Have you looked up random permutation generation on google?2012-08-29
  • 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
    Please check the edited question2012-08-29
  • 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