qnet.utils.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() Compute the concatenation of permutations
permutation_from_disjoint_cycles	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
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.utils.permutations.BadPermutationError

Bases: ValueError

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

qnet.utils.permutations.check_permutation(permutation)

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.utils.permutations.invert_permutation(permutation)

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.utils.permutations.permutation_to_disjoint_cycles(permutation)

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.utils.permutations.permutation_from_disjoint_cycles(cycles, offset=0)

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.utils.permutations.permutation_to_block_permutations(permutation)

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.utils.permutations.permutation_from_block_permutations(permutations)

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.utils.permutations.compose_permutations(alpha, beta)

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.utils.permutations.concatenate_permutations(a, b)

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.utils.permutations.permute(sequence, permutation)

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.utils.permutations.full_block_perm(block_permutation, block_structure)

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.utils.permutations.block_perm_and_perms_within_blocks(permutation, block_structure)

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