Permutation

class symmetria.Permutation(*image: int)

The Permutation class represents an element of the symmetric group as a map, i.e., a bijective function from a finite set of integer \(\{1, ..., n\}\), for some \(n \in \mathbb{N}_{>0}\), to itself.

To define a permutation, it is needed to provide a sequence of integers defining the image of the permutation.

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

Parameters:

image (int) – Set of integers defining the image of the permutation.

Raises:

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

• ValueError – If there is an integer which is strictly greater than the total number of integers.

• ValueError – If there are repeated integers.

Example:

>>> permutation = Permutation(3, 1, 2)
>>> permutation = Permutation(*[3, 1, 2])
>>> permutation = Permutation(*(3, 1, 2))

__bool__() → bool

Check if the permutation is different from the identity permutation.

Returns:

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

Return type:

bool

Example:

>>> permutation = Permutation(1)
>>> bool(permutation)
False
>>> permutation = Permutation(2, 1, 3)
>>> bool(permutation)
True

__call__(item: Any) → Any

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

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

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

• If item is a permutation, it returns the multiplication of the two permutations, i.e., the compositions.

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

Parameters:

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

Returns:

The permuted object.

Return type:

Any

Raises:

• AssertionError – If the length of the permutation is greater than the length of item, i.e., the permutation cannot permute the item.

• ValueError – If the permutation 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:

>>> permutation = Permutation(3, 1, 2)
>>> permutation(2)
1
>>> permutation("abc")
"cab"
>>> permutation([1, 2, 3])
[3, 1, 2]
>>> permutation(Permutation(3, 1, 2))
[3, 1, 2]

__eq__(other: Any) → bool

Check if the permutation is equal to another object.

Parameters:

other (Any) – The object to compare with.

Returns:

True if the permutation 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 permutation at the given index item.

In other words, it returns the image of the permutation at point item. The index corresponds to the position in the permutation, starting from 0.

Parameters:

item (int) – The index of the permutation.

Returns:

The value of the permutation at the specified index.

Return type:

int

Raises:

IndexError – If the index is out of range.

__int__() → int

Convert the permutation to its integer representation.

Returns:

The integer representation of the permutation.

Return type:

int

Example:

>>> permutation = Permutation(3, 1, 2)
>>> int(permutation)
312
>>> permutation = Permutation(1, 3, 4, 5, 2, 6)
>>> int(permutation)
134526

__len__() → int

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

Returns:

The length of the permutation.

Return type:

int

Example:

>>> permutation = Permutation(1)
>>> len(permutation)
1
>>> permutation = Permutation(3, 1, 2)
>>> len(permutation)
3
>>> permutation = Permutation(1, 3, 4, 5, 2, 6)
>>> len(permutation)
6

__mul__(other: Permutation) → Permutation

Multiply the permutation with another permutation, resulting in a new permutation that represents the composition of the two permutations.

Parameters:

other (Permutation) – The other permutation to multiply with.

Returns:

The composition of the two permutations.

Return type:

Permutation

Raises:

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

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

Example:

>>> Permutation(1, 2, 3) * Permutation(3, 2, 1)
Permutation(3, 2, 1)
>>> Permutation(1) * Permutation(1)
Permutation(1)
>>> Permutation(3, 4, 5, 1, 2) * Permutation(3, 5, 1, 2, 4)
Permutation(5, 2, 3, 4, 1)

__repr__() → str

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

Returns:

A string representation of the permutation.

Return type:

str

Example:

>>> permutation = Permutation(3, 1, 2)
>>> permutation.__repr__()
Permutation(3, 1, 2)
>>> permutation = Permutation(1, 3, 4, 5, 2, 6)
>>> permutation.__repr__()
Permutation(1, 3, 4, 5, 2, 6)

__str__() → str

Return a string representation of the permutation in the form of tuples.

Returns:

A string representation of the permutation.

Return type:

str

Example:

>>> permutation = Permutation(3, 1, 2)
>>> print(permutation)
(3, 1, 2)
>>> permutation = Permutation(1, 3, 4, 5, 2, 6)
>>> print(permutation)
(1, 3, 4, 5, 2, 6)

cycle_decomposition() → CycleDecomposition

Decompose the permutation into its cycle decomposition.

Returns:

The cycle decomposition of the permutation.

Return type:

CycleDecomposition

Example:

>>> permutation = Permutation(1)
>>> permutation.cycle_decomposition()
(1)
>>> permutation = Permutation(3, 1, 2)
>>> permutation.cycle_decomposition()
(1 3 2)
>>> permutation = Permutation(1, 3, 4, 5, 2, 6)
>>> permutation.cycle_decomposition()
(1)(2 3 4 5)(6)

cycle_notation() → str

Return a string representing the cycle notation of the permutation.

Returns:

The cycle notation of the permutation.

Return type:

str

Example:

