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.

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.

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

2 Answers 2

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.

share|improve this answer
    
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:

\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

share|improve this answer
    
commonly known as Fisher–Yates shuffle –  CodesInChaos Aug 29 '12 at 18:14

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.