Cycle Decomposition

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

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:

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

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

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

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

>>> cycle_decomposition = CycleDecomposition(Cycle(1, 2), Cycle(3, 4))
>>> for cycle in cycle_decomposition:
>>>     print(cycle)
Cycle(1, 2)
Cycle(3, 4)

__len__() → int

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

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

__mul__(other: CycleDecomposition) → CycleDecomposition

Multiplies 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

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

>>> cycle_decomposition = CycleDecomposition(Cycle(1))
>>> cycle_decomposition.__repr__()
CycleDecomposition(Cycle(1))
>>> cycle_decomposition = CycleDecomposition(Cycle(1, 3), Cycle(2))
>>> cycle_decomposition.__repr__()
CycleDecomposition(Cycle(1, 3), Cycle(2))
>>> cycle_decomposition = CycleDecomposition(Cycle(1, 3), Cycle(4, 5, 2, 6))
>>> cycle_decomposition.__repr__()
CycleDecomposition(Cycle(1, 3), Cycle(4, 5, 2, 6))

__str__() → str

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

Returns:

A string representation of the cycle decomposition.

Return type:

str

Example:

>>> cycle_decomposition = CycleDecomposition(Cycle(1))
>>> str(cycle_decomposition)
(1)
>>> cycle_decomposition = CycleDecomposition(Cycle(1, 3), Cycle(2))
>>> str(cycle_decomposition)
(1 3)(2)
>>> cycle_decomposition = CycleDecomposition(Cycle(1, 3), Cycle(4, 5, 2, 6))
>>> str(cycle_decomposition)
(1 3)(4 5 2 6)

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

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

Returns:

The cycle notation of the permutation.

Return type:

str

Example:

>>> cycle_decomposition = CycleDecomposition(Cycle(1))
>>> cycle_decomposition.cycle_notation()
'(1)'
>>> cycle_decomposition = CycleDecomposition(Cycle(1, 3, 2))
>>> cycle_decomposition.cycle_notation()
'(1 3 2)'
>>> cycle_decomposition = CycleDecomposition(Cycle(1, 3, 2), Cycle(4))
>>> cycle_decomposition.cycle_notation()
'(1 3 2)(4)'

property domain: Iterable[int]

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

>>> cycle_decomposition = CycleDecomposition(Cycle(1))
>>> cycle_decomposition.domain()
range(1, 2)
>>> cycle_decomposition = CycleDecomposition(Cycle(3, 1, 2))
>>> cycle_decomposition.domain()
range(1, 4)
>>> cycle_decomposition = CycleDecomposition(Cycle(1), Cycle(3, 4, 5, 2, 6))
>>> cycle_decomposition.domain()
range(1, 7)

equivalent(other: Any) → bool

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

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

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:

>>> cycle_permutation = CycleDecomposition(Cycle(1))
>>> cycle_permutation.is_derangement()
False
>>> cycle_decomposition = CycleDecomposition(Cycle(1, 2, 3))
>>> cycle_decomposition.is_derangement()
True
>>> cycle_decomposition = CycleDecomposition(Cycle(1), Cycle(2, 3))
>>> cycle_decomposition.is_derangement()
False

property map: Dict[int, int]

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

>>> cycle_decomposition = CycleDecomposition(Cycle(1))
>>> cycle_decomposition.map()
{1: 1}
>>> cycle_decomposition = CycleDecomposition(Cycle(1, 2), Cycle(3, 4))
>>> cycle_decomposition.map()
{1: 2, 2: 1, 3: 4, 4: 3}

orbit(item: Any) → List[Any]

Return the orbit created from the action of the element on the item.

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:

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

support() → Set[int]

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

>>> cycle_decomposition = CycleDecomposition(Cycle(1))
>>> cycle_decomposition.support()
set()
>>> cycle_decomposition = CycleDecomposition(Cycle(1), Cycle(2, 3))
>>> cycle_decomposition.support()
{2, 3}