|
2003-10-22
How to: Create random
permutations
Problem: Create a random
permutation over a set M.
Solution: Obtain a
random integer value x, with x in [0..|M!|), and create a permutation over
[0..|M|)
according to the following algorithm:
Algorithm 2:
1. T[0] := 0
2. for i := 1 to |M|-1 do
2.1. y := x mod (i+1)
2.2. x := x div (i+1)
2.3. for j := 0 to i-1 do
2.3.1. if not (T[j]
< y) then T[j] := T[j] + 1
2.4. Append element T[i] = y
to the array T.
4. Return P such that, for each a, Phi(P(a)) = T[Phi(a)].
Proposition 2: Algorithm
2 describes a bijective function G from the the interval [0..|M|!)
to the set of permutations over
M.
Proof: Simply
note that Algorithm 2 is the inverse of algorithm 1.
Q.E.D.
Remark: There are several alternative
algorithms. The following is, for historical reasons, an element of the key schedule of
Steak:
Algorithm 2.1:
1. Let S be the null set.
2. k := 0
3. for i := |M|-1 downto 1 do
3.1. y := x mod (i+1)
3.2. x := x div (i+1)
3.3. for j := 1 to y do
3.3.1. repeat until not (k in S)
3.3.1.1. k :=
(k+1) mod (|M|+1)
3.4. Include k into S.
3.5. T[i] = k
4. Return P such that, for each a, Phi(P(a)) = T[Phi(a)].
Algorithm 2.1 is
slightly slower than algorithm 2, both execute in poly(2) time, and
there are algorithms that do the job in linear time. However, these
algorithm correspond to different mappings. Algorithm 2.1 is the
fastest known implementation of that particular mapping from [0..|M!|)
to the set of permutations over M.
The following
algorithm executes in linear time:
Algorithm 2.2:
1. for i := 0 to |M|-1 do
1.1. T[i] := i
2. for i := |M|-1 downto 1 do
2.1. y := x mod (i+1)
2.2. x := x div (i+1)
2.3. Swap the elements at position i and y in T;
3. Return P such that, for each a, Phi(P(a)) = T[Phi(a)].
|
