Cycle

To use the class Cycle, just import it from symmetria in the following way

from symmetria import Cycle

class symmetria.Cycle(*cycle: int)

The Cycle class represents the cycle elements of a symmetric group.

Recall that a cycle is a permutation that rearranges the elements of a finite set in a circular fashion, i.e., moves each element to the position of the next element in a cycle manner, with the last element being moved to the position of the first element.

To define a cycle, you need to provide its cycle notation.

For example, to define the cycle \(\sigma \in S_3\) given by \(\sigma(1)=3\), \(\sigma(2)=1\) and \(\sigma(3)=2\), you should write Cycle(1, 3, 2)

Note

A cycle can have different representations. For example, the cycle Cycle(1, 3, 2) can be also written Cycle(2, 1, 3).

By convention, a cycle start always with the smaller number. Don’t panic, you can define a cycle in the way you like the most, but then it will be stored following the above convention.

Parameters:

cycle (int) – Set of integers representing the cycle notation of the cycle.

Raises:

ValueError – If there is an integer in the provided cycle which is not strictly positive.

Example:

>>> from symmetria import Cycle
...
>>> cycle = Cycle(1, 3, 2)
>>> cycle = Cycle(*[1, 3, 2])
>>> cycle = Cycle(*(1, 3, 2))

__bool__() → bool

Check if the cycle is different from the identity cycle.

Returns:

True if the cycle is different from the identity cycle, False otherwise.

Return type:

bool

Example:

>>> from symmetria import Cycle
...
>>> bool(Cycle(1))
False
>>> bool(Cycle(2, 1, 3))
True

Note:

Every cycle of the form Cycle(n) is considered empty for every \(n \in \mathbb{N}\), i.e., bool(Cycle(n)) = False.

__call__(item: Any) → Any

Call the cycle on the item object, i.e., mimic a cycle action on the element item.

• If item is an integer, it applies the cycle to the integer.

• If item is a string, a list or a tuple, it applies the cycle permuting the values using the indeces.

• If item is a permutation, it returns the composition of the cycle with the permutation.

• If item is a cycle or a cycle decomposition, it returns the composition in cycle decomposition.

Parameters:

item (Any) – The object on which the cycle acts.

Returns:

The permuted object.

Return type:

Any

Raises:

• AssertionError – If the largest element moved by the cycle is greater than the length of item, i.e., the cycle cannot permute the item.

• ValueError – If the cycle and the object item don’t belong to the same Symmetric group.

• TypeError – If the item is not of a supported type. See list above for supported types.

Example:

>>> from symmetria import Cycle, Permutation
...
>>> cycle = Cycle(3, 1, 2)
>>> cycle(2)
3
>>> cycle("abc")
'cab'
>>> cycle([1, 2, 3])
[3, 1, 2]
>>> cycle(Permutation(3, 1, 2))
Permutation(1, 2, 3)

__eq__(other: Any) → bool

Check if the cycle is equal to another object.

Parameters:

other (Any) – The object to compare with.

Returns:

True if the cycle is equal to other, i.e., they define the same map. Otherwise, False.

Return type:

bool

__getitem__(item: int) → int

Return the value of the cycle at the given index item.

The index corresponds to the position in the cycle, starting from 0.

Parameters:

item (int) – The index of the cycle.

Returns:

The value of the cycle at the specified index.

Return type:

int

Raises:

IndexError – If the index is out of range.

__int__() → int

Convert the cycle to its integer representation.

In other words, return a numeric one line notation of the cycle.

Returns:

The integer representation of the cycle.

Return type:

int

Example:

>>> from symmetria import Cycle
...
>>> int(Cycle(1))
1
>>> int(Cycle(13))
13
>>> int(Cycle(3, 1, 2))
123
>>> int(Cycle(1, 3, 4, 5, 2, 6))
134526

__len__() → int

Return the length of the cycle, which is the number of elements in its domain.

Returns:

The length of the cycle.

Return type:

int

Example:

>>> from symmetria import Cycle
...
>>> len(Cycle(3, 1, 2))
3
>>> len(Cycle(1, 3, 4, 5, 2, 6))
6

__mul__(other: Cycle) → Cycle

Implement multiplication between two object.

__pow__(power: int) → Cycle

Return the cycle object to the chosen power.

Parameters:

power (int) – the exponent for the power operation.

Returns:

the power of the cycle.

Return type:

Cycle

Example:

>>> from symmetria import Cycle
...
>>> Cycle(1, 3, 2) ** 0
Cycle(1, 2, 3)
>>> Cycle(1, 3, 2) ** 1
Cycle(1, 3, 2)
>>> Cycle(1, 3, 2) ** -1
Cycle(1, 2, 3)

__repr__() → str

Return a string representation of the cycle in the format “Cycle(x, y, z, …)”, where \(x, y, z, ... \in \mathbb{N}\) are the elements of the cycle.

Returns:

A string representation of the cycle.

Return type:

str

Example:

>>> from symmetria import Cycle
...
>>> Cycle(3, 1, 2).__repr__()
'Cycle(1, 2, 3)'
>>> Cycle(1, 3, 4, 5, 2, 6).__repr__()
'Cycle(1, 3, 4, 5, 2, 6)'

__str__() → str

Return a string representation of the cycle in the form of cycle notation.

Recall that for a cycle \(\sigma\) of order n, its cycle notation is given by \((\sigma(x) \sigma^2(x), ..., \sigma^n(x))\), where x is an element in the support of the cycle.

Returns:

A string representation of the cycle.

Return type:

str

Example:

>>> from symmetria import Cycle
...
>>> print(Cycle(3, 1, 2))
(1 2 3)
>>> print(Cycle(1, 3, 4, 5, 2, 6))
(1 3 4 5 2 6)

cycle_decomposition() → CycleDecomposition

Convert the cycle into its cycle decomposition, representing it as a product of disjoint cycles.

In the specific case of a cycle, it converts it from the class Cycle to the class CycleDecomposition.

Returns:

The cycle decomposition of the permutation.

Return type:

CycleDecomposition

Example:

>>> from symmetria import Cycle
...
>>> Cycle(1).cycle_decomposition()
CycleDecomposition(Cycle(1))
>>> Cycle(3).cycle_decomposition()
CycleDecomposition(Cycle(1), Cycle(2), Cycle(3))
>>> Cycle(3, 1, 2).cycle_decomposition()
CycleDecomposition(Cycle(1, 2, 3))

cycle_notation() → str

Return a string representing the cycle notation of the cycle.

Recall that for a cycle \(\sigma\) of order n, its cycle notation is given by \((\sigma(x) \sigma^2(x), ..., \sigma^n(x))\), where x is an element in the support of the cycle.

Returns:

The cycle notation of the cycle.

Return type:

str

Example:

>>> from symmetria import Cycle
...
>>> Cycle(1).cycle_notation()
'(1)'
>>> Cycle(3, 1, 2).cycle_notation()
'(1 2 3)'
>>> Cycle(3, 1, 2, 4, 5, 6).cycle_notation()
'(1 2 4 5 6 3)'

cycle_type() → Tuple[int]

Raises:

NotImplementedError – The method is not implemented for the class Cycle, because cycles are used as building blocks for permutations and are not proper permutation.

property domain: Iterable[int]

Return an iterable containing the elements of the domain of the cycle.

Here, the domain of a cycle is the set of indices for which the cycle is defined.

Returns:

The domain of the cycle.

Return type:

Iterable[int]

Example:

>>> from symmetria import Cycle
...
>>> Cycle(1).domain
range(1, 2)
>>> Cycle(13).domain
range(1, 14)
>>> Cycle(3, 1, 2).domain
range(1, 4)
>>> Cycle(1, 3, 4, 5, 2, 6).domain
range(1, 7)

property elements: Tuple[int]

Return a tuple containing the elements of the cycle.

Returns:

The elements of the cycle.

Return type:

Tuple[int]

Example:

>>> from symmetria import Cycle
...
>>> Cycle(3, 1, 2).elements
(1, 2, 3)

