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. 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