core.type_variations package

Submodules

core.type_variations.stachowiak_list module

core.type_variations.stachowiak_list.transform_list(lis, tr)

Transforms a list of permutations as lists according to the given renaming.

Parameters:

• lis (list[list[int]]) – list of permutations

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

Returns:

list of lists of transformed permutations

Return type:

list[list[int]]

core.type_variations.stachowiak_list.lemma2_cycle(chain_p, case_2_1=True)

This function generates the cycles of Lemma 2. If the length of the chain_p is even the last two nodes are discarded as in the lemma. Defaults to case 2.1 of Lemma 2. If the case_2_1 variable is set to False, the cycle will be as in case 2.2. The discarded nodes are:

• d_p = (01 l^p, 10 l^p) for case 2.1

• d_p’ = (l^p 01, l^p 10) for case 2.2

Parameters:

• chain_p (list[int]) – The chain of p elements in the lemma

• case_2_1 (bool, optional) –

  Whether the case is 2.1 or 2.2. Defaults to True.

  • True ==> Case 2.1 with all d_i paths.

  • False ==> Case 2.2 with all d_i’ paths.

Returns:

The cycle of all d_i or d_i’ paths. If the length of chain_p is even, d_p or d_p’ is discarded respectively to the input for case_2_1.

Return type:

list[list[int]]

core.type_variations.stachowiak_list.lemma2_extended_path(chain_p, case_2_1=True)

Extends the cycle of Lemma 2 with the last two elements in case chain_p is even. If the length of chain_p is odd, then the cycle is returned. Defaults to case 2.1 of Lemma 2. If the case_2_1 variable is set to False, the path will be as in case 2.2.

If chain_p is even, the two nodes which are appended to the path are;

• d_p = (01 l^p, 10 l^p) for case 2.1

• d_p’ = (l^p 01, l^p 10) for case 2.2

Parameters:

• chain_p (list[int]) – The chain of p elements in the lemma.

• case_2_1 (bool, optional) –

  Whether the case is 2.1 or 2.2. Defaults to True.

  • True ==> Case 2.1 with all d_i paths.

  • False ==> Case 2.2 with all d_i’ paths.

Returns:

The cycle of all d_i or d_i’ paths extended with the two nodes that are left out if the length of chain_p is even.

• d_i=[0l^{p-i} 1 l^i, l0l^{p-i-1} 1 l^i, …, l^{p-i} 01 l^i, l^{p-i} 10 l^i, …, 1 l^{p-i} 0 l^i]

• d_i’=[l^i 1 l^{p-i} 0, l^i 1 l^{p-i-1} 0 l, …, l^{i} 10 l^{p-i}, l^i 01 l^{p-i}, …, l^i 0 l^{p-i} 1]

Return type:

list[list[int]]

core.type_variations.stachowiak_list.lemma7(sig)

Computes Lemma 7 by Stachowiak: The graph G=GE( (0|1) (k^q|l^p) ) contains a Hamilton cycle for every p, q > 0.

Parameters:

sig (tuple[int, ...]) – The signature of the graph in the form (1, 1, q, p). The elements are of colors 0, 1, 2, 3 (so color 2 occurs q times and 3 occurs p times).

Returns:

A Hamiltonian cycle of the form (0|1) (k^q|l^p)

Return type:

list[list[int]]

core.type_variations.stachowiak_list.lemma8(sig)

The graph G=GE( ((0|1) k^q) | l^p) ) contains a Hamilton cycle for every p, q > 0

Parameters:

sig (tuple[int, ...]) – The signature of the neighbor-swap graph; 1, 1, q, p. We assume the first two elements are of colors 0 and 1 and occur once. The second two elements are of colors 2 and 3 and occur q and p times respectively.

Returns:

A Hamiltonian cycle of the form GE((0|1) k^q) | l^p)

Return type:

list[list[int]]

core.type_variations.stachowiak_list.lemma9(sig)

The graph G=GE( (k^r (0|1) k^s) | l^p) ) contains a Hamilton cycle for every p, r+s > 0.

Parameters:

sig (tuple[int, ...]) –

The signature of the neighbor-swap graph; (1, 1, r, s, p). We assume:

• The first two elements are of colors 0 and 1 respectively and occur once.

• The second two elements are of color 2 and occur r and s times respectively.

• The fourth element is of color 3 and occurs p times.

