bisc_package package

Subpackages

• bisc_package.core package
  • Submodules
  • bisc_package.core.bisc_algorithm module
    • mine_algorithm()
    • gen_algorithm()
    • bisc_algorithm()
    • bisc_with_pruning()
    • analyze_pattern_statistics()
  • bisc_package.core.mesh_pattern module
    • MeshPattern
      • MeshPattern.pattern
      • MeshPattern.shading
      • MeshPattern.length
      • MeshPattern.__init__()
      • MeshPattern.__str__()
      • MeshPattern.__repr__()
      • MeshPattern.__eq__()
      • MeshPattern.__hash__()
      • MeshPattern.is_classical()
      • MeshPattern.add_shading()
      • MeshPattern.remove_shading()
      • MeshPattern.get_all_regions()
      • MeshPattern.get_unshaded_regions()
      • MeshPattern.is_shading_maximal()
      • MeshPattern.get_classical_pattern()
      • MeshPattern.to_latex()
  • bisc_package.core.permutation module
    • Permutation
      • Permutation.sequence
      • Permutation.length
      • Permutation.__init__()
      • Permutation.__str__()
      • Permutation.__repr__()
      • Permutation.__eq__()
      • Permutation.__hash__()
      • Permutation.subwords()
      • Permutation.contains_classical_pattern()
      • Permutation.reverse()
      • Permutation.complement()
      • Permutation.inverse()
  • Module contents
    • Permutation
      • Permutation.sequence
      • Permutation.length
      • Permutation.__eq__()
      • Permutation.__hash__()
      • Permutation.__init__()
      • Permutation.__repr__()
      • Permutation.__str__()
      • Permutation.complement()
      • Permutation.contains_classical_pattern()
      • Permutation.inverse()
      • Permutation.reverse()
      • Permutation.subwords()
    • MeshPattern
      • MeshPattern.pattern
      • MeshPattern.shading
      • MeshPattern.length
      • MeshPattern.__eq__()
      • MeshPattern.__hash__()
      • MeshPattern.__init__()
      • MeshPattern.__repr__()
      • MeshPattern.__str__()
      • MeshPattern.add_shading()
      • MeshPattern.get_all_regions()
      • MeshPattern.get_classical_pattern()
      • MeshPattern.get_unshaded_regions()
      • MeshPattern.is_classical()
      • MeshPattern.is_shading_maximal()
      • MeshPattern.remove_shading()
      • MeshPattern.to_latex()
    • bisc_algorithm()
    • mine_algorithm()
    • gen_algorithm()
• bisc_package.examples package
  • Subpackages
    • bisc_package.examples.known_classes package
      • Submodules
      • bisc_package.examples.known_classes.baxter_permutations module
      • bisc_package.examples.known_classes.corrected_baxter_test module
      • bisc_package.examples.known_classes.smooth_permutations module
      • bisc_package.examples.known_classes.stack_sortable module
      • bisc_package.examples.known_classes.test_baxter module
      • Module contents
    • bisc_package.examples.paper_examples package
      • Module contents
  • Submodules
  • bisc_package.examples.bisc_demo module
    • demonstrate_bisc()
  • Module contents
    • run_all_examples()
• bisc_package.tests package
  • Subpackages
    • bisc_package.tests.integration package
      • Submodules
      • bisc_package.tests.integration.bisc_simple_test module
      • bisc_package.tests.integration.simple_verification module
      • bisc_package.tests.integration.verify_examples module
      • Module contents
    • bisc_package.tests.unit package
      • Submodules
      • bisc_package.tests.unit.test_permutation module
      • Module contents
  • Module contents
    • run_all_tests()
• bisc_package.utils package
  • Submodules
  • bisc_package.utils.mesh_utils module
    • get_maximal_shading()
    • is_pattern_contained()
    • is_shading_consequence()
    • mesh_pattern_contains()
    • generate_mesh_regions()
    • is_shading_minimal()
    • visualize_mesh_pattern()
  • bisc_package.utils.pattern_utils module
    • flatten()
    • contains_pattern()
    • generate_all_permutations()
    • find_missing_patterns()
    • permutation_to_string()
    • string_to_permutation()
    • reverse_permutation()
    • complement_permutation()
    • inverse_permutation()
  • Module contents
    • flatten()
    • contains_pattern()
    • generate_all_permutations()
    • get_maximal_shading()
    • is_pattern_contained()
    • is_shading_consequence()

Submodules

bisc_package.cli module

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.

Module contents

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.