Random Permutation

Alioune Ngom (angom@csi.uottawa.ca)
Fri, 23 Feb 1996 12:12:39 +0100


Hi everybody,

Does anyone know of an algorithm that generate a random permutation
of N? The method I am using is the following:

Given N, I compute N! and generate randomly a number P <= N! (since I am
programming in Pascal this is done by the function "random(N!)". Then,
having P, I compute its corresponding permutation of N (since there is a
bijection between the first N! natural numbers and the N! permutations of
N). Thus this method give a random permutaion. However it works only for
N <= 13, this because the function random() takes a word as parameter and,
for N > 14 the value N! is too large (to be contained in a word) and thus
the function random(N!) is undefined.

Another method is to randomly generate each P[i] of the permutation of N,
where 1 <= i <= N and 1 <= P[i] <= N. But then we will have to check for
P[i]'s that contain the same value and insert values which are absent in P.

Is there another method which is known to be efficient?

I need you help, please. I am using this in my work with ordered set an
linear extensions (using a genetic algorithm to find and optimize the
linear extensions of an order ...).

Thank you in advance.

Alioune Ngom.