Search code examples
algorithmrandompermutation

random permutation

I would like to generate a random permutation as fast as possible. The problem: The Knuth shuffle which is O(n) involves generating n random numbers. Since generating random numbers is quite expensive, I would like to find an O(n) function involving a fixed O(1) amount of random numbers.

I realize that this question has been asked before, but I did not see any relevant answers.

Just to stress a point: I am not looking for anything less than O(n), just an algorithm involving less generation of random numbers.

Thanks.

Solution

  • Create a 1-1 mapping of each permutation to a number from 1 to n! (n factorial). Generate a random number in 1 to n!, use the mapping, get the permutation.

    For the mapping, perhaps this will be useful: http://en.wikipedia.org/wiki/Permutation#Numbering_permutations

    Of course, this would get out of hand quickly, as n! can become really large soon.