bisc_package.core package

Submodules

bisc_package.core.bisc_algorithm module

Main BiSC algorithm implementation.

This module contains the core MINE and GEN algorithms, as well as the main BiSC algorithm that combines them.

bisc_package.core.bisc_algorithm.mine_algorithm(permutations, max_pattern_length)

The MINE algorithm (Algorithm 1 from the paper).

Finds all mesh patterns that are contained in permutations in the input. This is the first step of the BiSC algorithm.

Parameters:

• permutations (List[Permutation]) – List of input permutations

• max_pattern_length (int) – Upper bound on pattern length to search for

Return type:

Dict[Tuple[int, ...], Set[FrozenSet]]

Returns:

Dictionary mapping classical patterns to sets of maximal shadings

Note

The output maps pattern tuples to sets of frozensets, where each frozenset represents a maximal shading for that pattern.

bisc_package.core.bisc_algorithm.gen_algorithm(S)

The GEN algorithm (Algorithm 2 from the paper).

Generates forbidden patterns from the allowed patterns found by MINE. This is the second step of the BiSC algorithm.

Parameters:

S (Dict[Tuple[int, ...], Set[FrozenSet]]) – Output from MINE algorithm - patterns with their allowed shadings

Return type:

List[MeshPattern]

Returns:

List of forbidden mesh patterns

Note

This generates minimal forbidden shadings that are not contained in any allowed shading.

bisc_package.core.bisc_algorithm.bisc_algorithm(permutations, max_pattern_length)

The full BiSC algorithm.

Combines the MINE and GEN algorithms to discover forbidden patterns in a set of permutations.

Parameters:

• permutations (List[Permutation]) – Input set of permutations

• max_pattern_length (int) – Upper bound on pattern length to search for

Return type:

List[MeshPattern]

Returns:

List of conjectured forbidden patterns

Examples

>>> # Stack-sortable permutations
>>> stack_sortable = [Permutation([1]), Permutation([1,2]), ...]
>>> forbidden = bisc_algorithm(stack_sortable, max_pattern_length=3)
>>> # Should find pattern 231 as forbidden

bisc_package.core.bisc_algorithm.bisc_with_pruning(permutations, max_pattern_length)

BiSC algorithm with additional pruning step.

This version includes post-processing to remove redundant patterns.

Parameters:

• permutations (List[Permutation]) – Input set of permutations

• max_pattern_length (int) – Upper bound on pattern length to search for

Return type:

List[MeshPattern]

Returns:

List of minimal forbidden patterns

bisc_package.core.bisc_algorithm.analyze_pattern_statistics(S)

Analyze statistics from the MINE algorithm output.

Parameters:

S (Dict[Tuple[int, ...], Set[FrozenSet]]) – Output from MINE algorithm

Return type:

Dict[str, int]

Returns:

Dictionary with various statistics

bisc_package.core.mesh_pattern module

Mesh pattern class for the BiSC algorithm.

This module provides the MeshPattern class for representing classical patterns with shaded regions.

class bisc_package.core.mesh_pattern.MeshPattern(pattern, shading=None)

Bases: object

Represents a mesh pattern (classical pattern + shading).

A mesh pattern consists of: 1. A classical pattern (permutation) 2. A set of shaded regions that forbid elements from appearing

pattern

The classical pattern

Type:

List[int]

shading

Set of shaded regions (i,j)

Type:

frozenset

length

Length of the classical pattern

Type:

int

__init__(pattern, shading=None)

Initialize a mesh pattern.

Parameters:

• pattern (List[int]) – The classical pattern as a list

• shading (Set[Tuple[int, int]]) – Set of shaded regions (i,j). Defaults to empty set.

__str__()

String representation of the mesh pattern.

__repr__()

Detailed string representation.

__eq__(other)

Check equality with another mesh pattern.

__hash__()

Hash function for use in sets and dictionaries.

is_classical()

Check if this is a classical pattern (no shading).

Return type:

bool

