core.helper_operations package

Submodules

core.helper_operations.cycle_cover_connections module

core.helper_operations.cycle_cover_connections.get_tail_length(sig)

Get the length of the tail to cut the cycle cover on.

Parameters:

sig (tuple[int, ...]) – The signature of the permutation.

Returns:

The length of the tail.

Return type:

int

Raises:

ValueError – If the signature is not all-even or all-but-one-even.

core.helper_operations.cycle_cover_connections.generate_end_tuple_order(sig)

Generates the order of the end tuples of the cycles in the cycle cover. The end tuples are the tails of the cycles that are the nodes that connect them. They are cycles are ordered by their end tuples:

• All-even: _00, _01/_10, _11, _12/_21, _22, , …

• All-but-one-even: _0, _1, _2, _3, _4, _5, …

Parameters:

sig (tuple[int, ...]) – The signature of the permutation.

Returns:

The order of the end tuples of the cycles in the cycle. These orders are as follows:

• All-even: _100, _101, _211, _212, …

The last tuple is of length 2. That is, the number of colors in the signature followed by the number of colors in the signature - 1.

The first element is the change in the end tuple compared to the previous end tuple.

• All-but-one-even: _10, _21, _32, _43, _54, _65, …, 0S

The last tuple starts with 0 and then S; the number of colors in the signature.

The first element is the change in the end tuple compared to the previous end tuple.

Return type:

list[tuple[int, …]]

Raises:

• ValueError – If there is more than one change in consecutive end tuples.

• ValueError – If the signature is not all-even or all-but-one-even.

core.helper_operations.cycle_cover_connections.get_two_odd_rest_even_cycle(single_cycle_cover, end_tuple_order, cross_edges, sig)

Generate the Hamiltonian cycle for a signature with two odd and the rest even occurring colors Combines all the three odd signatures with a trailing even element to the first cycle with an odd trailing element. :type single_cycle_cover: list[list[tuple[int, ...]]] :param single_cycle_cover: The single cycle cover to connect. :type single_cycle_cover: list[list[tuple[int, …]]] :type end_tuple_order: list[tuple[int, ...]] :param end_tuple_order: The order of the last elements of the cycles. :type end_tuple_order: list[tuple[int, …]] :type cross_edges: dict[tuple[tuple[int, ...], tuple[int, ...]], list[tuple[tuple[int, ...], tuple[int, ...]]]] :param cross_edges: The cross edges to add to. :type cross_edges: dict[tuple[tuple[int, …], tuple[int, …]], list[tuple[tuple[int, …], tuple[int, …]]]] :type sig: tuple[int, ...] :param sig: The signature of the permutation. :type sig: tuple[int, …]

Returns:

The connected cycle cover as a list of tuples, where each tuple represents a permutation.

Return type:

list[tuple[int, …]]

core.helper_operations.cycle_cover_connections.get_cross_edges(sig, end_tuple_order)

Get the cross edges for a single cycle cover based on the end tuple order.

Parameters:

• sig (tuple[int, ...]) – The signature of the permutation.

• end_tuple_order (list[tuple[int, ...]]) – The order of the last elements of the cycles.

Returns:

A list of cross edges, where each edge is represented as a tuple of tuples.

Return type:

list[tuple[int, …]]

core.helper_operations.cycle_cover_connections.connect_single_cycle_cover(single_cycle_cover, end_tuple_order, naive_glue=False)

Connect a single list of cycles to form a Hamiltonian cycle on the non-stutter permutations of a neighbor-swap graph.

Parameters:

• single_cycle_cover (list[tuple[int, ...]]) – The single cycle cover to connect.

• end_tuple_order (list[tuple[int, ...]]) – The order of the last elements of the cycles.

• naive_glue (bool, optional) – Naively glue the disjoint cycle cover. Defaults to False.

Returns:

The connected cycle cover as a list of tuples, where each tuple represents a permutation.

The last element of the last tuple is the first element of the first tuple.

Return type:

list[tuple[int, …]]

core.helper_operations.cycle_cover_cross_edges module

core.helper_operations.cycle_cover_cross_edges.get_all_even_cross_edges(end_tuple_order, cross_edges, sig)

Get all cross edges for a signature with all even occurring colors

Parameters:

• end_tuple_order (list[tuple[int, ...]]) – The order of the end tuples of the cycles in the cycle cover.

• cross_edges (dict[tuple[tuple[int, ...], tuple[int, ...]], list[tuple[tuple[int, ...], tuple[int, ...]]]]) – The cross edges to add to.

• sig (tuple[int, ...]) – The signature of the permutation.

Returns:

The cross edges with all even occurring colors

Return type:

dict[tuple[tuple[int, …], tuple[int, …]], list[tuple[tuple[int, …], tuple[int, …]]]]

core.helper_operations.cycle_cover_cross_edges.generate_one_odd_cross_edges(end_tuple_order, cross_edges, sig)

Get all cross edges for a signature with one odd and the rest even occurring colors

Parameters:

