|
2003-10-22
How to: Create
random single cycle permutations
Problem: Create a single cycle permutation
over a set M.
Solution:
Obtain a random integer value x, with x in [0..(|M|-1)!),
create the permutation G(x) according to algorithm 2, and use
G(x) to create the cycle of the permutation H(x)
according to the following algorithm:
Algorithm 3:
1. Q := G|M|-1(x)
2. for i := 0 to |M|-2 do
2.1. T[i] := Q(i)
3. j := |M|-1
4. for i := 0 to |M|-2 do
4.1. y := T[i]
4.2. S[j] := y
4.3. j := y
5. S[j] := |M|-1
6. Return P such that, for all a, Phi(P(a)) = S[Phi(a)].
Proposition 3: Algorithm
3 describes a bijective function H from the interval
[0..(|M|-1)!) to the set of single cycle permutations over
M.
Proof: Note
that each element in a cycle occurs exactly once, just like they do
in the sequence <P(0) P(1) ... P(n-1)> corresponding to
a permutation P. Also note that the cyclic decomposition of a
permutation is unique, except for the order of the cycles and the
rotation of the elements in each cycle. Steps 3 and 5 of algorithm 3 might
consequently be justified
by the fact that any cycle of length |M| can be rotated so that the element
|M|-1 is last, making the order of the other |M|-1 elements the only thing that counts.
By the pidgeon hole principle we have that there are exactly (|M|-1)!
single cycle permutations over M.
Hence, all we have
to prove is that T, defined by algorithm 3 with the
addition that T[|M|-1] = |M|-1, describes the
cycle of P. This is clearly the case, because if a and b
are such that P(a) = b, then there is an integer i
such that T[i] = Phi(a) and T[i+1]
= Phi(b).
Q.E.D.
Remark: Algorithm 3 is also an element in
the key schedule of Steak.
|
