Cyclic permutation

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

Definition 1

mapping of permutation

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 + tk] for i = k − t + 1, k − t + 2, ..., k.

Note: Every cyclic permutation of definition type 1 will be constructed with exactly gcd (kt) disjoint cycles of equal length; see cycles and fixed points.

Cyclic permutations of definition type 1 are also called rotations, or circular shifts.

Example:


\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 3 & 4 & 5 & 7 & 6 & 1 & 8 & 2 \end{pmatrix} =
\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 7 & 6 & 8 \\ 3 & 4 & 5 & 7 & 6 & 8 & 1 & 2 \end{pmatrix} =
(1356)(2478)

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.

Definition 2

mapping of permutation

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:


\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 4 & 5 & 7 & 6 & 8 & 2 & 1 & 3 \end{pmatrix} =
\begin{pmatrix} 1 & 4 & 6 & 2 & 5 & 8 & 3 & 7 \\ 4 & 6 & 2 & 5 & 8 & 3 & 7 & 1 \end{pmatrix} =
(14625837)

Definition 3

mapping of permutation

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:


\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 4 & 2 & 7 & 6 & 5 & 8 & 1 & 3 \end{pmatrix} =
\begin{pmatrix} 1 & 4 & 6 & 8 & 3 & 7 & 2 & 5 \\ 4 & 6 & 8 & 3 & 7 & 1 & 2 & 5 \end{pmatrix} =
(146837)(2)(5)

See also


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • cyclic permutation — noun : a permutation in which a set of symbols is rearranged by putting the first for the last (as in ABC, BCA, CAB, ABC) or vice versa …   Useful english dictionary

  • Cyclic order — In mathematics, a cyclic order is a way to arrange a set of objects in a circle.[nb] Unlike most structures in order theory, a cyclic order cannot be modeled as a binary relation a < b . One does not say that east is more clockwise than west.… …   Wikipedia

  • Permutation — For other uses, see Permutation (disambiguation). The 6 permutations of 3 balls In mathematics, the notion of permutation is used with several slightly different meanings, all related to the act of permuting (rearranging) objects or values.… …   Wikipedia

  • Cyclic number — This article is about numbers where permutations of their digits (in some base) yield related numbers. For the number theoretic concept, see cyclic number (group theory). A summary of this article appears in Repeating decimal. A cyclic number is… …   Wikipedia

  • Cyclic (mathematics) — There are many terms in mathematics that begin with cyclic: Cyclic chain rule, for derivatives, used in thermodynamics Cyclic code, linear codes closed under cyclic permutations Cyclic convolution, a method of combining periodic functions Cycle… …   Wikipedia

  • Permutation group — In mathematics, a permutation group is a group G whose elements are permutations of a given set M , and whose group operation is the composition of permutations in G (which are thought of as bijective functions from the set M to itself); the… …   Wikipedia

  • List of permutation topics — This is a list of topics on mathematical permutations.*Alternating group *Alternating permutation *Bijection *Circular shift *Combination *Cycle index *Cycle notation *Cyclic order *Cyclic permutation *Derangement *Even and odd permutations… …   Wikipedia

  • Transposable integer — A summary of this article appears in Repeating decimal. The digits of some specific integers permute or shift cyclically when they are multiplied by a number n. Examples are: 142857 × 3 = 428571 (shifts cyclically one place left) 142857 × 5 =… …   Wikipedia

  • Fisher-Yates shuffle — The Fisher Yates shuffle, named after Ronald Fisher and Frank Yates, also known as the Knuth shuffle, after Donald Knuth, is an algorithm for generating a random permutation of a finite set in plain terms, for randomly shuffling the set. A… …   Wikipedia

  • 142857 (number) — 142,857 is the best known cyclic number in base 10. [ [http://www.daviddarling.info/encyclopedia/C/cyclic number.html Cyclic number ] , The Internet Encyclopedia of Science ] [Michael W. Ecker, [http://links.jstor.org/sici?sici=0049… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.