qnet.algebra.permutations module

Summary

Exceptions:

BadPermutationError Can be raised to signal that a permutation does not pass the :py:func:check_permutation test.

Functions:

block_perm_and_perms_within_blocks Decompose a permutation into a block permutation and into permutations acting within each block.
check_permutation Verify that a tuple of permutation image points (sigma(1), sigma(2), ..., sigma(n)) is a valid permutation, i.e.
compose_permutations Find the composite permutation
concatenate_permutations Concatenate two permutations:
full_block_perm Extend a permutation of blocks to a permutation for the internal signals of all blocks.
invert_permutation Compute the image tuple of the inverse permutation.
permutation_from_block_permutations Reverse operation to permutation_to_block_permutations()
permutation_from_disjoint_cycles Reconstruct a permutation image tuple from a list of disjoint cycles
permutation_to_block_permutations If possible, decompose a permutation into a sequence of permutations each acting on individual ranges of the full range of indices.
permutation_to_disjoint_cycles Any permutation sigma can be represented as a product of cycles.
permute Apply a permutation sigma({j}) to an arbitrary sequence.

Reference

exception qnet.algebra.permutations.BadPermutationError[source]

Bases: ValueError

Can be raised to signal that a permutation does not pass the :py:func:check_permutation test.

qnet.algebra.permutations.check_permutation(permutation)[source]

Verify that a tuple of permutation image points (sigma(1), sigma(2), ..., sigma(n)) is a valid permutation, i.e. each number from 0 and n-1 occurs exactly once. I.e. the following set-equality must hold:

{sigma(1), sigma(2), ..., sigma(n)} == {0, 1, 2, ... n-1}
Parameters:permutation (tuple) – Tuple of permutation image points
Return type:bool
qnet.algebra.permutations.invert_permutation(permutation)[source]

Compute the image tuple of the inverse permutation.

Parameters:permutation – A valid (cf. :py:func:check_permutation) permutation.
Returns:The inverse permutation tuple
Return type:tuple
qnet.algebra.permutations.permutation_to_disjoint_cycles(permutation)[source]

Any permutation sigma can be represented as a product of cycles. A cycle (c_1, .. c_n) is a closed sequence of indices such that

sigma(c_1) == c_2, sigma(c_2) == sigma^2(c_1)== c_3, …, sigma(c_(n-1)) == c_n, sigma(c_n) == c_1

Any single length-n cycle admits n equivalent representations in correspondence with which element one defines as c_1.

(0,1,2) == (1,2,0) == (2,0,1)

A decomposition into disjoint cycles can be made unique, by requiring that the cycles are sorted by their smallest element, which is also the left-most element of each cycle. Note that permutations generated by disjoint cycles commute. E.g.,

(1, 0, 3, 2) == ((1,0),(3,2)) –> ((0,1),(2,3)) normal form
Parameters:permutation (tuple) – A valid permutation image tuple
Returns:A list of disjoint cycles, that when comb
Return type:list
Raise:BadPermutationError
qnet.algebra.permutations.permutation_from_disjoint_cycles(cycles, offset=0)[source]

Reconstruct a permutation image tuple from a list of disjoint cycles :param cycles: sequence of disjoint cycles :type cycles: list or tuple :param offset: Offset to subtract from the resulting permutation image points :type offset: int :return: permutation image tuple :rtype: tuple

qnet.algebra.permutations.permutation_to_block_permutations(permutation)[source]

If possible, decompose a permutation into a sequence of permutations each acting on individual ranges of the full range of indices. E.g.

(1,2,0,3,5,4) --> (1,2,0) [+] (0,2,1)
Parameters:permutation (tuple) – A valid permutation image tuple s = (s_0,...s_n) with n > 0
Returns:A list of permutation tuples [t = (t_0,...,t_n1), u = (u_0,...,u_n2),..., z = (z_0,...,z_nm)] such that s = t [+] u [+] ... [+] z
Return type:list of tuples
Raise:ValueError
qnet.algebra.permutations.permutation_from_block_permutations(permutations)[source]

Reverse operation to permutation_to_block_permutations() Compute the concatenation of permutations

(1,2,0) [+] (0,2,1) --> (1,2,0,3,5,4)
Parameters:permutations (list of tuples) – A list of permutation tuples [t = (t_0,...,t_n1), u = (u_0,...,u_n2),..., z = (z_0,...,z_nm)]
Returns:permutation image tuple s = t [+] u [+] ... [+] z
Return type:tuple
qnet.algebra.permutations.compose_permutations(alpha, beta)[source]

Find the composite permutation

\[\begin{split}\sigma := \alpha \cdot \beta \\ \Leftrightarrow \sigma(j) = \alpha\left(\beta(j)\right) \\\end{split}\]
Parameters:
  • a – first permutation image tuple
  • beta (tuple) – second permutation image tuple
Returns:

permutation image tuple of the composition.

Return type:

tuple

qnet.algebra.permutations.concatenate_permutations(a, b)[source]
Concatenate two permutations:
s = a [+] b
Parameters:
  • a (tuple) – first permutation image tuple
  • b (tuple) – second permutation image tuple
Returns:

permutation image tuple of the concatenation.

Return type:

tuple

qnet.algebra.permutations.permute(sequence, permutation)[source]

Apply a permutation sigma({j}) to an arbitrary sequence.

Parameters:
  • sequence – Any finite length sequence [l_1,l_2,...l_n]. If it is a list, tuple or str, the return type will be the same.
  • permutation (tuple) – permutation image tuple
Returns:

The permuted sequence [l_sigma(1), l_sigma(2), ..., l_sigma(n)]

Raise:

BadPermutationError or ValueError

qnet.algebra.permutations.full_block_perm(block_permutation, block_structure)[source]

Extend a permutation of blocks to a permutation for the internal signals of all blocks. E.g., say we have two blocks of sizes (‘block structure’) (2, 3), then a block permutation that switches the blocks would be given by the image tuple (1,0). However, to get a permutation of all 2+3 = 5 channels that realizes that block permutation we would need (2, 3, 4, 0, 1)

Parameters:
  • block_permutation (tuple) – permutation image tuple of block indices
  • block_structure (tuple) – The block channel dimensions, block structure
Returns:

A single permutation for all channels of all blocks.

Return type:

tuple

qnet.algebra.permutations.block_perm_and_perms_within_blocks(permutation, block_structure)[source]

Decompose a permutation into a block permutation and into permutations acting within each block.

Parameters:
  • permutation (tuple) – The overall permutation to be factored.
  • block_structure (tuple) – The channel dimensions of the blocks
Returns:

(block_permutation, permutations_within_blocks) Where block_permutations is an image tuple for a permutation of the block indices and permutations_within_blocks is a list of image tuples for the permutations of the channels within each block

Return type:

tuple