5.2. sdzkp.elementaryabeliansubgroup

Classes

class sdzkp.elementaryabeliansubgroup.ElementaryAbelianSubgroup(n, generators)[source]

A class to represent an elementary abelian subgroup of the symmetric group Sn. The subgroup is generated by a set of permutations.

Initializes an ElementaryAbelianSubgroup instance.

Parameters:

n (int) – The number of elements in the symmetric group Sn.
generators (dict) – A dictionary of generators for the subgroup.

is_valid_permutation(perm)[source]

Checks if a given permutation is valid.

Parameters:: perm (list) – A permutation.
Returns:: True if the permutation is valid, False otherwise.
Return type:: bool

transpose(perm, i, j)[source]

Transposes two elements in the permutation.

Parameters:

perm (list) – The permutation.
i (int) – Index of the first element.
j (int) – Index of the second element.

Returns:

The permutation after transposition.

Return type:

list

multiply_permutations(perm1, perm2)[source]

Multiplies two permutations.

Parameters:

perm1 (list) – The first permutation.
perm2 (list) – The second permutation.

Returns:

The resulting permutation after multiplication.

Return type:

list

multiply_generators()[source]

Multiplies all generators to produce a single permutation.

Returns:: The resulting permutation after multiplying all generators.
Return type:: list

inverse(perm)[source]

Computes the inverse of a permutation.

Parameters:: perm (list) – The permutation to be inverted.
Returns:: A new instance with the inverse permutation.
Return type:: ElementaryAbelianSubgroup

random_binary_array()[source]

Generates a random binary array.

Returns:: A list of random 0s and 1s.
Return type:: list

generate_element_from_bitarray(bit_array)[source]

Generates an element of the subgroup from a binary array.

Parameters:: bit_array (list) – A binary array indicating which generators to use.
Returns:: A tuple containing the generated permutation and the bit array.
Return type:: tuple

random_element()[source]

Generates a random element of the subgroup.

Returns:: A tuple containing the random permutation and the bit array used to generate it.
Return type:: tuple

solve(g)[source]

Solves the subgroup distance problem by finding the element closest to a given permutation.

Parameters:: g (list) – The target permutation.
Returns:: The closest element in the subgroup and the Hamming distance.
Return type:: tuple

hamming_distance(p1, p2)[source]

Calculates the Hamming distance between two permutations.

Parameters:

p1 (list) – The first permutation.
p2 (list) – The second permutation.

Returns:

The Hamming distance.

Return type:

int

generate_all_elements()[source]

Generates all elements of the subgroup.

Returns:: A list of all permutations in the subgroup.
Return type:: list

print_all_elements()[source]: Prints all elements of the subgroup.

inverse_permutation(perm)[source]

Returns the inverse of a permutation. Since we use only transpositions, the elements are their own inverses.

Parameters:: perm (list) – The permutation.
Returns:: The inverse permutation.
Return type:: list

apply_generators(bitmask)[source]

Applies the generators to the identity permutation based on a bitmask.

Parameters:: bitmask (int) – A bitmask indicating which generators to apply.
Returns:: The resulting permutation.
Return type:: list

class sdzkp.elementaryabeliansubgroup.ElementaryAbelianSubgroupWithSolution(n, generators, solution_t_h)[source]

A subclass of ElementaryAbelianSubgroup that includes a solution to the subgroup distance problem.

Initializes an ElementaryAbelianSubgroupWithSolution instance.

Parameters:

n (int) – The number of elements in the symmetric group Sn.
generators (dict) – A dictionary of generators for the subgroup.
solution_t_h (list) – A bit array that generates the solution.

multiply_solution_generators()[source]

Multiplies the generators specified by the solution bit array.

Returns:: A tuple containing the resulting permutation and the bit array.
Return type:: tuple