• end_tuple_order (list[tuple[int, ...]]) – The order of the end tuples of the cycles in the cycle cover.

• cross_edges (dict[tuple[tuple[int, ...], tuple[int, ...]], list[tuple[tuple[int, ...], tuple[int, ...]]]]) – The cross edges to add to.

• sig (tuple[int, ...]) – The signature of the permutation.

Returns:

The cross edges with one odd - rest even occurring colors

Return type:

dict[tuple[tuple[int, …], tuple[int, …]], list[tuple[tuple[int, …], tuple[int, …]]]]

core.helper_operations.cycle_cover_cross_edges.generate_two_odd_cross_edges(end_tuple_order, cross_edges, sig)

Get all cross edges for a signature with two odd and the rest even occurring colors

Parameters:

• end_tuple_order (list[tuple[int, ...]]) – The order of the end tuples of the cycles in the cycle cover.

• cross_edges (dict[tuple[tuple[int, ...], tuple[int, ...]], list[tuple[tuple[int, ...], tuple[int, ...]]]]) – The cross edges to add to.

• sig (tuple[int, ...]) – The signature of the permutation.

Returns:

The cross edges with two odd - rest even occurring colors

Return type:

dict[tuple[tuple[int, …], tuple[int, …]], list[tuple[tuple[int, …], tuple[int, …]]]]

core.helper_operations.cycle_cover_generation module

core.helper_operations.cycle_cover_generation.parallel_sub_cycle_odd_2_1(k)

Generates the parallel cycle from the 02 and 20 cycles with stutters. Uses the createZigZagPath and incorporateSpursInZigZag functions.

Parameters:

• k (int) – The input value for k, the number of 0’s

