العربية
中国
Français
Deutsch
Ελληνική
हिन्दी
Italiano
日本語
Português
Русский
EspañolCYCLIC PERMUTATION
The notion 'cyclic permutation' is used in different but similar ways:
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; 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, 8) = 2 cycles; see image. The used order is: ''c''[6] := 7, ''c''[7] :=6, ''c''[''i''] = ''i'' else.
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:
:
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:
:
★ Cycle notation
★ Stirling number
★ Caesar cipher
| Contents |
| Definition 1 |
| Definition 2 |
| Definition 3 |
| See also |
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; 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, 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 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:
:
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
★ Cycle notation
★ Stirling number
★ Caesar cipher
This article provided by Wikipedia. To edit the contents of this article, click here for original source.
psst.. try this: add to faves
