Cyclic permutation
 |
This article does not cite any references or sources. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. (April 2011) |
A cyclic permutation or circular permutation is a permutation built from one or more sets of elements in cyclic order.
The notion "cyclic permutation" is used in different, but related ways:
Contents |
[edit] Definition 1
A permutation P over a set S with k elements is called a cyclic permutation with offset t if and only if
- the elements of S may be ordered (c[1] < c[2] < ... < c[k]) and the mapping of P may be written as:
- p(c[i] ) = c[i + t] for i = 1, 2, ..., k − t, and
- p(c[i]) = c[i + t − k] for i = k − t + 1, k − t + 2, ..., k.
Note: Every cyclic permutation of definition type 1 will be constructed with exactly gcd (k, t) disjoint cycles of equal length; see cycles and fixed points.
Cyclic permutations of definition type 1 are also called rotations, or circular shifts.
Example:
is a cyclic permutation with offset 2. It may be constructed with gcd(8, 2) = 2 cycles; see image. The used order is: c[6] := 7, c[7] :=6, c[i] = i else.
[edit] Definition 2
A permutation is called a cyclic permutation if and only if it will be constructed with exactly 1 cycle.
Note: Every permutation over a set with k elements is a cyclic permutation of definition type 2 if and only if it is a cyclic permutation of definition type 1 with gcd(k, offset) = 1
Example:
[edit] Definition 3
A permutation is called a cyclic permutation if and only if only one of the constructing cycles will have length > 1.
Note: Every cyclic permutation of definition type 3 may be seen as an union of a cyclic permutation of definition type 2 and some fixed points.
Every cyclic permutation of definition type 2 may be seen ″as a cyclic permutation of definition type 3 with zero fixed points.
Example:
