Permutation

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

from symmetria import 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:

>>> from symmetria import Permutation
...
>>> 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:

>>> from symmetria import Permutation
...
>>> bool(Permutation(1))
False
>>> bool(Permutation(2, 1, 3))
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:

>>> from symmetria import Permutation
...
>>> permutation = Permutation(3, 1, 2)
>>> permutation(2)
1
>>> permutation("abc")
'bca'
>>> permutation([1, 2, 3])
[2, 3, 1]
>>> permutation(Permutation(3, 1, 2))
Permutation(2, 3, 1)

__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

Example:

>>> from symmetria import Permutation
...
>>> Permutation(1, 2, 3) == Permutation(1, 2, 3)
True
>>> Permutation(1, 2, 3) == Permutation(3, 2, 1)
False
>>> Permutation(1, 2, 3) == 12
False

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

Note

The index corresponds to the element in the domain of the permutation, i.e., the index is a number between 1 and the length of the permutation.

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.

Example:

>>> from symmetria import Permutation
...
>>> permutation = Permutation(2, 3, 1)
>>> for idx in range(1, len(permutation)+1):
...     permutation[idx]
2
3
1

__int__() → int

Convert the permutation to its integer representation.

Returns:

The integer representation of the permutation.

Return type:

int

Example:

>>> from symmetria import Permutation
...
>>> int(Permutation(3, 1, 2))
312
>>> int(Permutation(1, 3, 4, 5, 2, 6))
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:

>>> from symmetria import Permutation
...
>>> len(Permutation(1))
1
>>> len(Permutation(3, 1, 2))
3
>>> len(Permutation(1, 3, 4, 5, 2, 6))
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:

>>> from symmetria import Permutation
...
>>> 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)

__pow__(power: int) → Permutation

Return the permutation object to the chosen power.

Parameters:

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

Returns:

the power of the permutation.

Return type:

Permutation

Raises:

TypeError – If power is not an integer.

Example:

