Cyclic Permutation - Definition 1

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 < c < ... < c) and the mapping of P may be written as:

p(c ) = c for i = 1, 2, ..., k − t, and

p(c) = c 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 := 7, c :=6, c = i else.