add_shading(region)

Return a new mesh pattern with an additional shaded region.

Parameters:

region (Tuple[int, int]) – The (i,j) region to shade

Return type:

MeshPattern

Returns:

New MeshPattern with the additional shading

remove_shading(region)

Return a new mesh pattern with a shaded region removed.

Parameters:

region (Tuple[int, int]) – The (i,j) region to unshade

Return type:

MeshPattern

Returns:

New MeshPattern without the specified shading

get_all_regions()

Get all possible mesh regions for this pattern.

Return type:

Set[Tuple[int, int]]

Returns:

Set of all possible (i,j) mesh regions

get_unshaded_regions()

Get all unshaded mesh regions.

Return type:

Set[Tuple[int, int]]

Returns:

Set of unshaded (i,j) regions

is_shading_maximal(allowed_shadings)

Check if this shading is maximal among allowed shadings.

Parameters:

allowed_shadings (Set[frozenset]) – Set of allowed shading patterns

Return type:

bool

Returns:

True if this shading is maximal

get_classical_pattern()

Get the underlying classical pattern.

Return type:

List[int]

to_latex()

Generate LaTeX representation (basic version).

Return type:

str

Returns:

LaTeX string representation

bisc_package.core.permutation module

Permutation class for the BiSC algorithm.

This module provides the core Permutation class with methods for subword enumeration and pattern analysis.

class bisc_package.core.permutation.Permutation(sequence)

Bases: object

Represents a permutation in one-line notation.

A permutation is a bijection from {1, 2, …, n} to itself. We represent it as a list where position i contains the value π(i).

sequence

The permutation in one-line notation

Type:

List[int]

length

The length of the permutation

Type:

int

__init__(sequence)

Initialize a permutation.

Parameters:

sequence (List[int]) – List representing the permutation in one-line notation

__str__()

String representation of the permutation.

__repr__()

Detailed string representation.

__eq__(other)

Check equality with another permutation.

__hash__()

Hash function for use in sets and dictionaries.

subwords(max_length)

Generate all subwords of length at most max_length.

Parameters:

max_length (int) – Maximum length of subwords to generate

Returns:

• subword is the subsequence of values

• positions is the list of indices where these values occur

Return type:

List of tuples (subword, positions) where

contains_classical_pattern(pattern)

Check if this permutation contains a classical pattern.

Parameters:

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

Return type:

bool

Returns:

True if the pattern is contained, False otherwise

reverse()

Return the reverse of this permutation.

Return type:

Permutation

complement()

Return the complement of this permutation.

Return type:

Permutation

inverse()

Return the inverse of this permutation.

Return type:

Permutation

Module contents

Core BiSC algorithm components.

class bisc_package.core.Permutation(sequence)

Bases: object

Represents a permutation in one-line notation.

A permutation is a bijection from {1, 2, …, n} to itself. We represent it as a list where position i contains the value π(i).

sequence

The permutation in one-line notation

Type:

List[int]

length

The length of the permutation

Type:

int

__eq__(other)

Check equality with another permutation.

__hash__()

Hash function for use in sets and dictionaries.

__init__(sequence)

Initialize a permutation.

Parameters:

sequence (List[int]) – List representing the permutation in one-line notation

__repr__()

Detailed string representation.

__str__()

String representation of the permutation.

complement()

Return the complement of this permutation.

Return type:

Permutation

contains_classical_pattern(pattern)

Check if this permutation contains a classical pattern.

Parameters:

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

Return type:

bool

Returns:

True if the pattern is contained, False otherwise

inverse()

Return the inverse of this permutation.

Return type:

Permutation

reverse()

Return the reverse of this permutation.

Return type:

Permutation

subwords(max_length)

Generate all subwords of length at most max_length.

Parameters:

max_length (int) – Maximum length of subwords to generate

Returns:

• subword is the subsequence of values

• positions is the list of indices where these values occur

Return type:

List of tuples (subword, positions) where

class bisc_package.core.MeshPattern(pattern, shading=None)

Bases: object

Represents a mesh pattern (classical pattern + shading).

A mesh pattern consists of: 1. A classical pattern (permutation) 2. A set of shaded regions that forbid elements from appearing

pattern

The classical pattern

Type:

List[int]

shading

Set of shaded regions (i,j)

Type:

frozenset

length

Length of the classical pattern

Type:

int

__eq__(other)

Check equality with another mesh pattern.

__hash__()

Hash function for use in sets and dictionaries.

__init__(pattern, shading=None)

Initialize a mesh pattern.

Parameters:

• pattern (List[int]) – The classical pattern as a list

• shading (Set[Tuple[int, int]]) – Set of shaded regions (i,j). Defaults to empty set.

__repr__()

Detailed string representation.

__str__()

String representation of the mesh pattern.

add_shading(region)

Return a new mesh pattern with an additional shaded region.

Parameters:

region (Tuple[int, int]) – The (i,j) region to shade

Return type:

MeshPattern

Returns:

New MeshPattern with the additional shading

get_all_regions()

Get all possible mesh regions for this pattern.

Return type:

Set[Tuple[int, int]]

Returns:

Set of all possible (i,j) mesh regions

get_classical_pattern()

Get the underlying classical pattern.

Return type:

List[int]

get_unshaded_regions()

Get all unshaded mesh regions.

Return type:

Set[Tuple[int, int]]

Returns:

Set of unshaded (i,j) regions

is_classical()

Check if this is a classical pattern (no shading).

Return type:

bool

is_shading_maximal(allowed_shadings)

Check if this shading is maximal among allowed shadings.

Parameters:

allowed_shadings (Set[frozenset]) – Set of allowed shading patterns

Return type:

bool

Returns:

True if this shading is maximal

remove_shading(region)

Return a new mesh pattern with a shaded region removed.

Parameters:

region (Tuple[int, int]) – The (i,j) region to unshade

Return type:

MeshPattern

Returns:

New MeshPattern without the specified shading

to_latex()

Generate LaTeX representation (basic version).

Return type:

str

Returns:

LaTeX string representation

bisc_package.core.bisc_algorithm(permutations, max_pattern_length)

The full BiSC algorithm.

Combines the MINE and GEN algorithms to discover forbidden patterns in a set of permutations.

Parameters:

• permutations (List[Permutation]) – Input set of permutations

• max_pattern_length (int) – Upper bound on pattern length to search for

Return type:

List[MeshPattern]

Returns:

List of conjectured forbidden patterns

Examples

>>> # Stack-sortable permutations
>>> stack_sortable = [Permutation([1]), Permutation([1,2]), ...]
>>> forbidden = bisc_algorithm(stack_sortable, max_pattern_length=3)
>>> # Should find pattern 231 as forbidden

bisc_package.core.mine_algorithm(permutations, max_pattern_length)

The MINE algorithm (Algorithm 1 from the paper).

Finds all mesh patterns that are contained in permutations in the input. This is the first step of the BiSC algorithm.

Parameters:

• permutations (List[Permutation]) – List of input permutations

• max_pattern_length (int) – Upper bound on pattern length to search for

Return type:

Dict[Tuple[int, ...], Set[FrozenSet]]

Returns:

Dictionary mapping classical patterns to sets of maximal shadings

Note

The output maps pattern tuples to sets of frozensets, where each frozenset represents a maximal shading for that pattern.

bisc_package.core.gen_algorithm(S)

The GEN algorithm (Algorithm 2 from the paper).

Generates forbidden patterns from the allowed patterns found by MINE. This is the second step of the BiSC algorithm.

Parameters:

S (Dict[Tuple[int, ...], Set[FrozenSet]]) – Output from MINE algorithm - patterns with their allowed shadings

Return type:

List[MeshPattern]

Returns:

List of forbidden mesh patterns

Note

This generates minimal forbidden shadings that are not contained in any allowed shading.