Returns:

A Hamiltonian cycle of the form GE( (k^r (0|1) k^s) | l^p) )

Return type:

list[list[int]]

core.type_variations.stachowiak_list.lemma10(sig)

Computes Lemma 10 by Stachowiak: If q = |Q| > 2, Q is even and GE(Q) contains a Hamiltonian path and p > 0 then GE(Q|l^p) has a Hamiltonian cycle. Here Q is two elements in the signature that form a Hamiltonian path of even length and p is the third element.

Parameters:

sig (tuple[int, ...]) – The signature of the graph; Q is the first two elements, p is the third. Q is of length 2, its colors are 0 and 1. It contains a Hamiltonian path. p is the third element of sig and has color 2 and occurs p times.

Returns:

A Hamiltonian cycle in the neighbor-swap graph of the form GE(Q|l^p)

Return type:

list[list[int]]

Raises:

AssertionError – If the signature is not well-formed. The first two elements must be able to form a Hamiltonian path of even length > 2.

core.type_variations.stachowiak_list.lemma11(sig)

Finds a Hamiltonian cycle in a graph using Lemma 11 from Stachowiak’s paper: If q = |Q| > 2, p = |P| > 0 and GE(Q) has an even number of vertices and contains a Hamiltonian path then GE(Q|P) has a Hamiltonian cycle.

Parameters:

sig (tuple[int, ...]) – A signature of a neighbor-swap graph where at least two elements form a Hamiltonian path of even length > 2. These two elements are set to the front of the signature using a recursive call. Note that this can also be three elements if the first two are 1 (using Lemma 2). Or at least 3 elements that occur once (using Steinhaus-Johnson-Trotter algorithm). The rest of the signature is processed using Stachowiak’s lemmas.

Returns:

A Hamiltonian cycle in the neighbor-swap graph of the form GE(Q|P). Q is this Hamiltonian path and P is the rest of the signature

Return type:

list[list[int]]

Raises:

• ValueError – If the signature is empty.

• ValueError – There are no elements that can form a Hamiltonian path.

Notes

• If q = |Q| > 2, p = |P| > 0 and GE(Q) has an even number of vertices and contains a Hamiltonian path, then GE(Q|P) has a Hamiltonian cycle.

• The function first checks the length of the signature and handles special cases where the signature has only one or two elements.

• If the signature is not ordered well, it transforms the signature and recursively calls the function with the transformed signature. The order is well when the first two elements are the largest odd numbers.

• If the first two elements in the signature can form a cycle (more than two permutations), it uses Verhoeff’s Theorem to find the cycle.

• If the first 3 (or more) elements are 1, it uses the Steinhaus-Johnson-Trotter algorithm to get the Hamiltonian cycle.

• If the third element in the signature is not 0, it uses Stachowiak’s Lemma 2 to find a Hamiltonian path in GE(Q|l^{sig[2]}).

• Finally, it iterates over the remaining elements in the signature and calls the helper function _lemma10_helper to extend the cycle.

References

• Stachowiak G. Hamilton Paths in Graphs of Linear Extensions for Unions of Posets. Technical report, 1992

• Tom Verhoeff. The spurs of D. H. Lehmer: Hamiltonian paths in neighbor-swap graphs of permutations. Designs, Codes, and Cryptography, 84(1-2):295-310, 7 2017. (Used to find Hamiltonian cycles in binary neighbor-swap graphs.)

core.type_variations.stachowiak_list_verhoeff_tuple module

core.type_variations.stachowiak_list_verhoeff_tuple.lemma10(sig)

Computes Lemma 10 by Stachowiak: If q = |Q| > 2, Q is even and GE(Q) contains a Hamiltonian path and p > 0 then GE(Q|l^p) has a Hamiltonian cycle. Here Q is two elements in the signature that form a Hamiltonian path of even length and p is the third element.

Parameters:

sig (tuple[int, ...]) – The signature of the graph; Q is the first two elements, p is the third. Q is of length 2, its colors are 0 and 1. It contains a Hamiltonian path. p is the third element of sig and has color 2 and occurs p times.

Returns:

A Hamiltonian cycle in the neighbor-swap graph of the form GE(Q|l^p)

Return type:

list[list[int]]

Raises:

AssertionError – If the signature is not well-formed. The first two elements must be able to form a Hamiltonian path of even length > 2.

