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.
Pubblicato da a
Reazioni: 

3 comments:

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

    ReplyDelete

  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/

    ReplyDelete

Subscribe to: Post Comments (Atom)