polynomials_on_simplices.algebra.permutations module

Permutations module.

Operations on permutations (elements of \(S_n\)) and functions for permuting a sequence of objects. The set of permutations \(S_n\) is defined as the set of bijections from the set \(\{0, 1, \ldots, n-1\}\) (or \(\{1, 2, \ldots, n\}\)) onto itself, see https://en.wikipedia.org/wiki/Permutation and https://en.wikipedia.org/wiki/Permutation_group for an introduction.

There are two natural ways for defining how a permutation \(\sigma\) acts on a general sequence of elements \(x = (x_1, x_2, \ldots, x_n)\).

1. The value \(x_i\) is mapped to the value \(x_{\sigma(i)}\),

   \[(x_1, \ldots, x_n) \mapsto \sigma(x) = (x_{\sigma(1)}, \ldots, x_{\sigma(n)}).\]

2. The element at position i is mapped to the position \(\sigma(i)\), i.e. \(\sigma(x)_{\sigma(i)} = x_i \iff \sigma(x)_i = x_{\sigma^{-1}(i)} \iff x_i \mapsto x_{\sigma^{-1}(i)}\).

   \[(x_1, \ldots, x_n) \mapsto \sigma(x) = (x_{\sigma^{-1}(1)}, \ldots, x_{\sigma^{-1}(n)}).\]

As an example consider permutation of [‘a’, ‘b’, ‘c’, ‘d’] with the permutation

\[\begin{split}\begin{pmatrix} 1 & 2 & 3 & 4 \\ 3 & 2 & 4 & 1 \end{pmatrix}.\end{split}\]

1. will then give [‘c’, ‘b’, ‘d’, ‘a’] (x[1] (‘a’) is mapped to (replaced by) x[s(1)] = x[3] (‘c’) and so on)
2. will then give [‘d’, ‘b’, ‘a’, ‘c’] (x[1] (‘a’) is mapped to position s(1) = 3 and so on)

Obviously these two interpretations are the inverses of each other. In the code we refer to alternative 1 as permutation by value and alternative 2 as permutation by position.

Note

These two conventions for permuting a generic sequence behaves differently under composition. For alternative 1 we have

\[(\sigma \circ \pi)(x) = \pi(\sigma(x)),\]

whereas for alternative 2 we have

\[(\sigma \circ \pi)(x) = \sigma(\pi(x)).\]

class Permutation(*values)

Bases: object

A permutation (element of \(S_n\)).

This class implements the group structure of the set of n-dimensional permutations.

Composition:

\[\circ : S_n \times S_n \to S_n, (\sigma \circ \pi)(x) = \sigma(\pi(x)).\]

Inverse:

\[(\cdot)^{-1} : S_n \to S_n, \sigma^{-1}(y) = x,\]

where \(x\) is the unique element that satisfies \(\sigma(x) = y\).

Examples

>>> Permutation(4, 3, 2, 1, 0) * Permutation(1, 3, 0, 2, 4) == Permutation(3, 1, 4, 2, 0)
True
>>> Permutation(1, 4, 3, 2, 0)**(-1) == Permutation(4, 0, 3, 2, 1)
True