>>> Permutation(1).cycle_notation()
'(1)'
>>> Permutation(3, 1, 2).cycle_notation()
'(1 3 2)'
>>> Permutation(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 permutation.

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

Returns:

The domain of the permutation.

Return type:

Iterable[int]

Example:

>>> permutation = Permutation(1)
>>> permutation.domain()
range(1, 2)
>>> permutation = Permutation(3, 1, 2)
>>> permutation.domain()
range(1, 4)
>>> permutation = Permutation(1, 3, 4, 5, 2, 6)
>>> permutation.domain()
range(1, 7)

equivalent(other: Any) → bool

Check if the permutation is equivalent to another object.

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

Parameters:

other (Any) – The object to compare with.

Returns:

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

Return type:

bool

Example:

>>> permutation_a = Permutation(1, 2, 3)
>>> permutation_b = Permutation(1, 2, 3)
>>> permutation_a.equivalent(permutation_b)
True
>>> permutation = Permutation(3, 1, 2)
>>> cycle = Cycle(1, 3, 2)
>>> cycle.equivalent(cycle)
True
>>> permutation = Permutation(2, 1, 4, 3)
>>> cycle_decomposition = CycleDecomposition(Cycle(1, 2), Cycle(3, 4))
>>> permutation.equivalent(cycle_decomposition)
True

classmethod from_cycle(cycle: Cycle) → Permutation

Return a permutation from a cycle.

In other word, it converts a cycle into a permutation.

Parameters:

cycle (Cycle) – A cycle.

Returns:

A permutation equivalent to the given cycle.

Return type:

Permutation

Example:

>>> permutation = Permutation.from_cycle(Cycle(1))
>>> print(permutation) # Permutation(1)
(1)
>>> permutation = Permutation.from_cycle(Cycle(1, 2, 3)) # Permutation(2, 3, 1)
>>> print(permutation) # Permutation(2, 3, 1)
(2, 3, 1)
>>> permutation = Permutation.from_cycle(Cycle(3)) # Permutation(1, 2, 3)
>>> print(permutation) # Permutation(1, 2, 3)
(1, 2, 3)

classmethod from_cycle_decomposition(cycle_decomposition: CycleDecomposition) → Permutation

Return a permutation from a cycle decomposition.

In other word, it converts a cycle decomposition into a permutation.

Parameters:

cycle_decomposition (CycleDecomposition) – A cycle decomposition.

Returns:

A permutation equivalent to the given cycle.

Return type:

Permutation

Example:

>>> cd = CycleDecomposition(Cycle(1))
>>> Permutation.from_cycle_decomposition(cd)
(1)
>>> cd = CycleDecomposition(Cycle(4, 3), Cycle(1, 2)))
>>> Permutation.from_cycle_decomposition(cd)
(2, 1, 4, 3)

classmethod from_dict(p: Dict[int, int]) → Permutation

Create a permutation object from a dictionary where keys represent indices and values represent the images of the indeces.

Parameters:

p (Dict[int, int]) – A dictionary representing the permutation.

Returns:

A permutation created from the dictionary.

Return type:

Permutation

Example:

>>> permutation = Permutation.from_dict({1: 3, 2: 1, 3:, 2})
>>> print(permutation) # Permutation(2, 1, 2)
(3, 1, 2)

inverse() → Permutation

Return the inverse of the permutation.

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

Return type:

Permutation

Example:

>>> Permutation(1, 2, 3).inverse()
Permutation(1, 2, 3)
>>> Permutation(1, 3, 4, 2).inverse()
Permutation(1, 4, 2, 3)
>>> Permutation(2, 3, 1, 5, 4).inverse()
Permutation(3, 1, 2, 5, 4)

is_derangement() → bool

Check if the permutation 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:

>>> permutation = Permutation(1)
>>> permutation.is_derangement()
False
>>> permutation = Permutation(3, 1, 2)
>>> permutation.is_derangement()
True
>>> permutation = Permutation(1, 3, 4, 5, 2, 6)
>>> permutation.is_derangement()
False

property map: Dict[int, int]

Return a dictionary representing the mapping of the permutation.

The keys of the dictionary are indices, while the values are the corresponding elements after permutation.

Returns:

The mapping of the permutation.

Return type:

Dict[int, int]

Example:

>>> permutation = Permutation(1)
>>> permutation.map()
{1: 1}
>>> permutation = Permutation(3, 1, 2)
>>> permutation.map()
{1: 3, 2: 1, 3: 3}

one_line_notation() → str

Return a string representation of the permutation in the one-line notation, i.e., in the form \(\sigma(x_1)\sigma(x_2)...\sigma(x_n)\), where \(\sigma\) is a permutation and \(x_1, ..., x_n\) are the elements permuted by \(\sigma\).

Returns:

The one-line notation of the permutation.

Return type:

str

Example:

>>> permutation = Permutation(1)
>>> permutation.one_line_notation()
'1'
>>> permutation = Permutation(3, 1, 2)
>>> permutation.one_line_notation()
'123'
>>> permutation = Permutation(1, 3, 4, 5, 2, 6)
>>> permutation.one_line_notation()
'134524'

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 permutation \(\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 permutation.

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.

Returns:

The order of the permutation.

Return type:

int

Example:

>>> permutation = Permutation(3, 1, 2)
>>> permutation.order()
1
>>> permutation = Permutation(3, 1, 2)
>>> permutation.order()
3
>>> permutation = Permutation(1, 3, 4, 5, 2, 6)
>>> permutation.order()
4

sgn() → int

Return the sign of the permutation.

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.

Returns:

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

Return type:

int

Example:

>>> Permutation(1).sgn()
1
>>> Permutation(2, 1).sgn()
-1
>>> Permutation(2, 3, 4, 5, 6, 1).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 permutation.

Return type:

Set[int]

Example:

>>> permutation = Permutation(1)
>>> permutation.support()
set()
>>> permutation = Permutation(3, 1, 2)
>>> permutation.support()
{1, 2, 3}
>>> permutation = Permutation(1, 3, 4, 5, 2, 6)
>>> permutation.support()
{2, 3, 4, 5}