>>> from symmetria import Permutation
...
>>> Permutation(3, 1, 2)**0
Permutation(1, 2, 3)
>>> Permutation(3, 1, 2)**1
Permutation(3, 1, 2)
>>> Permutation(3, 1, 2)**-1
Permutation(2, 3, 1)
>>> Permutation(3, 1, 2)**2
Permutation(2, 3, 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:

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

__str__() → str

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

The string representation represents the image of the permutation.

Returns:

A string representation of the permutation.

Return type:

str

Example:

>>> from symmetria import Permutation
...
>>> print(Permutation(3, 1, 2))
(3, 1, 2)
>>> print(Permutation(1, 3, 4, 5, 2, 6))
(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:

>>> from symmetria import Cycle, CycleDecomposition, Permutation
...
>>> Permutation(1).cycle_decomposition()
CycleDecomposition(Cycle(1))
>>> Permutation(3, 1, 2).cycle_decomposition()
CycleDecomposition(Cycle(1, 3, 2))
>>> Permutation(1, 3, 4, 5, 2, 6).cycle_decomposition()
CycleDecomposition(Cycle(1), Cycle(2, 3, 4, 5), Cycle(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:

>>> from symmetria import Permutation
...
>>> 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)'

cycle_type() → Tuple[int]

Return the cycle type of the permutation.

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

The resulting tuple is sorted in ascending order.

Returns:

The cycle type of the permutation.

Return type:

Tuple[int]

Example:

>>> from symmetria import Permutation
...
>>> Permutation(1).cycle_type()
(1,)
>>> Permutation(3, 1, 2).cycle_type()
(3,)
>>> Permutation(3, 1, 2, 4, 5, 6).cycle_type()
(1, 1, 1, 3)
>>> Permutation(1, 4, 5, 7, 3, 2, 6).cycle_type()
(1, 2, 4)

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:

>>> from symmetria import Permutation
...
>>> Permutation(1).domain
range(1, 2)
>>> Permutation(3, 1, 2).domain
range(1, 4)
>>> Permutation(1, 3, 4, 5, 2, 6).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:

>>> from symmetria import Cycle, CycleDecomposition, Permutation
...
>>> Permutation(1, 2, 3).equivalent(Permutation(1, 2, 3))
True
>>> Permutation(3, 1, 2).equivalent(Cycle(1, 3, 2))
True
>>> cycle_decomp = CycleDecomposition(Cycle(1, 2), Cycle(3, 4))
>>> Permutation(2, 1, 4, 3).equivalent(cycle_decomp)
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:

>>> from symmetria import Cycle, Permutation
...
>>> Permutation.from_cycle(Cycle(1))
Permutation(1)
>>> Permutation.from_cycle(Cycle(1, 2, 3))
Permutation(2, 3, 1)
>>> Permutation.from_cycle(Cycle(3))
Permutation(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:

>>> from symmetria import Cycle, CycleDecomposition, Permutation
...
>>> Permutation.from_cycle_decomposition(CycleDecomposition(Cycle(1)))
Permutation(1)
>>> Permutation.from_cycle_decomposition(CycleDecomposition(Cycle(4, 3), Cycle(1, 2)))
Permutation(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:

>>> from symmetria import Permutation
...
>>> Permutation.from_dict({1: 3, 2: 1, 3: 2})
Permutation(3, 1, 2)
>>> Permutation.from_dict({1: 5, 2: 3, 3: 1, 4: 2, 5:4})
Permutation(5, 3, 1, 2, 4)

property image: Tuple[int]

Return the image of the permutation.

For example, consider the permutation \(\sigma \in S_3\) given by \(\sigma(1)=3, \sigma(2)=1\), and \(\sigma (3)=2\), then the image of \(\sigma\) is \((3, 1, 2)\) .

Returns:

The image of the permutation.

Return type:

Tuple[int]

Example:

>>> from symmetria import Permutation
...
>>> Permutation(1, 2, 3).image
(1, 2, 3)
>>> Permutation(1, 3, 4, 2).image
(1, 3, 4, 2)
>>> Permutation(2, 3, 1, 5, 4).image
(2, 3, 1, 5, 4)

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:

>>> from symmetria import Permutation
...
>>> 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)

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

Return the inversions of the permutation.

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 permutation

Return type:

List[Tuple[int, int]]

Example:

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

is_conjugate(other: Permutation) → bool

Check if two permutations 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 (Permutation) – a permutation

Returns:

True if self and other are conjugated, False otherwise.

Return type:

bool

Raises:

TypeError – If other is not a permutation.

Example:

>>> from symmetria import Permutation
...
>>> Permutation(1, 2, 3).is_conjugate(Permutation(1, 2, 3))
True
>>> Permutation(1, 2, 3).is_conjugate(Permutation(3, 2, 1))
False
>>> Permutation(3, 2, 5, 4, 1).is_conjugate(Permutation(5, 2, 1, 4, 3))
True

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:

>>> from symmetria import Permutation
...
>>> Permutation(1).is_derangement()
False
>>> Permutation(3, 1, 2).is_derangement()
True
>>> Permutation(1, 3, 4, 5, 2, 6).is_derangement()
False

is_even() → bool

Check if the permutation 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 permutation is even, False otherwise.

Return type:

bool

Example:

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

is_odd() → bool

Check if the permutation 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 permutation is odd, False otherwise.

Return type:

bool

Example:

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

is_regular() → bool

Check if the permutation is regular.

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

Returns:

True if the permutation is regular, False otherwise.

Return type:

bool

Example:

>>> from symmetria import Permutation
...
>>> Permutation(1, 2, 3).is_regular()
True
>>> Permutation(2, 1).is_regular()
True
>>> Permutation(2, 1, 3).is_regular()
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:

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

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:

>>> from symmetria import Permutation
...
>>> Permutation(1).one_line_notation()
'1'
>>> Permutation(3, 1, 2).one_line_notation()
'312'
>>> Permutation(1, 3, 4, 5, 2, 6).one_line_notation()
'134526'

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:

>>> from symmetria import Cycle, CycleDecomposition, Permutation
...
>>> 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)]

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:

>>> from symmetria import Permutation
...
>>> Permutation(1, 2, 3).order()
1
>>> Permutation(3, 1, 2).order()
3
>>> Permutation(1, 3, 4, 5, 2, 6).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:

>>> from symmetria import Permutation
...
>>> 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:

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