Random commentary about Machine Learning, BigData, Spark, Deep Learning, C++, STL, Boost, Perl, Python, Algorithms, Problem Solving and Web Search
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.
By random permutation if you mean a shuffle then will Knuth Shuffle be acceptable to you?? Or I should think of something else ?
ReplyDeletethat would be a solution yes.
ReplyDeleteyou can generate N random numbers uniformly distributed on (0,1) - this takes O(N) - this clearly define a random permutation of {1,2,...,N}
ReplyDeleteBtw, you might be interested in
http://linbaba.wordpress.com/2010/06/03/random-permutations-and-giant-cycles/