API Reference

This section provides detailed API documentation for all modules and classes in the BiSC algorithm package.

bisc_package

BiSC Algorithm Package

Implementation of the BiSC algorithm from “BiSC: An algorithm for discovering generalized permutation patterns” by Henning Ulfarsson.

The BiSC algorithm automatically discovers forbidden patterns in sets of permutations, bridging computer science and mathematics through automated conjecture generation.

class bisc_package.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.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.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.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.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.

Core Modules

bisc_package.core.bisc_algorithm

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.permutation

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

bisc_package.core.mesh_pattern

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

Utility Modules

bisc_package.utils.pattern_utils

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

bisc_package.utils.mesh_utils

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

Example Modules

bisc_package.examples.known_classes.stack_sortable

Stack-sortable permutations example.

Stack-sortable permutations are those that can be sorted using a single stack. They are characterized by avoiding the pattern 231.

bisc_package.examples.known_classes.stack_sortable.generate_stack_sortable(max_length)

Generate all stack-sortable permutations up to max_length.

Parameters:

max_length (int) – Maximum length of permutations to generate

Return type:

List[Permutation]

Returns:

List of stack-sortable permutations

bisc_package.examples.known_classes.stack_sortable.demo_stack_sortable()

Demonstrate BiSC on stack-sortable permutations.

bisc_package.examples.known_classes.smooth_permutations

Smooth permutations example.

Smooth permutations are related to smooth Schubert varieties in algebraic geometry. They are characterized by avoiding patterns 1324 and 2143.

bisc_package.examples.known_classes.smooth_permutations.generate_smooth_permutations(max_length)

Generate all smooth permutations up to max_length.

Parameters:

max_length (int) – Maximum length of permutations to generate

Return type:

List[Permutation]

Returns:

List of smooth permutations

bisc_package.examples.known_classes.smooth_permutations.demo_smooth_permutations()

Demonstrate BiSC on smooth permutations.

bisc_package.examples.known_classes.baxter_permutations

Baxter permutations example.

Baxter permutations have applications in various areas of mathematics and are characterized by avoiding certain mesh patterns.

bisc_package.examples.known_classes.baxter_permutations.generate_baxter_approximation(max_length)

Generate an approximation of Baxter permutations using classical patterns.

Note: True Baxter permutations are defined by mesh patterns (2413, {(2,2)}) and (3142, {(2,2)}), but we use classical patterns as an approximation.

Parameters:

max_length (int) – Maximum length of permutations to generate

Return type:

List[Permutation]

Returns:

List of permutations avoiding classical patterns 2413 and 3142

bisc_package.examples.known_classes.baxter_permutations.demo_baxter_permutations()

Demonstrate the complexity of Baxter permutations.

bisc_package.examples.bisc_demo

Demonstration of the BiSC algorithm implementation.

This reproduces the core BiSC algorithm from the paper: “BiSC: An algorithm for discovering generalized permutation patterns” by Henning Ulfarsson.

bisc_package.examples.bisc_demo.demonstrate_bisc()

Demonstrate the BiSC algorithm with clear examples.

Command Line Interface

bisc_package.cli

Command-line interface for the BiSC algorithm package.

This module provides console commands for running examples and demonstrations.

bisc_package.cli.run_examples()

Run the main BiSC algorithm examples.

bisc_package.cli.run_demo()

Run the comprehensive BiSC demonstration.

bisc_package.cli.print_basic_info()

Print basic information about the BiSC algorithm.

bisc_package.cli.main()

Main CLI entry point.

Testing Modules

bisc_package.tests.unit.test_permutation

Unit tests for the Permutation class.

bisc_package.tests.unit.test_permutation.test_permutation()

Test basic Permutation functionality.

bisc_package.tests.unit.test_permutation.test_permutation_validation()

Test permutation validation.

bisc_package.tests.integration.verify_examples

Verification of examples from the BiSC paper. Tests our implementation against the specific examples mentioned in the paper.

bisc_package.tests.integration.verify_examples.generate_all_permutations(max_length)

Generate all permutations up to given length.

Return type:

List[List[int]]

bisc_package.tests.integration.verify_examples.contains_pattern(permutation, pattern)

Check if permutation contains the given classical pattern.

Return type:

bool

bisc_package.tests.integration.verify_examples.verify_stack_sortable()

Verify Example 1: Stack-sortable permutations avoid 231.

bisc_package.tests.integration.verify_examples.verify_west_2_stack_sortable()

Verify Example 2: West-2-stack-sortable permutations.

bisc_package.tests.integration.verify_examples.verify_difficult_example()

Verify the difficult example from equation (2): 1, 21, 321, 2341, 4123, 4321.

bisc_package.tests.integration.verify_examples.verify_smooth_permutations()

Verify smooth permutations avoid 1324 and 2143.

bisc_package.tests.integration.verify_examples.main()

Run all verifications.