# 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 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. The inverse permutation tuple 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 A list of disjoint cycles, that when comb list 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 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 list of tuples 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)] permutation image tuple s = t [+] u [+] ... [+] z 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 permutation image tuple of the composition. 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 permutation image tuple of the concatenation. 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 The permuted sequence [l_sigma(1), l_sigma(2), ..., l_sigma(n)] 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 A single permutation for all channels of all blocks. 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 (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 tuple