bisc_package.utils package

Submodules

bisc_package.utils.mesh_utils module

Mesh pattern utilities for the BiSC algorithm.

bisc_package.utils.mesh_utils.get_maximal_shading(pattern, subword, positions, permutation)

Compute the maximal shading for a pattern occurrence.

This is a core operation in the MINE algorithm. For a given occurrence of a classical pattern in a permutation, we find the maximal set of mesh regions that can be shaded while still preserving the occurrence.

Parameters:

• pattern (List[int]) – The flattened classical pattern

• subword (List[int]) – The original subword from the permutation

• positions (List[int]) – Positions of the subword in the permutation

• permutation (Permutation) – The full permutation

Return type:

Set[Tuple[int, int]]

Returns:

Set of shaded regions (i,j) where i is row, j is column

bisc_package.utils.mesh_utils.is_pattern_contained(small_pattern, large_pattern)

Check if small_pattern is contained in large_pattern as a classical pattern.

Parameters:

• small_pattern (List[int]) – The pattern to search for

• large_pattern (List[int]) – The pattern to search in

Return type:

bool

Returns:

True if small_pattern is contained in large_pattern

bisc_package.utils.mesh_utils.is_shading_consequence(forbidden_short, candidate_long)

Check if the long pattern’s forbidden shading is a consequence of the short pattern.

This is used in the GEN algorithm to remove redundant forbidden patterns. A mesh pattern is redundant if any permutation containing it also contains a previously forbidden pattern.

Parameters:

• forbidden_short (MeshPattern) – A previously identified forbidden pattern

• candidate_long (MeshPattern) – A candidate forbidden pattern to check

Return type:

bool

Returns:

True if candidate_long is a consequence of forbidden_short

Note

This is a simplified implementation. A complete version would require more sophisticated analysis of mesh pattern containment relationships.

bisc_package.utils.mesh_utils.mesh_pattern_contains(permutation, mesh_pattern)

Check if a permutation contains a mesh pattern.

This is a simplified implementation that checks classical pattern containment. A complete implementation would also verify mesh constraints.

Parameters:

• permutation (Permutation) – The permutation to check

• mesh_pattern (MeshPattern) – The mesh pattern to search for

Return type:

bool

Returns:

True if the mesh pattern is contained

Note

This implementation only checks classical pattern containment. Full mesh pattern checking requires geometric constraint verification.

bisc_package.utils.mesh_utils.generate_mesh_regions(pattern_length)

Generate all possible mesh regions for a pattern of given length.

Parameters:

pattern_length (int) – Length of the classical pattern

Return type:

List[Tuple[int, int]]

Returns:

List of all possible (i,j) mesh regions

bisc_package.utils.mesh_utils.is_shading_minimal(shading, forbidden_shadings)

Check if a shading is minimal among forbidden shadings.

Parameters:

• shading (Set[Tuple[int, int]]) – The shading to check

• forbidden_shadings (List[Set[Tuple[int, int]]]) – List of existing forbidden shadings

Return type:

bool

Returns:

True if the shading is minimal (no proper subset is also forbidden)

bisc_package.utils.mesh_utils.visualize_mesh_pattern(mesh_pattern)

Create a simple text visualization of a mesh pattern.

Parameters:

mesh_pattern (MeshPattern) – The mesh pattern to visualize

Return type:

str

Returns:

String representation of the pattern with shading

bisc_package.utils.pattern_utils module

Pattern manipulation utilities for the BiSC algorithm.

bisc_package.utils.pattern_utils.flatten(word)

Flatten a word to a permutation by replacing values with their relative order.

This is a fundamental operation in pattern analysis. Given a word of distinct integers, it replaces the i-th smallest value with i.

Parameters:

word (List[int]) – List of distinct integers

Return type:

List[int]

Returns:

The flattened permutation

Examples

>>> flatten([3, 1, 4])
[2, 1, 3]
>>> flatten([5, 2, 8, 1])
[3, 2, 4, 1]

bisc_package.utils.pattern_utils.contains_pattern(permutation, pattern)

Check if permutation contains the given classical pattern.

Parameters:

• permutation (List[int]) – The permutation to search in

• pattern (List[int]) – The pattern to search for

Return type:

bool

Returns:

True if the pattern is contained, False otherwise

Examples

>>> contains_pattern([3, 1, 4, 2], [2, 1])
True
>>> contains_pattern([1, 2, 3], [3, 2, 1])
False

bisc_package.utils.pattern_utils.generate_all_permutations(max_length)

Generate all permutations up to a given length.

Parameters:

max_length (int) – Maximum length of permutations to generate

Return type:

List[List[int]]

Returns:

List of all permutations of length 1 to max_length

bisc_package.utils.pattern_utils.find_missing_patterns(input_perms, max_pattern_length)

Find classical patterns that are missing from the input set.

Parameters:

• input_perms (List[List[int]]) – List of input permutations

• max_pattern_length (int) – Maximum length of patterns to consider

Return type:

List[List[int]]

Returns:

List of missing patterns

bisc_package.utils.pattern_utils.permutation_to_string(perm)

Convert a permutation to a string representation.

Parameters:

perm (List[int]) – The permutation as a list

Return type:

str

Returns:

String representation

bisc_package.utils.pattern_utils.string_to_permutation(s)

Convert a string to a permutation.

Parameters:

s (str) – String representation of the permutation

Return type:

List[int]

Returns:

The permutation as a list

Raises:

ValueError – If the string doesn’t represent a valid permutation

bisc_package.utils.pattern_utils.reverse_permutation(perm)

Return the reverse of a permutation.

Parameters:

perm (List[int]) – The input permutation

Return type:

List[int]

Returns:

The reversed permutation

bisc_package.utils.pattern_utils.complement_permutation(perm)

Return the complement of a permutation.

Parameters:

perm (List[int]) – The input permutation

Return type:

List[int]

Returns:

The complement permutation

bisc_package.utils.pattern_utils.inverse_permutation(perm)

Return the inverse of a permutation.

Parameters:

perm (List[int]) – The input permutation

Return type:

List[int]

Returns:

The inverse permutation

Module contents

Utility functions for the BiSC algorithm.

bisc_package.utils.flatten(word)

Flatten a word to a permutation by replacing values with their relative order.

This is a fundamental operation in pattern analysis. Given a word of distinct integers, it replaces the i-th smallest value with i.

Parameters:

word (List[int]) – List of distinct integers

Return type:

List[int]

Returns:

The flattened permutation

Examples

>>> flatten([3, 1, 4])
[2, 1, 3]
>>> flatten([5, 2, 8, 1])
[3, 2, 4, 1]

bisc_package.utils.contains_pattern(permutation, pattern)

Check if permutation contains the given classical pattern.

Parameters:

• permutation (List[int]) – The permutation to search in

• pattern (List[int]) – The pattern to search for

Return type:

bool

Returns:

True if the pattern is contained, False otherwise

Examples

>>> contains_pattern([3, 1, 4, 2], [2, 1])
True
>>> contains_pattern([1, 2, 3], [3, 2, 1])
False

bisc_package.utils.generate_all_permutations(max_length)

Generate all permutations up to a given length.

Parameters:

max_length (int) – Maximum length of permutations to generate

Return type:

List[List[int]]

Returns:

List of all permutations of length 1 to max_length

bisc_package.utils.get_maximal_shading(pattern, subword, positions, permutation)

Compute the maximal shading for a pattern occurrence.

This is a core operation in the MINE algorithm. For a given occurrence of a classical pattern in a permutation, we find the maximal set of mesh regions that can be shaded while still preserving the occurrence.

Parameters:

• pattern (List[int]) – The flattened classical pattern

• subword (List[int]) – The original subword from the permutation

• positions (List[int]) – Positions of the subword in the permutation

• permutation (Permutation) – The full permutation

Return type:

Set[Tuple[int, int]]

Returns:

Set of shaded regions (i,j) where i is row, j is column

bisc_package.utils.is_pattern_contained(small_pattern, large_pattern)

Check if small_pattern is contained in large_pattern as a classical pattern.

Parameters:

• small_pattern (List[int]) – The pattern to search for

• large_pattern (List[int]) – The pattern to search in

Return type:

bool

Returns:

True if small_pattern is contained in large_pattern

bisc_package.utils.is_shading_consequence(forbidden_short, candidate_long)

Check if the long pattern’s forbidden shading is a consequence of the short pattern.

This is used in the GEN algorithm to remove redundant forbidden patterns. A mesh pattern is redundant if any permutation containing it also contains a previously forbidden pattern.

Parameters:

• forbidden_short (MeshPattern) – A previously identified forbidden pattern

• candidate_long (MeshPattern) – A candidate forbidden pattern to check

Return type:

bool

Returns:

True if candidate_long is a consequence of forbidden_short

Note

This is a simplified implementation. A complete version would require more sophisticated analysis of mesh pattern containment relationships.