core.type_variations.stachowiak_list_verhoeff_tuple.lemma11(sig)

Finds a Hamiltonian cycle in a graph using Lemma 11 from Stachowiak’s paper: If q = |Q| > 2, p = |P| > 0 and GE(Q) has an even number of vertices and contains a Hamiltonian path then GE(Q|P) has a Hamiltonian cycle.

Parameters:

sig (tuple[int, ...]) – A signature of a neighbor-swap graph where at least two elements form a Hamiltonian path of even length > 2. These two elements are set to the front of the signature using a recursive call. Note that this can also be three elements if the first two are 1 (using Lemma 2). Or at least 3 elements that occur once (using Steinhaus-Johnson-Trotter algorithm). The rest of the signature is processed using Stachowiak’s lemmas.

Returns:

A Hamiltonian cycle in the neighbor-swap graph of the form GE(Q|P). Q is this Hamiltonian path and P is the rest of the signature

Return type:

list[list[int]]

Raises:

• ValueError – If the signature is empty.

• ValueError – There are no elements that can form a Hamiltonian path.

Notes

• If q = |Q| > 2, p = |P| > 0 and GE(Q) has an even number of vertices and contains a Hamiltonian path, then GE(Q|P) has a Hamiltonian cycle.

• The function first checks the length of the signature and handles special cases where the signature has only one or two elements.

• If the signature is not ordered well, it transforms the signature and recursively calls the function with the transformed signature. The order is well when the first two elements are the largest odd numbers.

• If the first two elements in the signature can form a cycle (more than two permutations), it uses Verhoeff’s Theorem to find the cycle.

• If the first 3 (or more) elements are 1, it uses the Steinhaus-Johnson-Trotter algorithm to get the Hamiltonian cycle.

• If the third element in the signature is not 0, it uses Stachowiak’s Lemma 2 to find a Hamiltonian path in GE(Q|l^{sig[2]}).

• Finally, it iterates over the remaining elements in the signature and calls the helper function _lemma10_helper to extend the cycle.

References

• Stachowiak G. Hamilton Paths in Graphs of Linear Extensions for Unions of Posets. Technical report, 1992

• Tom Verhoeff. The spurs of D. H. Lehmer: Hamiltonian paths in neighbor-swap graphs of permutations. Designs, Codes, and Cryptography, 84(1-2):295-310, 7 2017. (Used to find Hamiltonian cycles in binary neighbor-swap graphs.)

core.type_variations.stachowiak_numpy module

core.type_variations.stachowiak_numpy.split_path_in_2(p, a)

Split a path array into two parts based on a given value.

Parameters:

• p (np.ndarray) – The path array to be split.

• a (np.array) – The value used to split the path array.

Returns:

A tuple containing two arrays:

• The first array contains the elements of the path array up to and including the first occurrence of the given value.

• The second array contains the elements of the path array after the first occurrence of the given value.

Return type:

tuple[np.ndarray, np.ndarray]

Raises:

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

• AssertionError – If a is not in p.

core.type_variations.stachowiak_numpy.lemma2_cycle(chain_p, case_2_1=True)

This function generates the cycles of Lemma 2. If the length of the chain_p is even the last two nodes are discarded as in the lemma. Defaults to case 2.1 of Lemma 2. If the case_2_1 variable is set to False, the cycle will be as in case 2.2. The discarded nodes are:

• d_p = (01 l^p, 10 l^p) for case 2.1

• d_p’ = (l^p 01, l^p 10) for case 2.2

Parameters:

• chain_p (np.array) – The chain of p elements in the lemma

• case_2_1 (bool, optional) –

  Whether the case is 2.1 or 2.2. Defaults to True.

  • True ==> Case 2.1 with all d_i paths.

  • False ==> Case 2.2 with all d_i’ paths.

Returns:

The cycle of all d_i or d_i’ paths. If the length of chain_p is even, d_p or d_p’ is discarded respectively to the input for case_2_1.

Return type:

np.ndarray

core.type_variations.stachowiak_numpy.lemma2_extended_path(chain_p, case_2_1=True)

Extends the cycle of Lemma 2 with the last two elements in case chain_p is even. If the length of chain_p is odd, then the cycle is returned. Defaults to case 2.1 of Lemma 2. If the case_2_1 variable is set to False, the path will be as in case 2.2.

If chain_p is even, the two nodes which are appended to the path are;