Parameters:values (Iterable[int]) – Sequence of the elements \(\{0, 1, \ldots, n - 1 \}\) defining the values of the permutation (e.g. \(0 \mapsto \text{ values[0]}, 1 \mapsto \text{ values[1]}, \ldots\).

index(value)

Return first index of value.

Raises ValueError if the value is not present.

to_tuple()

Permutation converted to a tuple (one-line notation).

Returns:Tuple containing the permutation values. Return type:Tuple[int]

circularly_equivalent(permutation1, permutation2)

Check if two permutations are circularly equivalent.

Check whether or not two permutations belong to the same circular equivalence class (whether or not we can reach the second permutation by successively moving the last element of the first permutation to the front).

Parameters:

• permutation1 – First permutation in one-line notation (length n tuple of the numbers 0, 1, …, n-1).
• permutation2 – Second permutation in one-line notation (length n tuple of the numbers 0, 1, …, n-1).

Returns:

True/False whether or not the permutations belong to the same equivalence class.

Examples

>>> circularly_equivalent((0, 1, 2), (2, 0, 1))
True

composition(sigma, pi)

Compute the composition of two permutations, \(\sigma \circ \pi, x \mapsto \sigma(\pi(x))\).

Parameters:

• sigma – Permutation in one-line notation (length n tuple of the numbers 0, 1, …, n-1).
• pi – Permutation in one-line notation (length n tuple of the numbers 0, 1, …, n-1).

Returns:

Composition of the two permutations, which again is a permutation in one-line notation (length n tuple of the numbers 0, 1, …, n-1).

construct_permutation(domain, codomain, n)

Construct a permutation satisfying given constraints.

Construct a length n permutation which maps the given domain into the given codomain. Let \((x_0, x_1, \ldots, x_k)\) be the given domain and \((y_0, y_1, \ldots, y_k)\) be the given codomain. Then the output permutation \(\sigma\) should satisfy \(\sigma(x_i) = y_i, i = 0, 1, \ldots, k\).

Parameters:

• domain – Domain for which the permutation is prescribed. Subset of the set {0, 1, …, n - 1}.
• codomain – Image for each element in the prescribed domain. Subset of the set {0, 1, …, n - 1}. Need to be the same length as the domain.
• n – Length of permutation.

Returns:

Permutation in one-line notation (length n tuple of the numbers 0, 1, …, n-1).

Examples

>>> construct_permutation([0, 1], [1, 0], 3)
(1, 0, 2)

construct_permutation_general(domain, codomain, by_value=True)

Construct a permutation from two general sequences of (the same) elements.

Construct a length n permutation which maps the given domain into the given codomain. Let \(x = (x_0, x_1, \ldots, x_k)\) be the given domain and \(y = (y_0, y_1, \ldots, y_k)\) be the given codomain. Then the output permutation \(\sigma\) should satisfy \(\sigma(x_i) = y_i, i = 0, 1, \ldots, k\).

Parameters:

• domain – Domain for which the permutation is prescribed.
• codomain – Image for each element in the prescribed domain. Need to be the same length as the domain.
• by_value – Whether to use the “by value” or “by position” interpretation of the permutation of an array of objects.

Returns:

Permutation in one-line notation (length n tuple of the numbers 0, 1, …, n-1).

Examples

>>> construct_permutation_general(['a', 'b', 'c', 'd'], ['d', 'b', 'a', 'c'])
(3, 1, 0, 2)
>>> construct_permutation_general(['a', 'b', 'c', 'd'], ['d', 'b', 'a', 'c'], by_value=False)
(2, 1, 3, 0)

cycle(permutation, start)

Compute a cycle of a permutation.

Parameters:

• permutation – Permutation in one-line notation (length n tuple of the numbers 0, 1, …, n-1).
• start – Permutation element to start with.

Returns:

Tuple of elements we pass until we cycle back to the start element.

Examples

>>> cycle((2, 3, 0, 1), 0)
(0, 2)
>>> cycle((2, 3, 0, 1), 1)
(1, 3)

cyclic_permutations(permutation)

Get list of all cyclic permutations equivalent to a given permutation.

Parameters:permutation – Permutation in one-line notation (length n tuple of the numbers 0, 1, …, n-1). Returns:List of tuples containing all cyclic permutations of the input permutation.

Examples

>>> cyclic_permutations((0, 1, 2))
[(0, 1, 2), (2, 0, 1), (1, 2, 0)]

from_cycle_notation(permutation, n)

Convert a permutation from cycle notation to one-line notation.

Parameters:

• permutation – Permutation in cycle notation (list of tuples fo cycles in the permutation).
• n – Length of the permutation (needed since length 1 cycles are omitted in the cycle notation).

Returns:

Permutation in one-line notation (length n tuple of the numbers 0, 1, …, n-1).

Examples

>>> from_cycle_notation([(0, 1, 4), (2, 3)], 6)
(1, 4, 3, 2, 0, 5)

from_one_based(permutation)

Convert a permutation using one based elements to zero based elements.

In Python code it’s most natural to represent \(S_n\) by the numbers \(\{0, 1, \ldots, n-1\}\), while in mathematical literature it’s standard to use the numbers \(\{1, 2, \ldots, n\}\).

Parameters:permutation – One based permutation in one-line notation (length n tuple of the numbers 1, 2, …, n-1). Returns:One based permutation in one line notation (length n tuple of the numbers 0, 1, …, n).

Examples

>>> from_one_based((1, 2, 3))
(0, 1, 2)

from_transpositions(transpositions, n)

Convert a permutation from a composition of transpositions to one-line notation.

Parameters:

• transpositions – Permutation as a composition of transpositions (length 2 cycles, applied from right to left).
• n – Length of the permutation (needed since elements mapping to themselves are not represented in the composition of transpositions).

Returns:

Permutation in one-line notation (length n tuple of the numbers 0, 1, …, n-1).

Examples

>>> from_transpositions([(0, 2), (0, 1)], 3)
(2, 0, 1)

from_two_line_notation(permutation)

Convert a permutation from two-line notation to one-line notation.

Parameters:permutation – Permutation in two line notations (two length n tuples of the numbers 0, 1, …, n-1, where the first lists the elements \(x_i\), and the second lists the image under the permutation \(\sigma(x_i)\). Returns:Permutation expressed in one-line notation (length n tuple of the numbers 0, 1, …, n-1).

Examples

>>> from_two_line_notation(((0, 2, 1, 3), (0, 2, 3, 1)))
(0, 3, 2, 1)

generate_increasing_subset_permutations(array, k)

Generate all increasing subset permutations.

Generate all permutations of any k elements of an array, where the elements appear in increasing order, based on the element order in the input array.

Parameters:

• array – Input list of elements.
• k – Number of elements to pick from the array.

Returns:

Generator generating all permutations of subsets of k increasing elements from the input array.

generate_random_increasing_subset_permutation(n, k)

Generate random increasing subset permutation.

Generate a random length k permutation of the elements 0, 1, …, n-1 where the elements appear in increasing order.

Parameters:

• n – Number of elements to pick from.
• k – Length of permutation.

Returns:

Permutation in one-line notation (length k tuple of increasing numbers from the set 0, 1, …, n-1).

generate_random_permutation(n)

Generate a random length n permutation (element of \(S_n\)).

Parameters:n – Length of permutation. Returns:Permutation in one-line notation (length n tuple of the numbers 0, 1, …, n-1).

generate_random_subset_permutation(n, k)

Generate a random length k permutation of the elements 0, 1, …, n-1.

Parameters:

• n – Number of elements to pick from.
• k – Length of permutation.

Returns:

Permutation in one-line notation (length k tuple of the numbers 0, 1, …, n-1).

generate_subset_permutations(array, k)

Generate all permutations of any k elements of an array.

Parameters:

• array – Input list of elements.
• k – Number of elements to pick from the array.

Returns:

Generator generating all permutations of subsets of k elements from the input array.

identity(n)

Get the identity permutation in \(S_n\).

Parameters:n – Length of the permutation. Returns:Identity permutation.

Examples

>>> identity(3)
(0, 1, 2)

increasing_subset_permutations(n, k)

Get increasing subset permutations.

Get a list of all permutations of any k elements of the elements 0, 1, …, n-1, where the elements appear in increasing order.

Parameters:

• n – Number of total elements.
• k – Number of elements to pick.

Returns:

List of tuples containing all permutations of subsets of k increasing elements from the elements 0, 1, …, n-1.

Examples

>>> increasing_subset_permutations(3, 2)
[(0, 1), (0, 2), (1, 2)]

inverse(permutation)

Compute the inverse of a permutation.

Parameters:permutation – Permutation in one-line notation (length n tuple of the numbers 0, 1, …, n-1). Returns:Inverse permutation in one line notation (length n tuple of the numbers 0, 1, …, n-1).

Examples

>>> inverse((1, 4, 3, 2, 0))
(4, 0, 3, 2, 1)

num_fixed_points(permutation)

Compute the number of fixed points (elements mapping to themselves) of a permutation.

Parameters:permutation – Permutation in one-line notation (length n tuple of the numbers 0, 1, …, n-1). Returns:Number of fixed points in the permutation.

Examples

>>> num_fixed_points((0, 2, 1))
1

num_increasing_subset_permutations(n, k)

Get the number of permutations of any k elements of the elements 0, 1, …, n - 1, where the elements appear in increasing order.

This is given by \(\binom{n}{k} = \frac{n!}{k! (n - k)!}\).

Parameters:

• n – Number of total elements.
• k – Number of elements to pick.

Returns:

Number of length k permutations of n elements.

Return type:

int

num_permutations(n)

Get the number of length n permutations, n! (number of permutations of n elements = number of elements in \(S_n\)).

Parameters:n – Length of permutations. Returns:Number of length n permutations. Return type:int

num_subset_permutations(n, k)

Get the number of permutations of any k elements of the elements 0, 1, …, n - 1.

This is given by \(\frac{n!}{(n - k)!}\)

Parameters:

• n – Number of total elements.
• k – Number of elements to pick.

Returns:

Number of length k permutations of n elements.

Return type:

int

permutation_matrix_positions(permutation)

Compute permutation matrix for permutation by position.

Compute the permutation matrix which when multiplied with a column vector permutes the position of the elements in the vector according to the given permutation.

Parameters:permutation – Permutation in one-line notation (length n tuple of the numbers 0, 1, …, n-1). Returns:n by n permutation matrix (orthogonal matrix containing a single 1 in each row and column). Return type:Numpy array

Examples

>>> permutation_matrix_positions((0, 3, 1, 4, 2))
array([[1, 0, 0, 0, 0],
       [0, 0, 1, 0, 0],
       [0, 0, 0, 0, 1],
       [0, 1, 0, 0, 0],
       [0, 0, 0, 1, 0]])

permutation_matrix_values(permutation)

Compute permutation matrix for permutation by value.

Compute the permutation matrix which when multiplied with a column vector permutes the values of the vector according to the given permutation.

Parameters:permutation – Permutation in one-line notation (length n tuple of the numbers 0, 1, …, n-1). Returns:n by n permutation matrix (orthogonal matrix containing a single 1 in each row and column). Return type:Numpy array

Examples

>>> permutation_matrix_values((0, 3, 1, 4, 2))
array([[1, 0, 0, 0, 0],
       [0, 0, 0, 1, 0],
       [0, 1, 0, 0, 0],
       [0, 0, 0, 0, 1],
       [0, 0, 1, 0, 0]])

permutations(n)

Get a list of all permutations of length n (elements of \(S_n\)).

Parameters:n – Length of permutations. Returns:List of tuples containing all permutations of the elements 0, 1, …, n-1.

Examples

>>> permutations(3)
[(0, 1, 2), (0, 2, 1), (1, 0, 2), (1, 2, 0), (2, 0, 1), (2, 1, 0)]

permute_positions(permutation, sequence)

Permute the elements of a sequence with a specified permutation.

The permutation specifies what position each element in the input sequence is mapped to in the permuted sequence. Mathematically we have: \(\sigma((x_0, x_1, \ldots, x_n)) = (x_{\sigma^{-1}(0)}, x_{\sigma^{-1}(1)}, \ldots, x_{\sigma^{-1}(n-1)})\).

Parameters:

• permutation – Permutation in one-line notation (length n tuple of the numbers 0, 1, …, n-1).
• sequence – Sequence of elements we wish to permute.

Returns:

The permuted sequence.

Examples

>>> permute_positions((2, 0, 1), ['a', 'b', 'c'])
['b', 'c', 'a']

permute_values(permutation, sequence)

Permute the elements of a sequence with a specified permutation.

The permutation specifies how each element of the input sequence maps into another element of the input sequence. Mathematically we have: \(\sigma((x_0, x_1, \ldots, x_{n-1})) = (x_{\sigma(0)}, x_{\sigma(1)}, \ldots, x_{\sigma(n-1)})\).

Parameters:

• permutation – Permutation in one-line notation (length n tuple of the numbers 0, 1, …, n-1).
• sequence – Sequence of elements we wish to permute.

Returns:

The permuted sequence.

Examples

>>> permute_values((2, 0, 1), ['a', 'b', 'c'])
['c', 'a', 'b']

sign(permutation)

Compute the sign of a permutation.

Parameters:permutation – Permutation in one-line notation (length n tuple of the numbers 0, 1, …, n-1). Returns:Sign of the permutation.

Examples

>>> sign((0, 1, 2))
1
>>> sign((0, 2, 1))
-1

subset_permutations(n, k)

Get a list of all permutations of any k elements of the elements 0, 1, …, n-1.

Parameters:

• n – Number of total elements.
• k – Number of elements to pick.

Returns:

List of tuples containing all permutations of subsets of k elements from the elements 0, 1, …, n-1.

Examples

>>> subset_permutations(3, 2)
[(0, 1), (0, 2), (1, 0), (1, 2), (2, 0), (2, 1)]

swap(permutation, transposition)

Swap image of two elements in a permutation (apply a transposition to the permutation).

Let \(\sigma\) be the input permutation, \(i, j\) be the elements of the transposition, and \(\pi\) be the output permutation after the applied transposition. Then we have \(\pi(i) = \sigma(j), \pi(j) = \sigma(i), \pi(k) = \sigma(k), k \neq i, j\).

Parameters:

• permutation – Permutation in one-line notation (length n tuple of the numbers 0, 1, …, n-1).
• transposition – Tuple of two elements that should be switched in the permutation.

Returns:

Permutation after the applied transposition in one line notation (length n tuple of the numbers 0, 1, …, n-1).

Examples

>>> swap((0, 1, 2, 3), (1, 3))
(0, 3, 2, 1)
>>> swap((0, 3, 2, 1), (2, 3))
(0, 3, 1, 2)

to_cycle_notation(permutation)

Convert a permutation from one-line notation to cycle notation.

Parameters:permutation – Permutation in one-line notation (length n tuple of the numbers 0, 1, …, n-1). Returns:Permutation in cycle notation (list of tuples of cycles in the permutation).

Examples

>>> to_cycle_notation((1, 4, 3, 2, 0))
[(0, 1, 4), (2, 3)]

to_one_based(permutation)

Convert a permutation using zero based elements to one based elements.

In Python code it’s most natural to represent \(S_n\) by the numbers \(\{0, 1, \ldots, n-1\}\), while in mathematical literature it’s standard to use the numbers \(\{1, 2, \ldots, n\}\).

Parameters:permutation – Zero based permutation in one-line notation (length n tuple of the numbers 0, 1, …, n-1). Returns:One based permutation in one line notation (length n tuple of the numbers 1, 2, …, n).

Examples

>>> to_one_based((0, 1, 2))
(1, 2, 3)

to_transpositions(permutation)

Convert a permutation from one-line notation to a composition of transpositions.

Parameters:permutation – Permutation in one-line notation (length n tuple of the numbers 0, 1, …, n-1). Returns:Permutation as a composition of transpositions (length 2 cycles, applied from right to left).

Examples

>>> to_transpositions((2, 0, 1))
[(0, 2), (0, 1)]

to_two_line_notation(permutation)

Convert a permutation from one-line notation to two line notation.

Parameters:permutation – Permutation in one-line notation (length n tuple of the numbers 0, 1, …, n-1). Returns:Permutation expressed in two line notations (two length n tuples of the numbers 0, 1, …, n-1, where the first lists the elements \(x_i\), and the second lists the image under the permutation \(\sigma(x_i)\).

Examples

>>> to_two_line_notation((0, 3, 2, 1))
((0, 1, 2, 3), (0, 3, 2, 1))