Cyclic permutation
The notion cyclic permutation is used in different but similar ways:
Encyclopedia
The notion
cyclic permutation is used in different but similar ways:
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 and the mapping of P may be written as:
- p = c[i + t] for i = 1, 2, ..., k − t, and
- p = 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 disjoint cycles; see
cycles and fixed points.
Cyclic permutations of definition type 1 are also called rotations.
Example:
is a cyclic permutation with offset 2. It may be constructed with gcd = 2 cycles; see image. The used order is:
c[6] := 7,
c[7] :=6,
c[
i] =
i else.
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 is prime
- it is a cyclic permutation of definition type 1 with offset = 1
"it is a cyclic permutation of definition type 1 with offset =
k − 1.
Example:
Definition 3
A permutation is called a cyclic permutation if and only if only 1 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:
See also
