Cycle Decomposition

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

from symmetria import CycleDecomposition

class symmetria.CycleDecomposition(*cycles: Cycle)

The CycleDecomposition class represents the cycle decomposition of a permutation of the symmetric group.

Recall that every permutation of the symmetric group can be represented uniquely as the composition of a finite number of cycles thanks to the Cycle Decomposition Theorem for Permutations.

To define a permutation as a cycle decomposition, you need to provide its cycles.

For example, to define the permutation given by the cycles: Cycle(2, 1) and Cycle(4, 3), you should write CycleDecomposition(Cycle(2, 1), Cycle(4, 3)).

Note

By convention, a cycle decomposition starts always with the smaller cycle, i.e., the cycle with the smallest element, and is increasing.

This is because a cycle decomposition can have different representations. Don’t panic, you can write the cycle decomposition in the way you like the most, but then it will be stored following the above convention.

Parameters:

cycle (Cycle) – Cycle factors of the permutation.

Raises:

• ValueError – If there are two or more cycles with non-disjoint support.

• ValueError – If there are missing cycles in the decomposition.

Example:

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

__bool__() → bool

Check if the cycle decomposition is non-empty, i.e., it is different from the identity cycle decomposition.

Returns:

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

Return type:

bool

Example:

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

Note:

Every cycle of the form CycleDecomposition(Cycle(n)) is considered empty for every \(n \in \mathbb{N}\), i.e., bool(CycleDecomposition(Cycle(n))) = False. Same for cycle decomposition of identity cycle, e.g., CycleDecomposition(Cycle(1), Cycle(2), Cycle(3)).

__call__(item: Any) → Any

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

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

• If item is a string, a list or a tuple, it applies the cycle decomposition permuting the values by indexes.

• If item is a permutation, it returns the composition of the cycle decomposition 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:

• ValueError – If there are not enough elements in the item to perform the permutation.

• ValueError – If attempting to compose the cycle decomposition with a permutation, cycle, or cycle decomposition from a different symmetric group.

• TypeError – If the item type is not supported.

__eq__(other: Any) → bool

Check if the cycle decomposition is equal to the another object.

Parameters:

other (Any) – The object to compare with.

Returns:

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

Return type:

bool

__getitem__(idx: int) → Cycle

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

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

Parameters:

idx (int) – The index of the cycle.

Returns:

The cycle of the cycle decomposition at the specified index.

Return type:

int

Raises:

IndexError – If the index is out of range.

Example:

>>> from symmetria import Cycle, CycleDecomposition
...
>>> CycleDecomposition(Cycle(1, 2), Cycle(3, 4))[0]
Cycle(1, 2)

__int__() → int

Raises:

NotImplementedError – The method is not implemented for the class CycleDecomposition, because it is not possible to uniquely represent a cycle decomposition of a permutation using just an integer.

__iter__() → Iterable[Cycle]

Return an iterator over the cycles in the cycle decomposition.

Returns:

An iterator over the cycles in the cycle decomposition.

Return type:

Iterable[Cycle]

Example:

>>> from symmetria import Cycle, CycleDecomposition
...
>>> for cycle in CycleDecomposition(Cycle(1, 2), Cycle(3, 4)):
...     print(cycle)
(1 2)
(3 4)

__len__() → int

Return the length of the cycle decomposition, which is the number of cycles present in the decomposition.

Returns:

The length of the cycle decomposition.

Return type:

int

Example:

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

__mul__(other: CycleDecomposition) → CycleDecomposition

Multiply the cycle decomposition with another cycle decomposition, resulting in a new cycle decomposition that represents the composition of the two cycle decompositions.

Parameters:

other (CycleDecomposition) – The other cycle decomposition to multiply with.

Returns:

The composition of the two cycle decompositions.

Return type:

CycleDecomposition

Raises:

• ValueError – If the cycle decompositions don’t live in the same Symmetric group.

• TypeError – If the other object is not a CycleDecomposition.

__repr__() → str

Return a string representation of the cycle decomposition in the format ‘CycleDecomposition(Cycle(x, …), Cycle(y, …), …)’, where \(x, y, ... \in \mathbb{N}\) are the elements of the cycles.

Returns:

A string representation of the cycle decomposition.

Return type:

str

Example:

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

__str__() → str

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

Returns:

A string representation of the cycle decomposition.

Return type:

str

Example:

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

cycle_decomposition() → CycleDecomposition

Return the cycle decomposition of the permutation.

As a cycle decomposition is already in the cycle decomposition, the method return the cycle decomposition itself.

Returns:

The cycle decomposition of the permutation.

Return type:

CycleDecomposition

cycle_notation() → str

Return a string representing the cycle notation of the cycle decomposition.

Returns:

The cycle notation of the permutation.

Return type:

str

Example:

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

cycle_type() → Tuple[int]

