Cyclic permutation

From Free net 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 iff

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; see cycles and fixed points.

Cyclic permutations of definition type 1 are also called rotations.

Example:

<math>

\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 7 & 6 & 8 \\ 3 & 4 & 5 & 7 & 6 & 8 & 1 & 2 \end{pmatrix}</math>

is a cyclic permutation with offset 2. It may be constructed with gcd(2, 8) = 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 iff 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

iff it is a cyclic permutation of definition type 1 with gcd(k, offset) is prime

iff it is a cyclic permutation of definition type 1 with offset = 1

iff it is a cyclic permutation of definition type 1 with offset = k − 1.

Example:

<math>

\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 7 & 6 & 8 \\ 4 & 5 & 7 & 6 & 8 & 1 & 2 & 3 \end{pmatrix} = \begin{pmatrix} 1 & 4 & 6 & 2 & 5 & 8 & 3 & 7 \\ 4 & 6 & 2 & 5 & 8 & 3 & 7 & 1 \end{pmatrix}</math>

Definition 3

A permutation is called a cyclic permutation iff 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:

<math>

\begin{pmatrix} 1 & 4 & 6 & 8 & 3 & 7 & 2 & 5 \\ 4 & 6 & 8 & 3 & 7 & 1 & 2 & 5 \end{pmatrix}</math>

See also

• Cycle notation
• Stirling number
• Caesar cipher