• d_p = (01 l^p, 10 l^p) for case 2.1

• d_p’ = (l^p 01, l^p 10) for case 2.2

Parameters:

• chain_p (np.array) – The chain of p elements in the lemma.

• case_2_1 (bool, optional) –

  Whether the case is 2.1 or 2.2. Defaults to True.

  • True ==> Case 2.1 with all d_i chains.

  • False ==> Case 2.2 with all d_i’ chains.

Returns:

The cycle of all d_i or d_i’ chains extended with the two nodes that are left out if the length of chain_p is even.

• d_i=[0l^{p-i} 1 l^i, l0l^{p-i-1} 1 l^i, …, l^{p-i} 01 l^i, l^{p-i} 10 l^i, …, 1 l^{p-i} 0 l^i]

• d_i’=[l^i 1 l^{p-i} 0, l^i 1 l^{p-i-1} 0 l, …, l^{i} 10 l^{p-i}, l^i 01 l^{p-i}, …, l^i 0 l^{p-i} 1]

Return type:

np.ndarray

core.type_variations.stachowiak_numpy.lemma7(sig)

Computes Lemma 7 by Stachowiak: The graph G=GE( (0|1) (k^q|l^p) ) contains a Hamilton cycle for every p, q > 0.

Parameters:

sig (np.array) – The signature of the graph in the form [1, 1, q, p]. The elements are of colors 0, 1, 2, 3 (so color 2 occurs q times and 3 occurs p times).

Returns:

A Hamiltonian cycle of the form (0|1) (k^q|l^p)

Return type:

np.ndarray

core.type_variations.stachowiak_numpy.lemma8(sig)

The graph G=GE( ((0|1) k^q) | l^p) ) contains a Hamilton cycle for every p, q > 0

Parameters:

sig (np.array) – The signature of the neighbor-swap graph; 1, 1, q, p. We assume the first two elements are of colors 0 and 1 and occur once. The second two elements are of colors 2 and 3 and occur q and p times respectively.

Returns:

A Hamiltonian cycle of the form GE((0|1) k^q) | l^p)

Return type:

np.ndarray

core.type_variations.stachowiak_numpy.lemma9(sig)

The graph G=GE( (k^r (0|1) k^s) | l^p) ) contains a Hamilton cycle for every p, r+s > 0.

Parameters:

sig (np.array) –

The signature of the neighbor-swap graph; [1, 1, r, s, p]. We assume:

• The first two elements are of colors 0 and 1 respectively and occur once.

• The second two elements are of color 2 and occur r and s times respectively.

• The fourth element is of color 3 and occurs p times.

Returns:

A Hamiltonian cycle of the form GE( (k^r (0|1) k^s) | l^p) )

Return type:

np.ndarray

core.type_variations.stachowiak_numpy.lemma10(sig)

Computes Lemma 10 by Stachowiak: If q = |Q| > 2, Q is even and GE(Q) contains a Hamiltonian path and p > 0 then GE(Q|l^p) has a Hamiltonian cycle. Here Q is two elements in the signature that form a Hamiltonian path of even length and p is the third element.

Parameters:

sig (np.array) – The signature of the graph; Q is the first two elements, p is the third. Q is of length 2, its colors are 0 and 1. It contains a Hamiltonian path. p is the third element of sig and has color 2 and occurs p times.

Returns:

A Hamiltonian cycle in the neighbor-swap graph of the form GE(Q|l^p)

Return type:

np.ndarray

Raises:

AssertionError – If the signature is not well-formed. The first two elements must be able to form a Hamiltonian path of even length > 2.

core.type_variations.stachowiak_numpy.lemma11(sig)

Finds a Hamiltonian cycle in a graph using Lemma 11 from Stachowiak’s paper: If q = |Q| > 2, p = |P| > 0 and GE(Q) has an even number of vertices and contains a Hamiltonian path then GE(Q|P) has a Hamiltonian cycle.

Parameters:

sig (np.array) – A signature of a neighbor-swap graph where at least two elements form a Hamiltonian path of even length > 2. These two elements are set to the front of the signature using a recursive call. Note that this can also be three elements if the first two are 1 (using Lemma 2). Or at least 3 elements that occur once (using Steinhaus-Johnson-Trotter algorithm). The rest of the signature is processed using Stachowiak’s lemmas.

Returns:

A Hamiltonian cycle in the neighbor-swap graph of the form GE(Q|P). Q is this Hamiltonian path and P is the rest of the signature

Return type:

np.ndarray

Raises:

• ValueError – If the signature is empty.

• ValueError – There are no elements that can form a Hamiltonian path.

Notes

• If q = |Q| > 2, p = |P| > 0 and GE(Q) has an even number of vertices and contains a Hamiltonian path, then GE(Q|P) has a Hamiltonian cycle.

• The function first checks the length of the signature and handles special cases where the signature has only one or two elements.

• If the signature is not ordered well, it transforms the signature and recursively calls the function with the transformed signature. The order is well when the first two elements are the largest odd numbers.

• If the first two elements in the signature can form a cycle (more than two permutations), it uses Verhoeff’s Theorem to find the cycle.

• If the first 3 (or more) elements are 1, it uses the Steinhaus-Johnson-Trotter algorithm to get the Hamiltonian cycle.

• If the third element in the signature is not 0, it uses Stachowiak’s Lemma 2 to find a Hamiltonian path in GE(Q|l^{sig[2]}).

• Finally, it iterates over the remaining elements in the signature and calls the helper function _lemma10_helper to extend the cycle.

References

• Stachowiak G. Hamilton Paths in Graphs of Linear Extensions for Unions of Posets. Technical report, 1992

• Tom Verhoeff. The spurs of D. H. Lehmer: Hamiltonian paths in neighbor-swap graphs of permutations. Designs, Codes, and Cryptography, 84(1-2):295-310, 7 2017. (Used to find Hamiltonian cycles in binary neighbor-swap graphs.)

core.type_variations.stachowiak_tuple_verhoeff_list module

core.type_variations.stachowiak_tuple_verhoeff_list.lemma10(sig)

Computes Lemma 10 by Stachowiak: If q = |Q| > 2, Q is even and GE(Q) contains a Hamiltonian path and p > 0 then GE(Q|l^p) has a Hamiltonian cycle. Here Q is two elements in the signature that form a Hamiltonian path of even length and p is the third element.

Parameters:

sig (tuple[int, ...]) – The signature of the graph; Q is the first two elements, p is the third. Q is of length 2, its colors are 0 and 1. It contains a Hamiltonian path. p is the third element of sig and has color 2 and occurs p times.

Returns:

A Hamiltonian cycle in the neighbor-swap graph of the form GE(Q|l^p)

Return type:

list[tuple[int, …]]

Raises:

AssertionError – If the signature is not well-formed. The first two elements must be able to form a Hamiltonian path of even length > 2.

core.type_variations.stachowiak_tuple_verhoeff_list.lemma11(sig)

Finds a Hamiltonian cycle in a graph using Lemma 11 from Stachowiak’s paper: If q = |Q| > 2, p = |P| > 0 and GE(Q) has an even number of vertices and contains a Hamiltonian path then GE(Q|P) has a Hamiltonian cycle.

Parameters:

sig (tuple[int, ...]) – A signature of a neighbor-swap graph where at least two elements form a Hamiltonian path of even length > 2. These two elements are set to the front of the signature using a recursive call. Note that this can also be three elements if the first two are 1 (using Lemma 2). Or at least 3 elements that occur once (using Steinhaus-Johnson-Trotter algorithm). The rest of the signature is processed using Stachowiak’s lemmas.

Returns:

A Hamiltonian cycle in the neighbor-swap graph of the form GE(Q|P). Q is this Hamiltonian path and P is the rest of the signature

Return type:

list[tuple[int, …]]

Raises:

• ValueError – If the signature is empty.

• ValueError – There are no elements that can form a Hamiltonian path.

Notes

• If q = |Q| > 2, p = |P| > 0 and GE(Q) has an even number of vertices and contains a Hamiltonian path, then GE(Q|P) has a Hamiltonian cycle.

• The function first checks the length of the signature and handles special cases where the signature has only one or two elements.

• If the signature is not ordered well, it transforms the signature and recursively calls the function with the transformed signature. The order is well when the first two elements are the largest odd numbers.

• If the first two elements in the signature can form a cycle (more than two permutations), it uses Verhoeff’s Theorem to find the cycle.

• If the first 3 (or more) elements are 1, it uses the Steinhaus-Johnson-Trotter algorithm to get the Hamiltonian cycle.

