Examples

This section provides detailed examples of using the BiSC algorithm for various permutation classes.

Stack-Sortable Permutations

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

from bisc_package import Permutation, bisc_algorithm

# Define stack-sortable permutations up to length 4
stack_sortable = [
    Permutation([1]),
    Permutation([1, 2]),
    Permutation([2, 1]),
    Permutation([1, 2, 3]),
    Permutation([1, 3, 2]),
    Permutation([2, 1, 3]),
    Permutation([2, 3, 1]),  # This is actually 321, not 231
    Permutation([3, 1, 2]),  # This is 312
    Permutation([3, 2, 1]),  # This is 321
]

# Note: 231 pattern should be excluded from stack-sortable permutations
# Let's use the correct set:
correct_stack_sortable = [
    Permutation([1]),
    Permutation([1, 2]),
    Permutation([2, 1]),
    Permutation([1, 2, 3]),
    Permutation([1, 3, 2]),
    Permutation([2, 1, 3]),
    Permutation([3, 1, 2]),
    Permutation([3, 2, 1]),
]

# Find forbidden patterns
forbidden = bisc_algorithm(correct_stack_sortable, max_pattern_length=3)
print(f"Forbidden pattern for stack-sortable: {forbidden}")

Smooth Permutations

Smooth permutations avoid the patterns 1324 and 2143.

from bisc_package import Permutation, bisc_algorithm

# Generate smooth permutations up to length 4
# (This is a simplified example - in practice you'd generate all smooth perms)
smooth_perms = [
    Permutation([1]),
    Permutation([1, 2]),
    Permutation([2, 1]),
    Permutation([1, 2, 3]),
    Permutation([1, 3, 2]),
    Permutation([2, 1, 3]),
    Permutation([2, 3, 1]),
    Permutation([3, 1, 2]),
    Permutation([3, 2, 1]),
    # Length 4 smooth permutations (excluding 1324 and 2143)
    Permutation([1, 2, 3, 4]),
    Permutation([1, 2, 4, 3]),
    # ... (would include all smooth permutations of length 4)
]

# Find forbidden patterns of length 4
forbidden = bisc_algorithm(smooth_perms, max_pattern_length=4)
print(f"Forbidden patterns for smooth permutations: {forbidden}")

Custom Pattern Discovery

You can use the BiSC algorithm to discover patterns in your own permutation classes:

from bisc_package import Permutation, bisc_algorithm

# Define your own permutation class
my_permutations = [
    Permutation([1, 2, 3]),
    Permutation([1, 3, 2]),
    Permutation([2, 1, 3]),
    Permutation([3, 2, 1]),
    # Add more permutations that belong to your class
]

# Discover forbidden patterns of various lengths
for length in range(2, 5):
    forbidden = bisc_algorithm(my_permutations, max_pattern_length=length)
    if forbidden:
        print(f"Length {length} forbidden patterns: {forbidden}")
    else:
        print(f"No forbidden patterns of length {length}")

Working with Mesh Patterns

The BiSC algorithm can also work with mesh patterns for more sophisticated pattern avoidance:

from bisc_package import MeshPattern, Permutation
from bisc_package.core.bisc_algorithm import mine_patterns

# Create permutations
perms = [Permutation([1, 2, 3]), Permutation([1, 3, 2])]

# Mine mesh patterns
patterns = mine_patterns(perms, 3)
print(f"Found mesh patterns: {patterns}")

# You can also create specific mesh patterns
mesh_pattern = MeshPattern([1, 2], {(0, 0), (2, 2)})
print(f"Custom mesh pattern: {mesh_pattern}")

Performance Analysis

For larger permutation sets, you can analyze the performance:

import time
from bisc_package import Permutation, bisc_algorithm

# Generate a larger set of permutations
large_set = []
for i in range(1, 100):  # Adjust size as needed
    # Generate some permutation (this is just an example)
    if i % 2 == 0:
        large_set.append(Permutation([1, 2, 3]))
    else:
        large_set.append(Permutation([1, 3, 2]))

# Time the algorithm
start_time = time.time()
forbidden = bisc_algorithm(large_set, max_pattern_length=3)
end_time = time.time()

print(f"Found {len(forbidden)} forbidden patterns")
print(f"Time taken: {end_time - start_time:.4f} seconds")

Advanced Usage with Pattern Containment

You can also check if specific patterns are contained in permutations:

from bisc_package import Permutation

perm = Permutation([3, 1, 4, 2])
pattern = Permutation([2, 1, 3])

# Check if pattern is contained in permutation
if pattern in perm.get_subwords(3):
    print(f"Pattern {pattern} is contained in {perm}")
else:
    print(f"Pattern {pattern} is NOT contained in {perm}")

Batch Processing

For processing multiple permutation classes:

from bisc_package import Permutation, bisc_algorithm

# Define multiple permutation classes
classes = {
    "class1": [Permutation([1, 2]), Permutation([2, 1])],
    "class2": [Permutation([1, 2, 3]), Permutation([1, 3, 2])],
    "class3": [Permutation([1, 3, 2]), Permutation([2, 1, 3])],
}

# Process each class
results = {}
for class_name, perms in classes.items():
    forbidden = bisc_algorithm(perms, max_pattern_length=3)
    results[class_name] = forbidden
    print(f"{class_name}: {forbidden}")

# Compare results
print("\nComparison:")
for class_name, forbidden in results.items():
    print(f"{class_name} has {len(forbidden)} forbidden patterns")

Integration with External Data

You can also load permutations from external sources:

from bisc_package import Permutation, bisc_algorithm

# Example: Load from a file (pseudocode)
def load_permutations_from_file(filename):
    permutations = []
    # Read file and parse permutations
    # This is just an example - implement according to your file format
    with open(filename, 'r') as f:
        for line in f:
            # Parse line to get permutation data
            perm_data = list(map(int, line.strip().split()))
            permutations.append(Permutation(perm_data))
    return permutations

# Example usage (if you have a data file)
# perms = load_permutations_from_file('my_permutations.txt')
# forbidden = bisc_algorithm(perms, max_pattern_length=4)
# print(f"Forbidden patterns: {forbidden}")

These examples demonstrate the flexibility and power of the BiSC algorithm for discovering forbidden patterns in various permutation classes.