Cycle

class symmetria.Cycle(*cycle: int)

The Cycle class represents the cycles element 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 here, a cycle start always with the smaller number.

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:

>>> 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:

>>> cycle = Cycle(1)
>>> bool(cycle)
False
>>> cycle = Cycle(2, 1, 3)
>>> bool(cycle)
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:

>>> 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:

>>> cycle = Cycle(1)
>>> int(cycle)
1
>>> cycle = Cycle(13)
>>> int(cycle)
13
>>> cycle = Cycle(3, 1, 2)
>>> int(cycle)
312
>>> cycle = Cycle(1, 3, 4, 5, 2, 6)
>>> int(cycle)
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:

>>> cycle = Cycle(3, 1, 2)
>>> len(cycle)
3
>>> Cycle = Cycle(1, 3, 4, 5, 2, 6)
>>> len(cycle)
6

__mul__(other: Cycle) → Cycle

Implement multiplication between two object.

__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:

>>> cycle = Cycle(3, 1, 2)
>>> cycle.__repr__()
Cycle(3, 1, 2)
>>> cycle = Cycle(1, 3, 4, 5, 2, 6)
>>> cycle.__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:

>>> cycle = Cycle(3, 1, 2)
>>> print(cycle)
(3 1 2)
>>> cycle = Cycle(1, 3, 4, 5, 2, 6)
>>> print(cycle)
(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:

>>> cycle = Cycle(1)
>>> cycle.cycle_decomposition()
CycleDecomposition(Cycle(1))
>>> cycle = Cycle(3)
>>> cycle.cycle_decomposition()
CycleDecomposition(Cycle(1), Cycle(2), Cycle(3))
>>> cycle = Cycle(3, 1, 2)
>>> cycle.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:

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

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:

>>> cycle = Cycle(1)
>>> cycle.domain()
range(1, 2)
>>> cycle = Cycle(13)
>>> cycle.domain()
range(1, 14)
>>> cycle = Cycle(3, 1, 2)
>>> cycle.domain()
range(1, 4)
>>> cycle = Cycle(1, 3, 4, 5, 2, 6)
>>> cycle.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:

>>> cycle = Cycle(3, 1, 2)
>>> cycle.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:

>>> 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)))
False

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 the identity cycle.

Returns:

True if the cycle is a derangement, False otherwise.

Return type:

bool

Example:

>>> cycle = cycle(1)
>>> cycle.is_derangement()
True
>>> cycle = cycle(13)
>>> cycle.is_derangement()
True
>>> cycle = cycle(1, 2, 3)
>>> cycle.is_derangement()
False

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:

>>> cycle = Cycle(1)
>>> cycle.map
{1: 1}
>>> cycle = Cycle(3)
>>> cycle.map
{1: 1, 2: 2, 3: 3}
>>> cycle = Cycle(3, 1, 2)
>>> cycle.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:

>>> permutation = Permutation(3, 1, 2)
>>> permutation.orbit(1)
[1, 3, 2]
>>> permutation.orbit([1, 2, 3])
[[1, 2, 3], [2, 3, 1], [3, 1, 2]]
>>> permutation.orbit("abc")
['abc', 'bca', 'cab']
>>> permutation.orbit(Permutation(3, 1, 2))
[Permutation(3, 1, 2), Permutation(2, 3, 1), Permutation(1, 2, 3)]
>>> permutation.orbit(Cycle(1, 2, 3))
[
    CycleDecomposition(Cycle(1, 2, 3)),
    CycleDecomposition(Cycle(1), Cycle(2), Cycle(3)),
    CycleDecomposition(Cycle(1, 3, 2)),
]

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:

>>> cycle = Cycle(3, 1, 2)
>>> cycle.order()
1
>>> cycle = Cycle(3, 1, 2)
>>> cycle.order()
3
>>> cycle = Cycle(1, 3, 4, 5, 2, 6)
>>> cycle.order()
4

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:

>>> cycle = Cycle(1)
>>> cycle.support()
set()
>>> cycle = Cycle(13)
>>> cycle.support()
set()
>>> cycle = Cycle(3, 1, 2)
>>> cycle.support()
{1, 2, 3}
>>> cycle = Cycle(1, 3, 4, 5, 2, 6)
>>> cycle.support()
{2, 3, 4, 5}