• If the third element in the signature is not 0, it uses Stachowiak’s Lemma 2 to find a Hamiltonian path in GE(Q|l^{sig[2]}).

• Finally, it iterates over the remaining elements in the signature and calls the helper function _lemma10_helper to extend the cycle.

References

• Stachowiak G. Hamilton Paths in Graphs of Linear Extensions for Unions of Posets. Technical report, 1992

• Tom Verhoeff. The spurs of D. H. Lehmer: Hamiltonian paths in neighbor-swap graphs of permutations. Designs, Codes, and Cryptography, 84(1-2):295-310, 7 2017. (Used to find Hamiltonian cycles in binary neighbor-swap graphs.)

core.type_variations.steinhaus_johnson_trotter_list module

class core.type_variations.steinhaus_johnson_trotter_list.SteinhausJohnsonTrotterList

Bases: object

LEFT_TO_RIGHT = True

RIGHT_TO_LEFT = False

searchArr(a, n, mobile)

Search for the mobile element in the array a

Parameters:

• a (list[int]) – The array of elements

• n (int) – The length of the array

• mobile (int) – The mobile element

Returns:

The index of the mobile element

Return type:

int

getMobile(a, dir, n)

Get the mobile element in the array a

Parameters:

• a (list[int]) – The array of elements

• dir (list[bool]) – The direction array

• n (int) – The length of the array

Returns:

The mobile element

Return type:

int

get_sjt_permutations(n)

Generate permutations using the Steinhaus-Johnson-Trotter algorithm.

Parameters:

n (int) – The number of elements in the permutation.

Returns:

A list of permutations generated using the Steinhaus-Johnson-Trotter algorithm.

Return type:

list[list[int]]

core.type_variations.steinhaus_johnson_trotter_numpy module

class core.type_variations.steinhaus_johnson_trotter_numpy.SteinhausJohnsonTrotterNumpy

Bases: object

LEFT_TO_RIGHT = True

RIGHT_TO_LEFT = False

searchArr(a, n, mobile)

Search for the mobile element in the array a

Parameters:

• a (np.ndarray) – The array of elements

• n (int) – The length of the array

• mobile (int) – The mobile element

Returns:

The index of the mobile element

Return type:

int

getMobile(a, dir, n)

Get the mobile element in the array a

Parameters:

• a (np.ndarray) – The array of elements

• dir (np.ndarray) – The direction array

• n (int) – The length of the array

Returns:

The mobile element

Return type:

int

get_sjt_permutations(n)

Get the steinhaus-johnson-trotter permutations of length n

Parameters:

n (int) – The length of the permutations

Returns:

A 2D array of permutations of length

Return type:

np.ndarray

core.type_variations.verhoeff_list module

core.type_variations.verhoeff_list.stutterize(p)

Converts argument into a stutter permutation by repeating every number.

Parameters:

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

Returns:

every number in p repeated twice and put into a list

Return type:

list[list[int]]

core.type_variations.verhoeff_list.selectOdds(sig)

Returns list of numbers with odd occurrence frequencies in the given signature. :type sig: tuple[int, ...] :param sig: signature as a list of integers :type sig: tuple[int, …]

Returns:

list of integers with odd occurrence frequencies in the signature

Return type:

list[int]

core.type_variations.verhoeff_list.stutterPermutations(s)

Generates stutter permutations of a given signature. Stutter permutations have the form [a, a, b, b, c, c, …, z] where a, b, c, … are the elements of the permutation. So every pair of elements is repeated twice from the left. An stutter can have one element with odd frequency appended at the end. :type s: tuple[int, ...] :param s: the signature of the stutter permutations :type s: tuple[int, …]

Returns:

list of stutter permutations of signature s

Return type:

list[list[int]]

core.type_variations.verhoeff_list.createZigZagPath(c, u, v)

Creates a zigzag path from a given cycle c by appending u and v and v and u alternatively. :type c: list[list[int]] :param c: cycle of even length, list of tuples of integers :type c: list[list[int]] :type u: list[int] :param u: tuple to append :type u: list[int] :type v: list[int] :param v: tuple to append, adjacent to u :type v: list[int]

Returns:

cycle obtained by combining two “parallel” copies of given cycle, to form a ‘square wave’, running from cycle[[0]]v to cycle[[-1]]v; the two copies are distinguished by appending u and v; also works for a path

Return type:

list[list[int]]

Raises:

AssertionError – If u and v are not adjacent

core.type_variations.verhoeff_list.incorporateSpurInZigZag(path, vertex_pair)

Incorporates a spur path into a zigzag path. The spur has the same last two elements as the zigzag path. The spurs are stutters if the last two elements are disregarded. They have to be incorporated in the zigzag path because those elements are appended. :type path: list[list[int]] :param path: zigzag path as a list of lists of integers :type path: list[list[int]] :type vertex_pair: list[list[int]] :param vertex_pair: spur path as a list of lists of integers :type vertex_pair: list[list[int]]

Returns:

zigzag path with the spur path incorporated

Return type:

list[list[int]]

core.type_variations.verhoeff_list.incorporateSpursInZigZag(path, vertices, spur_suffixes)

Incorporates multiple spur paths into a zigzag path. Uses the incorporateSpurInZigZag function. :type path: list[list[int]] :param path: zigzag path as a list of lists of integers. :type path: list[list[int]] :type vertices: list[list[int]] :param vertices: list of spur paths as a list of lists of integers. :type vertices: list[list[int]] :type spur_suffixes: list[list[int]] :param spur_suffixes: list of suffixes for the spur paths. :type spur_suffixes: list[list[int]]

Returns:

zigzag path with the spur paths incorporated.

Return type:

list[list[int]]

core.type_variations.verhoeff_list.createSquareTube(path, u, v)

Creates a square tube from a given path by appending u and v in the following order: uu, uv, vv, vu, -> next node -> vu, vv, uv, uu. and for the last two nodes: uu, uv, vv, vu -> next node -> vu, uu, uv, vv. :type path: list[list[int]] :param path: path as a list of lists of integers :type path: list[list[int]] :type u: list[int] :param u: tuple to append :type u: list[int] :type v: list[int] :param v: tuple to append, adjacent to u :type v: list[int]

Returns:

path obtained by combining four copies of given path, to form a ‘square tube’, running from path[0]uu to path[-1]vv; the four copies are distinguished by appending u and v

Return type:

list[list[int]]

core.type_variations.verhoeff_list.swapPair(perm, i, j=None)

Swaps elements in perm at positions i and j (or i and i+1 if j is not provided). :type perm: list[int] :param perm: list of integers :type perm: list[int] :type i: int :param i: index of the first element to swap :type i: int :type j: int | None :param j: index of the second element to swap. Defaults to None; in this case, j is set to i+1. :type j: int | None, optional

Returns:

list of integers with elements at positions i and j swapped

Return type:

list[int]

core.type_variations.verhoeff_list.extend(lst, e)

Extend every item in l with e :type lst: list[list[int]] :param lst: list of lists of integers :type lst: list[list[int]] :type e: list[int] :param e: list to extend every item in lst with :type e: list[int]

Returns:

list of lists of integers with every item of lst extended by e

Return type:

list[list[int]]

core.type_variations.verhoeff_list.HpathNS(k0, k1)

Computes a Hamiltonian path in the neighbor-swap graph on the non-stutter permutations for the given signature. If k0 and k1 are both even, the path is a Hamiltonian cycle. :type k0: int :param k0: Number of 0s in the signature. :type k0: int :type k1: int :param k1: Number of 1s in the signature. :type k1: int

Returns:

A Hamiltonian path in the neighbor-swap graph G(0^k_0|1^(k_1)).

Return type:

list[list[int]]

References

• Tom Verhoeff. The spurs of D. H. Lehmer: Hamiltonian paths in neighbor-swap graphs of permutations. Designs, Codes, and Cryptography, 84(1-2):295-310, 7 2017.

core.type_variations.verhoeff_numpy module

core.type_variations.verhoeff_numpy.stutterize(perm)

Converts argument into stutter permutation by repeating every number.

Parameters:

perm (np.array) – A permutation of integers to be converted into a stutter permutation.

Returns:

The input permutation but every integers is repeated twice.

Return type:

np.ndarray

core.type_variations.verhoeff_numpy.selectOdds(sig)

Returns list of numbers with odd occurrence frequencies in the given signature.

Parameters:

sig (np.array) – A signature of a permutation.

Returns:

A list of numbers with odd occurrence frequencies.

Return type:

np.array

core.type_variations.verhoeff_numpy.multiset(freq)

Generates the lexicographically smallest list with given occurrence frequencies.