equivalent(other: Any) → bool

Check if the cycle is equivalent to the other object.

In symmetria, a permutation of the symmetric group can have different representations. For example, it can be a Permutation, or a Cycle, or also a CycleDecomposition. The method checks if the (self) cycle is representing the same permutation of the other object.

Parameters:

other (Any)

Returns:

True if the cycle is equivalent to the other object.

Rtype bool:

Example:

>>> from symmetria import Cycle, Permutation, CycleDecomposition
...
>>> Cycle(1, 2, 3).equivalent(Permutation(2, 3, 1))
True
>>> Cycle(1, 2, 3).equivalent(CycleDecomposition(Cycle(1, 2, 3)))
True
>>> Cycle(1, 2, 3).equivalent(CycleDecomposition(Cycle(1, 2, 3), Cycle(4)))
True

inverse() → Cycle

Return the inverse of the cycle.

Recall that the inverse of a permutation \(\sigma \in S_n\), for some \(n \in \mathbb{N}\), is the the only permutation \(\tau \in S_n\) such that \(\sigma * \tau = \tau * \sigma = id\), where \(id\) is the identity permutation.

In the case of cycles, it suffices to consider the backward cycle.

Returns:

The inverse of the cycle.

Return type:

Cycle

Example:

>>> from symmetria import Cycle
...
>>> Cycle(1, 2, 3).inverse()
Cycle(1, 3, 2)
>>> Cycle(1, 3, 4, 2).inverse()
Cycle(1, 2, 4, 3)
>>> Cycle(2, 3, 1, 5, 4).inverse()
Cycle(1, 3, 2, 4, 5)

inversions() → List[Tuple[int, int]]

Return the inversions of the cycle.

Recall that an inversion of a permutation \(\sigma \in S_n\), for \(n \in \mathbb{N}\), is a pair \((i, j)\) of positions (indexes), where the entries of the permutation are in the opposite order, i.e., \(i<j\) but \(\sigma(i)>\sigma(j)\).

Note

The inversions of the cycle are computed after the cycle is standardized in its normal form, i.e., \(c_1 < c_j\) for every \(c_j \neq c_1\) in the cycle \(c = (c_1, ..., c_n)\).

Returns:

The inversions of the cycle.

Return type:

List[Tuple[int, int]]

Example:

>>> from symmetria import Cycle
...
>>> Cycle(1, 2, 3).inversions()
[]
>>> Cycle(1, 3, 4, 2).inversions()
[(2, 4), (3, 4)]
>>> Cycle(1, 2, 5, 4, 3).inversions()
[(3, 4), (3, 5), (4, 5)]

is_conjugate(other: Cycle) → bool

Raises:

NotImplementedError – The method is_conjugate is not implemented for cycles. This is because cycles are just building blocks for permutations.

is_derangement() → bool

Check if the cycle is a derangement.

Recall that a permutation \(\sigma\) is called a derangement if it has no fixed points, i.e., \(\sigma(x) \neq x\) for every \(x\) in the permutation domain.

By definition, a cycle is a derangement if and only if it is not the identity cycle.

Returns:

True if the cycle is a derangement, False otherwise.

Return type:

bool

Example:

>>> from symmetria import Cycle
...
>>> Cycle(1).is_derangement()
False
>>> Cycle(13).is_derangement()
False
>>> Cycle(1, 2, 3).is_derangement()
True

is_even() → bool

Check if the cycle is even.

Recall that a cycle is said to be even if it can be expressed as the product of an even number of transpositions.

Returns:

True if the cycle is even, False otherwise.

Return type:

bool

Example:

>>> from symmetria import Cycle
...
>>> Cycle(1).is_even()
True
>>> Cycle(1, 2).is_even()
False
>>> Cycle(1, 2, 3, 4, 5, 6).is_even()
False
>>> Cycle(1, 2, 3, 4, 5, 6, 7).is_even()
True

is_odd() → bool

Check if the cycle is odd.

