## Wednesday, March 24, 2010

### Generate a random permutation of an array of intergers

You are given an array of n integers containing numbers from 1 to n (with repetition), generate a random permutation of the array. The distribution should be uniform.

1. By random permutation if you mean a shuffle then will Knuth Shuffle be acceptable to you?? Or I should think of something else ?

2. that would be a solution yes.

3. you can generate N random numbers uniformly distributed on (0,1) - this takes O(N) - this clearly define a random permutation of {1,2,...,N}

Btw, you might be interested in
http://linbaba.wordpress.com/2010/06/03/random-permutations-and-giant-cycles/