Parameters:

freq (np.array) – A list of integers representing the occurrence frequencies of the elements.

Returns:

A list of integers with the given occurrence frequencies.

Return type:

np.ndarray

core.type_variations.verhoeff_numpy.permutations(s)

Generates all possible permutations of a given list of integers.

Parameters:

s (np.array) – The signature of the permutations.

Returns:

A list of all possible permutations with the input signature.

Return type:

np.ndarray

core.type_variations.verhoeff_numpy.stutterPermutations(s)

Generates stutter permutations of a given list of integers.

Parameters:

s (np.array) – The signature of the permutations.

Returns:

A list of all possible stutter permutations with the input signature.

Return type:

np.ndarray

core.type_variations.verhoeff_numpy.createZigZagPath(c, uv)

Creates a zigzag path by combining two “parallel” copies of the given cycle.

Parameters:

• c (np.ndarray) – A cycle of even length.

• uv (np.ndarray) – An array containing two elements [u, v] to append.

Returns:

A cycle obtained by combining two “parallel” copies of the given cycle to form a ‘square wave’,

running from cycle[[1]]v to cycle[[-1]]v. The two copies are distinguished by appending u and v. Also works for a path.

Return type:

np.ndarray

Raises:

AssertionError – If the elements in uv are not adjacent.

core.type_variations.verhoeff_numpy.cutCycle(c, a)

Splits a cycle at vertex a. Vertex a appears on first place

Parameters:

• c (np.ndarray) – A cycle.

• a (np.array) – A vertex to split the cycle at.

Returns:

A cycle which starts with vertex a.

Return type:

np.ndarray

core.type_variations.verhoeff_numpy.incorporateSpurInZigZag(path, vertex_pair)

Incorporates a spur into a zigzag path.

Parameters:

• path (np.ndarray) – A zigzag path.

• vertex_pair (np.ndarray) – A pair of vertices to incorporate into the path.

Returns:

A zigzag path with the spur incorporated.

Return type:

np.ndarray

core.type_variations.verhoeff_numpy.incorporateSpursInZigZag(path, vertices, spur_suffixes)

Incorporates a list of spurs into a zigzag path.

Parameters:

• path (np.ndarray) – A zigzag path.

• vertices (np.ndarray) – A list of vertices to incorporate into the path.

• spur_suffixes (np.ndarray) – A list of suffixes to incorporate into the path.

Returns:

A zigzag path with the spurs incorporated.

Return type:

np.ndarray

core.type_variations.verhoeff_numpy.createSquareTube(path, u, v)

Creates a square tube path by interleaving the elements of the four copies of the path list.

Parameters:

• path (np.ndarray) – A path list.

• u (np.array) – An array of one of the two elements to append.

• v (np.array) – An array of one of the two elements to append.

Returns:

A square tube path; u and v are appended to the path list in an interleaved manner.

Return type:

np.ndarray

core.type_variations.verhoeff_numpy.swapPair(perm, i, j=None)

Swaps elements in perm at positions i and j (or i and i+1 if j is not provided).

Parameters:

• perm (np.ndarray) – A permutation.

• i (int) – The first index to swap.

• j (int | None, optional) – The second index to swap. Defaults to None; in this case, i+1 is used.

Returns:

The permutation with the elements at positions i and j swapped

Return type:

np.ndarray

core.type_variations.verhoeff_numpy.extend(lst, e)

Extend every item in l with e

Parameters:

• lst (np.ndarray) – A list of arrays.

• e (np.ndarray) – An array to extend the list with.

Returns:

A list of arrays with e appended to each array.

Return type:

np.ndarray

core.type_variations.verhoeff_numpy.HpathNS(k0, k1)

Computes a Hamiltonian path in the neighbor-swap graph on the non-stutter permutations for the given signature. If k0 and k1 are both even, the path is a Hamiltonian cycle.

Parameters:

• k0 (int) – Number of 0s in the signature.

• k1 (int) – Number of 1s in the signature.

Returns:

A Hamiltonian path in the neighbor-swap graph G(0^k_0|1^(k_1)).

Return type:

np.ndarray

References

• Tom Verhoeff. The spurs of D. H. Lehmer: Hamiltonian paths in neighbor-swap graphs of permutations. Designs, Codes, and Cryptography, 84(1-2):295-310, 7 2017.

Module contents