Recall that a cycle is said to be odd if it can be expressed as the product of an odd number of transpositions.

Returns:

True if the cycle is odd, False otherwise.

Return type:

bool

Example:

>>> from symmetria import Cycle
...
>>> Cycle(1).is_odd()
False
>>> Cycle(1, 2).is_odd()
True
>>> Cycle(1, 2, 3, 4, 5, 6).is_odd()
True
>>> Cycle(1, 2, 3, 4, 5, 6, 7).is_odd()
False

is_regular() → bool

Raises:

NotImplementedError – The method is_regular is not implemented for cycles. This is because cycles are just building blocks for permutations, and don’t have a cycle decomposition.

property map: Dict[int, int]

Return a dictionary representing the mapping of the cycle, where keys are indices and values are the corresponding elements after the permutation.

Returns:

The mapping of the cycle.

Return type:

Dict[int, int]

Example:

>>> from symmetria import Cycle
...
>>> Cycle(1).map
{1: 1}
>>> Cycle(3).map
{3: 3}
>>> Cycle(3, 1, 2).map
{1: 2, 2: 3, 3: 1}

orbit(item: Any) → List[Any]

Compute the orbit of item object under the action of the cycle.

Recall that the orbit of the action of a cycle \(\sigma\) on an element x is given by the set \(\{ \sigma^n(x): n \in \mathbb{N}\}\).

Parameters:

item (Any) – The initial element or iterable to compute the orbit for.

Returns:

The orbit of the specified element under the permutation.

Return type:

List[Any]

Example:

>>> from symmetria import Cycle, CycleDecomposition, Permutation
...
>>> Cycle(1, 3, 2).orbit(1)
[1, 3, 2]
>>> Cycle(1, 3, 2).orbit([1, 2, 3])
[[1, 2, 3], [2, 3, 1], [3, 1, 2]]
>>> Cycle(1, 3, 2).orbit("abc")
['abc', 'bca', 'cab']
>>> Cycle(1, 3, 2).orbit(Permutation(3, 1, 2))
[Permutation(3, 1, 2), Permutation(2, 3, 1), Permutation(1, 2, 3)]

order() → int

Return the order of the cycle.

Recall that the order of a permutation \(\sigma\) is the smallest positive integer \(n \in \mathbb{N}\) such that \(\sigma^n = id\), where \(id\) is the identity permutation. Therefore, the order of a cycle is nothing but just its length.

Returns:

The order of the cycle.

Return type:

int

Example:

>>> from symmetria import Cycle
...
>>> Cycle(1).order()
1
>>> Cycle(3, 1, 2).order()
3
>>> Cycle(1, 3, 4, 5, 2, 6).order()
6

sgn() → int

Return the sign of the cycle.

Recall that the sign, signature, or signum of a permutation \(\sigma\) is defined as +1 if \(\sigma\) is even, and -1 if \(\sigma\) is odd.

To compute the sign of a cycle, we use the fact that a cycle is odd if and only if it has even length.

Returns:

1 if the cycle is even, -1 if the cycle is odd.

Return type:

int

Example:

>>> from symmetria import Cycle
...
>>> Cycle(1).sgn()
1
>>> Cycle(1, 2).sgn()
-1
>>> Cycle(1, 2, 3, 4, 5, 6).sgn()
-1
>>> Cycle(1, 2, 3, 4, 5, 6, 7).sgn()
1

support() → Set[int]

Return a set containing the indices in the domain of the cycle whose images are different from their respective indices, i.e., the set of \(n\) in the cycle domain which are not mapped to itself.

The support of a cycle is elementwise equal to the domain of the cycle if and only if the cycle is not the identity cycle. Otherwise, it is empty.

Returns:

The support set of the cycle.

Return type:

Set[int]

Example:

>>> from symmetria import Cycle
...
>>> Cycle(1).support()
set()
>>> Cycle(13).support()
set()
>>> Cycle(3, 1, 2).support()
{1, 2, 3}
>>> Cycle(1, 3, 4, 5, 2, 6).support()
{1, 2, 3, 4, 5, 6}