What is the most efficient way to generate a random permutation of first n natural numbers?

Tag: algorithm , implementation , permutation , probability , random-sample Author: wghibe Date: 2012-08-13

Until now i have been using a list which keeps track of all unique numbers encounterd. I am using a random number generator to get a random number between 1 and n. if that number is already in my list then i just keep on generating random numbers until i encounter a number which is not in my list. When I get a new number which is not on my list, i add it to my list and repeat the process until all 'n' numbers are there in my list.

Clearly this method is very inefficient. Can someone propose an efficient solution to this??

Best Answer

Knuth's your man for this, though other algorithms are available.

Other Answer1

  • Create an ordered list with the numbers from 1 to N.
  • Shuffle it (i.e., create a permutation of it). This can be done linear time (see this algorithm).