• 20 (This must be even because we don't count the zero in the trailing 02 /)

Returns:

The generated path from 0 1 0^{k-1} 1 0 2 to 1 0^(k) 1 0 2

Return type:

list[tuple[int, …]]

Raises:

ValueError – If k is odd

core.helper_operations.cycle_cover_generation.incorporated_odd_2_1_path_a_b(k)

Generates a path based on the number of 0’s k from a = 1 2 0^{k0} 1 to b = 0 2 1 0^{k0-1} 1. Including the _02 and _20 cycles (with stutters), and the _1 & _12 path. First generates the a_b_path, then the parallel cycles, and then splits the a_b_path in 2 at the parallel edge. The cross edges are:

• From 0 1 0^{k-1} 1 0 2 to 0 1 0^{k0-1} 1 2

• From 1 0^k 1 0 2 to 1 0^(k) 1 0 2.

Parameters:

k (int) – The input value the number of 0s. Must be odd!

Returns:

The generated path from a to b

• a = 1 2 0^{k0} 1

• b = 0 2 1 0^{k0-1} 1

Return type:

list[tuple[int, …]]

core.helper_operations.cycle_cover_generation.incorporated_odd_2_1_cycle(k, flip_stutter_cross_edge=False)

Generates a path based on the number of 0’s k from e = 1 0 2 0^{k0-1} 1 to f = 0 1 2 0^{k0-1} 1. Including the _02 and _20 cycles (with stutters), and the _1 & _12 path. First generates the a_b_path, then the parallel cycles, and then splits the a_b_path in 2 at the parallel edge. The cross edges are:

• From 0 1 0^{k-1} 1 0 2 to 0 1 0^{k0-1} 1 2

• From 1 0^k 1 0 2 to 1 0^(k) 1 0 2.

Parameters:

• k (int) – The input value the number of 0s. Must be odd!

• flip_stutter_cross_edge (bool, optional) – If the cross edge should be flipped. Defaults to False; 0^{k-1} 1 0 2 to 0^{k0-1} 1 2.

Returns:

The generated path from a to b

• e = 1 0 2 0^{k0-1} 1

• f = 0 1 2 0^{k0-1} 1

Return type:

list[tuple[int, …]]

core.helper_operations.cycle_cover_generation.waveTopRowOddOddOne(even_odd_1, odd_odd_two_equal)

Connects the even-odd-1 and odd-odd-xx cycles by incorporating the spurs in the zig-zag path. This is the top figure of Figure 2.9 of the master thesis document (figure: VerhoeffOdd21);

Parameters:

• even_odd_1 (list[tuple[int, ...]]) – The even-odd-1 cycle.

• odd_odd_two_equal (list[tuple[int, ...]]) – The odd-odd-xx cycle.

Returns:

The connected cycle.

Return type:

list[tuple[int, …]]

Raises:

• AssertionError – If the cycle is not a cycle.

• ValueError – If the adjacent nodes are not found in the even-odd-1 cycle.

core.helper_operations.naive_parallel_edges module

core.helper_operations.naive_parallel_edges.find_end_tuple_order(cycle_cover, force_three=False)

Find the connecting end tuples in the order of the cycle cover. The end tuples are the tails of the cycles that are the nodes that connect them. The length of the end tuples is at most 3 but they can vary between end tuples.

Parameters:

• cycle_cover (list[list[tuple[int, ...]]]) – The cycle cover to find the end tuples for.

• force_three (bool, optional) – If the end tuples should be of length 3. Defaults to False.

Returns:

The order of the end tuples of the cycles in the cycle cover.

Return type:

list[tuple[int, …]]

Raises:

• ValueError – If the cycle cover does not have connecting tails of length at most 3.

• ValueError – If the cycle cover depth is more than 1.

core.helper_operations.naive_parallel_edges.filter_adjacent_edges_by_tail(cycle, tail)

From a cycle, get all the edges (i.e. the pairs of consecutive permutations). Then filter those edges such that both nodes have the specified tail.

Parameters:

• cycle (list[tuple[int, ...]]) – The cycle to filter.

• tail (tuple[int, ...]) – The tail that the nodes should have.

Returns:

The edges that have the specified tail.

Return type:

list[tuple[tuple[int, …], tuple[int, …]]]

core.helper_operations.naive_parallel_edges.find_parallel_edges_in_cycle_cover(cycle_cover, end_tuple_order)

Find parallel edges in the cycle cover. These edges are pairs of nodes in the cycle cover that have a tail that connects them to the next cycle. The tail is defined by the number of odd colors in the signature.

Parameters:

• cycle_cover (list[tuple[int, ...]]) – The cycle cover to find parallel edges in.

• end_tuple_order (list[tuple[int, ...]]) – The order of the end tuples of the cycles in the cycle cover.

Returns:

A dictionary where the key is the pair of tails of the cycle that are combined and the value is the list of parallel edges. Each parallel edge is a tuple of two tuples of permutations (a permutation is a tuple of integers).

Return type:

dict[list[tuple[tuple[int, …], tuple[int, …]]]]

core.helper_operations.naive_parallel_edges.find_cross_edges(cycle_cover, end_tuple_order, return_first=False)

Find the cross edges in the cycle cover. These are pairs of parallel edges between cycles that are adjacent. The cross edges are used to connect the cycles in the cycle cover.

Parameters:

• cycle_cover (list[list[tuple[int, ...]]]) – The cycle cover to find cross edges in.

• end_tuple_order (list[tuple[int, ...]]) – The order of the end tuples of the cycles in the cycle cover.

• return_first (bool, optional) – If only the first cross edge should be returned. Defaults to False.

Returns:

A dictionary where the key is a pair of tails of the cycle that are combined and the value is the list of cross edges. Each cross edge is a tuple of two tuples of permutations (a permutation is a tuple of integers).

Return type:

dict[tuple[int, …], list[tuple[tuple[tuple[int, …], tuple[int, …]], tuple[tuple[int, …], tuple[int, …]]]]]

Raises:

ValueError – If the cycle cover is empty.

core.helper_operations.naive_parallel_edges.write_cross_edge_ratio_to_file(cross_edges, tail1, tail2, prompt_keep_old_csv=False)

Writes the cross edge ratio to a csv file; ./crossedges.csv. If the file doesn’t exist, it creates it.

Parameters:

• cross_edges (dict[tuple[int, ...], list[tuple[tuple[tuple[int, ...], tuple[int, ...]], tuple[tuple[int, ...], tuple[int, ...]]]]]) – The cross edges to write to the file.

• tail1 (tuple[int, ...]) – The first tail of the cross edge.

• tail2 (tuple[int, ...]) – The second tail of the cross edge.

• prompt_keep_old_csv (bool, optional) – If the user should be prompted to keep the old csv file. Defaults to False.

Return type:

None

Returns:

None

Raises:

ValueError – If the cross edge is not found in the cross edges dictionary.

core.helper_operations.path_operations module

core.helper_operations.path_operations.adjacent(s, t)

Check if two tuples are adjacent. They are adjacent if they differ by a swap of two adjacent elements.

Parameters:

• s (tuple[int, ...]) – The first tuple.

• t (tuple[int, ...]) – The second tuple.

Returns:

True if the tuples are adjacent, False otherwise.

Return type:

bool

core.helper_operations.path_operations.pathQ(p, verbose=True)

Checks if the given list of vertices represents a path. So True if all vertices are adjacent, False otherwise.

Parameters:

• p (list[tuple[int, ...]]) – List of permutations (vertices). The order of the vertices is checked.

• verbose (bool, optional) – Whether the error in the path should be printed in console. Defaults to True.

Returns:

True if p is a path, False otherwise.

Return type:

bool

core.helper_operations.path_operations.cycleQ(c)

Checks if a list of tuples represents a cycle. The list represents a cycle if all vertices are adjacent and the first and last vertices are adjacent.

Parameters:

c (list[tuple[int, ...]]) – A list of tuples representing a cycle.

Returns:

True if the list represents a cycle, False otherwise.

Return type:

bool

core.helper_operations.path_operations.pathEdges(p)

Returns a list of edges of a path. T

Parameters:

p (list[tuple[int, ...]]) – The path represented as a list of adjacent vertices.

Returns:

A list of edges, where each edge is represented as a tuple of two adjacent vertices.

Return type:

list[tuple[tuple[int, …], tuple[int, …]]]

Raises:

ValueError – If the given list of vertices does not represent a path.

core.helper_operations.path_operations.splitPathIn2(p, a)

Splits a path in two parts at vertex a. Element a appears in only the first path.

Parameters:

• p (list[tuple[int, ...]]) – The path to be split.

• a (tuple[int, ...]) – The vertex at which to split the path.

Returns:

A tuple containing two lists representing the split paths.

• The first list contains the vertices from the start of the original path up to and including vertex a.

• The second list contains the vertices from vertex a+1 to the end of the original path.

Return type:

tuple[list[tuple[int, …]], list[tuple[int, …]]]

Raises:

• AssertionError – If the length of the path is less than or equal to 1.

• AssertionError – If the vertex a is not present in the path.

• AssertionError – If the list p does not represent a path.

core.helper_operations.path_operations.cutCycle(c, a)

Splits a cycle at vertex a and rotates it such that vertex a apprears first in the returned path.

Parameters:

• c (list[tuple[int, ...]]) – The cycle to be split. Can also be a numpy array.

• a (tuple[int, ...]) – The vertex at which to split the cycle. Must be present in the cycle.

Returns:

The cycle c but rotated such that vertex a appears first.

Return type:

list[tuple[int, …]]

Raises:

• AssertionError – If the vertex a is not present in the cycle c.

• ValueError – If the vertex a is not present in the numpy cycle c (if c is a numpy array).

core.helper_operations.path_operations.spurBaseIndex(path, vertex)

Determines the index of the base of the spur for a given path and spur tip.

Parameters:

• path (list[tuple[int, ...]]) – The path to search for the base of the spur.

• vertex (tuple[int, ...]) – The spur tip vertex.

Returns:

The index of the base of the spur.

Return type:

int

Raises:

ValueError – If no vertex adjacent to vertex is found in the path.

core.helper_operations.path_operations.find_last_distinct_adjacent_index(perm)

Find the last pair of distinct adjacent elements in a permutaiton (tuple).

Parameters:

perm (tuple[int, ...]) – Permutation as a tuple of integers.

Returns:

The index of the first element in the last pair of distinct adjacent

Return type:

int

Raises:

ValueError – If no distinct adjacent elements are found in the permutation.

core.helper_operations.path_operations.find_first_distinct_adjacent_index(perm)

Find the first pair of distinct adjacent elements in a permutaiton (tuple).

Parameters:

perm (tuple[int, ...]) – Permutation as a tuple of integers.

Returns:

The index of the first element in the first pair of distinct adjacent

Return type:

int

Raises:

ValueError – If no distinct adjacent elements are found in the permutation.

core.helper_operations.path_operations.mul(sez, e)

Adds ‘e’ to all elements (tuples) in the list sez.

Parameters:

• sez (list[tuple[int, ...]]) – The list of tuples to be modified.

• e (int) – The value to be appended to each element in sez.

Returns:

The modified list with ‘e’ added to each element.

Return type:

list[tuple[int, …]]

core.helper_operations.path_operations.createZigZagPath(p, u, v)

Create a zigzag path by combining two “parallel” copies of a given path. The zig zag path runs from p[0]u to p[-1]u. Obtained by appending u and v to each vertex in the path. Then for the following vertex in the path, append v and u to it. Then u and v, again v and u and so on.

Parameters:

• p (list[tuple[int, ...]]) – Path as a list of tuples.

• u (tuple[int, ...]) – Tuple to append.

• v (tuple[int, ...]) – Tuple to append.

Returns:

Path obtained by combining two “parallel” copies of the given path p.

Return type:

list[tuple[int, …]]

Raises:

• AssertionError – If the path p is not a path.

• AssertionError – If the length of the path is less than 1.

• AssertionError – If the vertices u and v are not adjacent.

core.helper_operations.path_operations.incorporateSpurInZigZag(path, vertex_pair)

Incorporates a spur in a zigzag path. A spur consists of two vertices, both ending with two trailing elements that are the same as in the zigzag path. The spur is incorporated by finding the base of the spur in the zigzag path, i.e. the vertex adjacent to the spur tip which is in the “zig” part. Then the spur is inserted in the path at that index. Then the path continues with the “zag” part.

Parameters:

• path (list[tuple[int, ...]]) – List of vertices, a zigzag path.

• vertex_pair (tuple[tuple[int, ...], tuple[int, ...]]) – A pair of vertices to incorporate. The pair consists of two vertices, both ending with two trailing elements that are the same as in the zigzag path. The parts prior to the trailing elements are stutters.

Returns:

List of vertices, the zigzag path with the spur incorporated.

Return type:

list[tuple[int, …]]

core.helper_operations.path_operations.createSquareTube(path, u, v)

Creates a square tube from a path by appending combinations of u and v like so:

• The first vertices with uu, uv, vv, vu, vu, vv, uv, uu

• Only the last one with uu, uv, vv, vu, vu, uu, uv, vv

Every vertex in the original path is repeated 4 times. Once for each combination of u and v above.

Parameters:

• path (list[tuple]) – List of vertices, a path.

• u (tuple) – Tuple to append.

• v (tuple) – Tuple adjacent to u to append.

Returns:

List of vertices, the square tube. Every vertex in the original path is repeated 4 times.

Return type:

list[tuple[int, …]]

core.helper_operations.path_operations.get_transformer(s, func)

Sorts the signature using a given function and provides array to transform it back. The transformer array is built by indexing the numbers. See transform for more details on the format.

Parameters:

• s (tuple[int, ...]) – The signature as a tuple of integers.

• func (callable) – The lambda function of tuples of form (value, index) to sort the signature.

Returns:

A tuple of a tuple and a list of integers: - the first is a tuple: the sorted signature. - the second is a list: the transformation array (used in the tranform function).

Return type:

tuple[tuple[int, …], list[int]]

core.helper_operations.path_operations.transformer_to_sorted(unsorted_signature, func=<function <lambda>>)

Get the transformer to go from unsorted to sorted signature. Works using a separate function to get 0’s in the signature as well.

Parameters:

• unsorted_signature (tuple[int, ...]) – The unsorted signature.

• func (callable, optional) – The lambda function of tuples of form (value, index) to sort the signature. Defaults to lambda x: x[0].

Returns:

The transformer to go from unsorted to sorted signature.

Return type:

list[int]

core.helper_operations.path_operations.transform(perms, tr)

Transforms a list of permutations as tuples according to the given renaming. The transformer list tr is a list of integers where the integer at index i is the new name for element i. See the example below.

The function raises a ValueError if lis contains an element whose index is larger than the length tr. So the transformation list should be at least as long as the largest index in the permutations.

Parameters:

• perms (list[tuple[int, ...]]) – List of permutations.

• tr (list[int]) – Transformation list, int at index i is the new name for i.

Returns:

List of tuples of integers. The transformed permutations.

Return type:

list[tuple[int, …]]

Raises:

ValueError – If the index of an element in the permutation is larger than the length of the transformation list.

Example

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

core.helper_operations.path_operations.transform_cycle_cover(perms3d, tr)

Transforms a list of unknown depth holding a list of permutations according to the given renaming. Used for the cycle cover. The transformer list tr is a list of integers where the integer at index i is the new name for element i. The depth is at least 2 and determined by the cycle cover function.

Parameters:

• perms3d (list[list[tuple[int, ...]]]) – List of lists of permutations. Does not have a fixed depth. The depth is determined by the cycle cover function. If the depth is 2 (list of lists of permutations, where permutations are tuples), the function will transform the permutations.

• tr (list[int]) – Transformation list, int at index i is the new name for i.

Returns:

The same structure of lists as the input, but with the permutations transformed.

Return type:

list[list[tuple[int, …]]]

Raises:

• AssertionError – If the input list does not have a length greater than 0.

• ValueError – If the input is not a list.

core.helper_operations.path_operations.shorten_cycle_cover(lis3d, elements)

Shortens a list of unknown depth holding a list of permutations by the given elements. Used for the cycle cover. The elements are removed from the permutations in the lists of tuples. Also checks whether all tuples end with the given elements.

Parameters:

• lis3d (list[list]) – List of lists of permutations. Does not have a fixed depth. The depth is determined by the cycle cover function. If the depth is 2 (list of lists of permutations, where permutations are tuples), the function will shorten the permutations.

• elements (tuple[int, ...]) – Tuple of integers to remove from the permutations.

Returns:

The same structure of lists as the input, but with the permutations shortened by elements.

Return type:

list[list]

Raises:

• AssertionError – If the input list does not have a length greater than 0.

• AssertionError – If a permutation does not end with the given elements.

core.helper_operations.path_operations.recursive_cycle_check(cycle, total_length=0)

Recursively check whether the given list is a cycle. The input is a list of cycles of unknown depth. The function will check the depth and return the total number of permutations in the lists of permutations. For each list, the cycle property is checked (and whether it has duplicates). Then the length of the cycle is added to the total length. The total length is returned.

Parameters:

• cycle (list[list]) – List of cycles.

• total_length (int, optional) – Total length of the cycle, defaults at 0.

Returns:

Total length of the list of cycles.

Return type:

int

Raises:

• AssertionError – If the input is not a list of length greater than 0.

• AssertionError – If the input is not a list of cycles.

• AssertionError – If the subcycles contain duplicates.

core.helper_operations.path_operations.get_first_element(nested_list, element=0)

Recursively retrieves the first element of a nested list.

Parameters:

• nested_list (list) – The nested list. Ultimately a tuple of integers (the permutations).

• element (int, optional) – The element to retrieve. Defaults to 0.

Returns:

The first element of the nested list.

Return type:

tuple[int, …]

core.helper_operations.path_operations.non_stutter_cycleQ(sig)

Return whether a cycle on the non-stutter permutations is possible for the given signature. This cycle is not possible for the following signatures:

• Linear neighbor-swap graphs (even-1 or odd-1)

• Odd-odd

• Odd-even / even-odd

• Even-1-1

Parameters:

sig (tuple[int, ...]) – The signature of the multiset permutations.

Returns:

True if a cycle on the non-stutter permutations is possible, False if only a path is possible.

Return type:

bool

core.helper_operations.path_operations.stutterPermutationQ(perm)

Check whether a given permutation is a stutter permutation. A stutter permutation is a permutation where all elements are the same except for the last two elements.

Parameters:

perm (tuple[int, ...]) – The permutation to check.

Returns:

True if the permutation is a stutter permutation, False otherwise.

Return type:

bool

core.helper_operations.path_operations.glue(cycle1, cycle2, vertex_pair_c1, vertex_pair_c2)

Glue two cycles together by using the cross edges instead of the parallel edges The cycles must contain the vertices and the vertices must be adjacent (in the cycle)

Parameters:

• cycle1 (list[tuple[int, ...]]) – The first cycle.

• cycle2 (list[tuple[int, ...]]) – The second cycle.

• vertex_pair_c1 (tuple[tuple[int, ...], tuple[int, ...]]) – The pair of vertices in the first cycle.

• vertex_pair_c2 (tuple[tuple[int, ...], tuple[int, ...]]) – The pair of vertices in the second cycle.

Returns:

The glued cycles.

Return type:

list[tuple[int, …]]

Raises:

ValueError – If the vertices are not adjacent in the cycles.

core.helper_operations.permutation_graphs module

core.helper_operations.permutation_graphs.binomial(k0, k1)

Returns binomial coefficient: k0+k1 choose k0.

Parameters:

• k0 (int) – The first parameter of the binomial coefficient.

• k1 (int) – The second parameter of the binomial coefficient.

Returns:

The calculated binomial coefficient.

Return type:

int

Raises:

AssertionError – If k0 or k1 is negative.

core.helper_operations.permutation_graphs.multinomial(sig)

Returns multinomial coefficient for list sig. sig is a tuple of integers, where each integer represents the number of occurrences of a unique element in a multiset. The multinomial coefficient is calculated as the product of the binomial coefficients of the elements in sig. The multinomial coefficient is the number of ways to arrange the elements of a multiset.

Parameters:

sig (tuple[int, ...]) – The tuple of integers for which the multinomial coefficient is calculated.

Returns:

The calculated multinomial coefficient.

Return type:

int

Raises:

AssertionError – If any element in sig is negative.

core.helper_operations.permutation_graphs.perm(sig)

Returns all permutations with signature sig. The signature is a list of integers, where each integer represents the number of occurrences of a unique element in a multiset. The permutations are returned as a list of lists of integers.

Parameters:

sig (tuple[int, ...]) – Signature as a tuple of integers

Returns:

List of permutations as lists of integers

Return type:

list[list[int]]

core.helper_operations.permutation_graphs.get_num_of_inversions(permutation)

Count the number of inversions in a permutation using merge sort. See references for more information.

Parameters:

permutation (tuple[int, ...]) – Permutation as a tuple of integers

Returns:

Number of inversions in the permutation

Return type:

int

References

• From https://www.geeksforgeeks.org/inversion-count-in-array-using-merge-sort/

core.helper_operations.permutation_graphs.count_inversions(sig)

Count the number of inversions for all permutations of a signature

Parameters:

sig (tuple[int, ...]) – Signature as a tuple of integers

Returns:

Dictionary with permutations as keys and number of inversions as values

Return type:

dict[tuple, int]

core.helper_operations.permutation_graphs.defect(sig)

Compute the defect of a signature. The defect is the difference between the number of even and odd permutations. The defect is the number of permutations that cannot be reached in the bipartite neighbor-swap graph. This defect is calculated by the difference in nodes between the two partitions of the bipartite graph. A bipartite graph can only admit a Hamiltonian cycle if the defect is 0 since it needs to alternate between the two partitions.

Parameters:

sig (tuple[int, ...]) – Signature as a list of integers

Returns:

The absolute difference between the number of even and odd permutations.

Return type:

int

core.helper_operations.permutation_graphs.swapPair(perm, i, j=None)

Swaps elements in perm at positions i and j (or i and i+1 if j is not provided). Note that i and j can be negative, in which case they are counted from the end of the permutation.

Parameters:

• perm (tuple[int, ...]) – Permutation as a tuple of integers.

• i (int) – Index to place the element that was previously at position j.

• j (int | None, optional) – Index to place the element that was previously at position i. Defaults to i+1.

Returns:

perm with elements at positions i and j swapped.

Return type:

tuple[int, …]

Raises:

ValueError – If the index i or j is out of range for the given permutation.

core.helper_operations.permutation_graphs.incorporateSpursInZigZag(path, vertices, spur_suffixes, skip=0)

Incorporates a list of spurs in a zigzag path. See incorporateSpurInZigZag for more details.

Parameters:

• path (list[tuple[int, ...]]) – List of vertices, a zigzag path.

• vertices (list[tuple[int, ...]]) – List of vertices to incorporate. These should be stutters.

• spur_suffixes (list[tuple[int, ...]]) – List of spur suffixes (suffixes for the vertices variable).

• skip (int, optional) – Number of elements to skip before the suffixes when finding the swap index. Defaults to 0.

Returns:

List of vertices, the zigzag path with the spurs incorporated.

Return type:

list[tuple[int, …]]

core.helper_operations.permutation_graphs.generate_adj(p)

Returns all adjacent elements of permutation p. Adjacent elements are generated by swapping pairs of elements in p.

Parameters:

p (list[int]) – List of integers representing a permutation

Returns:

List of tuples representing the new permutations generated by neighbor-swapping

Return type:

list[tuple[int, …]]

core.helper_operations.permutation_graphs.graph(sig)

Returns a graph with signature sig in form of dictionary of strings. Generates an adjacency dictionary where the keys are permutations and the values are sets of adjacent permutations.

Parameters:

sig (tuple[int, ...]) – signature as a tuple of integers

Returns:

dictionary with permutations as keys and adjacent permutations as values

Return type:

dict[str, set[str]]

core.helper_operations.permutation_graphs.extend(lst, e)

Extend every item in lst with e. The extension is done by concatenating the tuple e to each tuple in lst.

Parameters:

• lst (list[tuple[int, ...]]) – List of tuples to be extended.

• e (tuple[int, ...]) – Tuple to extend every item in lst with.

Returns:

List of tuples with each item extended by e.

Return type:

list[tuple[int, …]]

core.helper_operations.permutation_graphs.extend_cycle_cover(lis3d, e)

Extend every item in a list of unknown depth holding a list of permutations with e.

Parameters:

• lis3d (list[list[tuple[int, ...]]]) – List of unknown depth with list of tuples.

• e (tuple[int, ...]) – Tuple to extend every item in lis3d with.

Returns:

List of extended permutations. The list structure is preserved.

Return type:

list[list[tuple[int, …]]]

core.helper_operations.permutation_graphs.shorten(lis, num)

Shorten every item in l by num elements from the end.

Parameters:

• lis (list[tuple[int, ...]]) – List of permutations

• num (int) – Number of elements to remove from the back

Returns:

List of shortened permutations.

Return type:

list[tuple[int, …]]

core.helper_operations.permutation_graphs.get_perm_signature(permutation)

Get the signature of a permutation.

Parameters:

permutation (tuple[int, ...]) – The permutation as a tuple of integers.

Returns:

The signature of the permutation as a tuple of integers.

Return type:

tuple[int, …]

core.helper_operations.permutation_graphs.rotate(l, n)

Rotates the list l by n positions to the left.

Parameters:

• l (list) – The list to rotate.

• n (int) – The number of positions to rotate.

Returns:

The rotated list.

Return type:

list

core.helper_operations.permutation_graphs.halve_signature(sig)

Halves a signature sig (tuple of integers) by taking every element and dividing it by 2. The result is rounded down.

Parameters:

sig (tuple[int, ...]) – Signature as a tuple of integers.

Returns:

Halved signature as a tuple of integers.

Return type:

tuple[int, …]

Raises:

ValueError – If the signature contains negative integers.

Examples

>>> _halveSignature((2, 4, 6))
(1, 2, 3)
>>> _halveSignature((1, 3, 5))
(0, 1, 2)

core.helper_operations.permutation_graphs.multiset(s)

Generates the lexicographically smallest list with given signature.

Parameters:

s (tuple[int, ...]) – Tuple of integers, each representing the frequency of the corresponding element (signature).

Returns:

Lexicographically smallest permutation with the given signature.

Return type:

tuple[int, …]

core.helper_operations.permutation_graphs.permutations_from_sig(sig)

Generates all possible permutations of a given signature sig which is tuple of integers.

Parameters:

sig (tuple[int, ...]) – Tuple of integers, the signature.

Returns:

List of permutations as tuples of integers.

Return type:

list[tuple[int, …]]

core.helper_operations.permutation_graphs.stutterPermutations(sig)

Generates stutter permutations of a given signature. A stutter permutation is a permutation where each element is repeated twice. It can have a single trailing element but no other odd elements. If the signature is empty or contains only a single 0, an empty list is returned.

Parameters:

sig (tuple[int, ...]) – Signature of the permutations as a tuple of integers. Or an empty list if there are no stutter permutations.

Returns:

Stutter permutations as a list of tuples of integers.

Return type:

list[tuple[int, …]]

core.helper_operations.permutation_graphs.nonStutterPermutations(s)

Returns all non-stutter permutations of signature sig. See stutterPermutations for the definition of stutter permutations.

Parameters:

s (tuple[int, ...]) – signature of the permutations as a tuple of integers

Returns:

non-stutter permutations as a list of tuples of integers

Return type:

list[tuple[int, …]]

core.helper_operations.permutation_graphs.selectByTail(permutations, tail)

Select permutations with a given tail ‘tail’

Parameters:

• permutations (list[tuple[int, ...]]) – List of permutations

• tail (tuple[int, ...]) – Elements of the tail to select

Returns:

List of permutations with the given tail

Return type:

list[tuple[int, …]]

Raises:

AssertionError – If the length of the permutations differs between the permutations.

core.helper_operations.permutation_graphs.HpathQ(per, sig)

Determines whether the path is a Hamiltonian path on the non-stutter permutations of the given signature. The list is a Hamiltonian path iff it is a path and the set of permutations is equal to the set of non-stutter permutations.

Parameters:

• per (list[tuple[int, ...]]) – List of permutations ordered in a path.

• sig (tuple[int, ...]) – Signature as a tuple of integers.

Returns:

True if the path is a Hamiltonian path on the non-stutter permutations of the given signature, False otherwise.

Return type:

bool

core.helper_operations.permutation_graphs.HcycleQ(per, sig)

Determines whether the list of permutations is a Hamiltonian cycle on the non-stutter permutations of the given signature. The list is a Hamiltonian cycle iff the list is a Hamiltonian path and the first and last permutations are adjacent.

Parameters:

• per (list[tuple[int, ...]]) – List of permutations, ordered in a cycle.

• sig (tuple[int, ...]) – Signature as a tuple of integers.

Returns:

True if the list of permutations is a Hamiltonian cycle on the non-stutter permutations of the given signature, False otherwise.

Return type:

bool

core.helper_operations.permutation_graphs.LargeHpathQ(per, sig)

Determines whether the list is a Hamiltonian path on the non-stutter permutations of the given signature. Used for “larger” signatures where the path contains a lot of permutations. The other function will get slow then because it has to compare all permutations. This only only checks properties for a Hamiltonian path:

• No duplicates

• Correct length

• Is a path

Parameters:

• per (list[tuple[int, ...]]) – List of permutations, ordered in a path.

• sig (tuple[int, ...]) – Signature as a tuple of integers.

Returns:

True if the path is a Hamiltonian path on the non-stutter permutations of the given signature, False otherwise.

Return type:

bool

core.helper_operations.permutation_graphs.LargeHcycleQ(per, sig)

Determines whether the list is a Hamiltonian cycle on the non-stutter permutations of the given signature. Used for “larger” signatures where the cycle contains a lot of permutations. The other function will get slow then because it has to compare all permutations. This only only checks properties for a Hamiltonian cycle:

• No duplicates

• Correct length

• Is a cycle

Parameters:

• per (list[tuple[int, ...]]) – List of permutations, ordered in a cycle.

• sig (tuple[int, ...]) – Signature as a tuple of integers.

Returns:

True if the list is a Hamiltonian cycle on the non-stutter permutations of the given signature, False otherwise.

Return type:

bool

core.helper_operations.permutation_graphs.total_path_motion(permutation_list)

Returns the sum of the transposition widths for all edges in the permutation_list. The difference in index between the two transposed elements is the width of the transposition. The total motion is the sum of all transposition widths in the permutation_list. Note that the list is not required to be a path because the function takes into account the transpositions widths.

Parameters:

permutation_list (list[tuple[int, ...]]) – List of permutations to calculate the total motion for

Returns:

Total motion as an integer

Return type:

int

core.helper_operations.simple_verhoeff_paths module

core.helper_operations.simple_verhoeff_paths.Hpath_even_1_1(k)

Generates a path based on the number of 0’s k from 1 2 0^k to 0 2 1 0^(k-1)

Parameters:

k (int) – The input value for the number of 0’s. Must be even!

Returns:

The generated path from c to d: - c = 1 2 0^k - d = 0 2 1 0^(k-1)

Return type:

list[tuple[int, …]]

Raises:

ValueError – If k is not even

core.helper_operations.simple_verhoeff_paths.Hpath_odd_2_1(k)

Generates a path based on the number of 0’s k from 1 2 0^{k0} 1 to 0 2 1 0^{k0-1} 1.

Parameters:

k (int) – The input value for the number of 0’s. Must be odd!

Returns:

The generated path from a to b

• a = 1 2 0^{k0} 1

• b = 0 2 1 0^{k0-1} 1

Return type:

list[tuple[int, …]]

Raises:

ValueError – If k is not odd

core.helper_operations.simple_verhoeff_paths.Hcycle_odd_2_1(k)

Generates a cycle based on the number of 0’s k from 1 0 2 0^{k0-1} 1 to 0 1 2 0^{k0-1} 1.

Parameters:

k (int) – The input value for the number of 0’s. Must be odd!

Returns:

The generated cycle from e to f

• e = 1 0 2 0^{k0-1} 1

• f = 0 1 2 0^{k0-1} 1

Return type:

list[tuple[int, …]]

Raises:

ValueError – If k is not odd or k < 3

Module contents