Return the cycle type of the cycle decomposition.

Recall that the cycle type of the permutation \(\sigma\) is a sequence of integer, where There is a 1 for every fixed point of \(\sigma\), a 2 for every transposition, and so on.

Note

Note that the resulting tuple is sorted in ascending order.

Returns:

The cycle type of the cycle decomposition.

Return type:

Tuple[int]

Example:

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

property domain: Iterable[int]

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

The domain of a cycle decomposition is the set of indices for which the cycle decomposition is defined.

Returns:

The domain of the cycle decomposition.

Return type:

Iterable[int]

Example:

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

equivalent(other: Any) → bool

Check if the cycle decomposition is equivalent to another object.

This method is introduced because we can have different representation of the same cycle decomposition, e.g., as a cycle, or as permutation.

Parameters:

other (Any) – The object to compare with.

Returns:

True if the cycle decomposition is equivalent to the other object, False otherwise.

Return type:

bool

Example:

>>> from symmetria import Cycle, CycleDecomposition, Permutation
...
>>> cycle_decomposition = CycleDecomposition(Cycle(1, 2, 3))
>>> cycle_decomposition.equivalent(cycle_decomposition)
True
>>> cycle = Cycle(1, 2, 3)
>>> cycle_decomposition.equivalent(cycle)
True
>>> permutation = Permutation(2, 3, 1)
>>> cycle_decomposition.equivalent(permutation)
True

inverse() → CycleDecomposition

Return the inverse of the cycle decomposition.

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.

Returns:

The inverse of the cycle decomposition.

Return type:

CycleDecomposition

Example:

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

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

Return the inversions of the cycle decomposition.

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)\).

Returns:

The inversions of the ycle decomposition.

Return type:

List[Tuple[int, int]]

Example:

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

is_conjugate(other: CycleDecomposition) → bool

Check if two cycle decompositions are conjugated.

Recall that two permutations \(\sigma, \quad \tau \in S_n\), for some \(n \in \mathbb{N}\), are said to be conjugated if there is \(\gamma \in S_n\) such that \(\gamma\sigma\gamma^{-1} = \tau\).

Parameters:

other (CycleDecomposition) – a cycle decomposition

Returns:

True if self and other are conjugated, False otherwise.

Return type:

bool

Example:

>>> from symmetria import Cycle, CycleDecomposition
...
>>> cycle_dec = CycleDecomposition(Cycle(1, 2, 3))
>>> cycle_dec.is_conjugate(cycle_dec)
True
>>> cycle_dec_a = CycleDecomposition(Cycle(1, 3, 2, 5, 4))
>>> cycle_dec_b = CycleDecomposition(Cycle(1, 4, 3, 5, 2))
>>> cycle_dec_a.is_conjugate(cycle_dec_b)
True
>>> cycle_dec_a = CycleDecomposition(Cycle(1, 2), Cycle(3, 4))
>>> cycle_dec_b = CycleDecomposition(Cycle(1), Cycle(3, 2, 4))
>>> cycle_dec_a.is_conjugate(cycle_dec_b)
False

is_derangement() → bool

Check if the cycle decomposition 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.

Returns:

True if the permutation is a derangement, False otherwise.

Return type:

bool

Example:

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

is_even() → bool

Check if the cycle decomposition is even.

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

Returns:

True if the cycle decomposition is even, False otherwise.

Return type:

bool

Example:

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

is_odd() → bool

Check if the cycle decomposition is odd.

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

Returns:

True if the cycle decomposition is odd, False otherwise.

Return type:

bool

Example:

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

is_regular() → bool

Check if the cycle decomposition is regular.

Recall that a permutation is said regular if all cycles in its cycle decomposition have the same length.

Returns:

True if the cycle decomposition is regular, False otherwise.

Return type:

bool

Example:

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

property map: Dict[int, int]

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

Returns:

The mapping of the cycle decompostiion.

Return type:

Dict[int, int]

Example:

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

orbit(item: Any) → List[Any]

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

Recall that the orbit of the action of a cycle decomposition \(\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]

order() → int

Return the order of the cycle permutation.

Recall that the order of a cycle decompostion is the least common multiple of lengths (order) of its cycles.

Returns:

The order of the cycle permutation.

Return type:

int

Example:

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

sgn() → int

Return the sign of the cycle decomposition.

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 decomposition, we use the fact that the sign is a homomorphism of groups, i.e., the sign of the cycle decomposition is just the product of the signs of the cycle componing it.

Returns:

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

Return type:

int

Example:

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

support() → Set[int]

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

Returns:

The support set of the cycle decomposition.

Return type:

Set[int]

Example:

>>> from symmetria import Cycle, CycleDecomposition
...
>>> CycleDecomposition(Cycle(1)).support()
set()
>>> CycleDecomposition(Cycle(1), Cycle(2, 3)).support()
{2, 3}