"""
Simple verification of BiSC examples using basic pattern analysis.
Focus on pattern presence/absence rather than full mesh pattern generation.
"""
from typing import List
from itertools import combinations, permutations
[docs]
def flatten(word: List[int]) -> List[int]:
"""Flattens a word to a permutation by replacing values with their relative order."""
if not word:
return []
sorted_unique = sorted(set(word))
rank_map = {val: i + 1 for i, val in enumerate(sorted_unique)}
return [rank_map[val] for val in word]
[docs]
def contains_pattern(permutation: List[int], pattern: List[int]) -> bool:
"""Check if permutation contains the given classical pattern."""
if len(pattern) > len(permutation):
return False
for positions in combinations(range(len(permutation)), len(pattern)):
subword = [permutation[i] for i in positions]
if flatten(subword) == pattern:
return True
return False
[docs]
def find_missing_patterns(input_perms: List[List[int]], max_pattern_length: int) -> List[List[int]]:
"""Find patterns that are missing from the input set."""
# Generate all possible patterns up to max_pattern_length
all_patterns = []
for length in range(1, max_pattern_length + 1):
for perm in permutations(range(1, length + 1)):
all_patterns.append(list(perm))
# Find which patterns appear in the input
patterns_seen = set()
for perm in input_perms:
for pattern_length in range(1, min(len(perm) + 1, max_pattern_length + 1)):
for positions in combinations(range(len(perm)), pattern_length):
subword = [perm[i] for i in positions]
pattern = flatten(subword)
patterns_seen.add(tuple(pattern))
# Find missing patterns
missing = []
for pattern in all_patterns:
if tuple(pattern) not in patterns_seen:
missing.append(pattern)
return missing
[docs]
def verify_stack_sortable():
"""Test 1: Stack-sortable permutations should avoid 231."""
print("=" * 50)
print("TEST 1: Stack-sortable permutations")
print("=" * 50)
# All permutations of length ≤ 4 that avoid 231
all_perms = []
for length in range(1, 5):
for perm in permutations(range(1, length + 1)):
perm_list = list(perm)
if not contains_pattern(perm_list, [2, 3, 1]):
all_perms.append(perm_list)
print(f"Stack-sortable permutations (length ≤ 4): {len(all_perms)} total")
# Show some examples
print("\nExamples:")
for i, perm in enumerate(all_perms[:10]):
print(f" {''.join(map(str, perm))}")
if len(all_perms) > 10:
print(f" ... and {len(all_perms) - 10} more")
# Find missing patterns
missing = find_missing_patterns(all_perms, 3)
print(f"\nMissing patterns of length ≤ 3: {missing}")
# Check if 231 is the only missing pattern of length 3
missing_length_3 = [p for p in missing if len(p) == 3]
expected = [[2, 3, 1]]
success = missing_length_3 == expected
print(f"\nExpected missing: {expected}")
print(f"Actually missing: {missing_length_3}")
print(f"Result: {'PASS' if success else 'FAIL'}")
return success
[docs]
def verify_smooth_permutations():
"""Test 2: Smooth permutations should avoid 1324 and 2143."""
print("\n" + "=" * 50)
print("TEST 2: Smooth permutations")
print("=" * 50)
# All permutations that avoid both 1324 and 2143
smooth_perms = []
for length in range(1, 5):
for perm in permutations(range(1, length + 1)):
perm_list = list(perm)
if (not contains_pattern(perm_list, [1, 3, 2, 4]) and
not contains_pattern(perm_list, [2, 1, 4, 3])):
smooth_perms.append(perm_list)
print(f"Smooth permutations (length ≤ 4): {len(smooth_perms)} total")
# Find missing patterns
missing = find_missing_patterns(smooth_perms, 4)
missing_length_4 = [p for p in missing if len(p) == 4]
print(f"\nMissing patterns of length 4: {len(missing_length_4)} patterns")
for pattern in missing_length_4[:5]: # Show first 5
print(f" {''.join(map(str, pattern))}")
if len(missing_length_4) > 5:
print(f" ... and {len(missing_length_4) - 5} more")
# Check if 1324 and 2143 are among the missing
has_1324 = [1, 3, 2, 4] in missing_length_4
has_2143 = [2, 1, 4, 3] in missing_length_4
print(f"\nChecking for expected forbidden patterns:")
print(f" 1324 missing: {has_1324}")
print(f" 2143 missing: {has_2143}")
success = has_1324 and has_2143
print(f"Result: {'PASS' if success else 'FAIL'}")
return success
[docs]
def verify_west_2_stack():
"""Test 3: Partial test for West-2-stack-sortable."""
print("\n" + "=" * 50)
print("TEST 3: West-2-stack-sortable (partial)")
print("=" * 50)
# From the paper - some West-2-stack-sortable permutations
west_perms = [
[1],
[1, 2], [2, 1],
[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1],
# Some length 4 examples (not complete list)
[1, 2, 3, 4], [1, 2, 4, 3], [1, 3, 2, 4], [2, 1, 3, 4],
[3, 1, 2, 4], [4, 1, 2, 3], [4, 3, 2, 1]
]
print(f"Sample West-2-stack-sortable permutations: {len(west_perms)}")
for perm in west_perms:
print(f" {''.join(map(str, perm))}")
# Check which common patterns are missing
test_patterns = [
[2, 3, 4, 1], # 2341
[3, 2, 4, 1], # 3241
]
print(f"\nTesting for absence of key patterns:")
for pattern in test_patterns:
found = any(contains_pattern(perm, pattern) for perm in west_perms)
print(f" Pattern {''.join(map(str, pattern))}: {'present' if found else 'absent'}")
# For this test, we expect 2341 to be absent
success = not any(contains_pattern(perm, [2, 3, 4, 1]) for perm in west_perms)
print(f"Result: {'PASS' if success else 'FAIL'} (2341 should be absent)")
return success
[docs]
def verify_difficult_example():
"""Test 4: The difficult example from equation (2)."""
print("\n" + "=" * 50)
print("TEST 4: Difficult example from equation (2)")
print("=" * 50)
# The exact permutations from equation (2) in the paper
difficult_perms = [
[1],
[2, 1],
[3, 2, 1],
[2, 3, 4, 1],
[4, 1, 2, 3],
[4, 3, 2, 1]
]
print("Input permutations from equation (2):")
for perm in difficult_perms:
print(f" {''.join(map(str, perm))}")
# Check what patterns of length ≤ 2 are present
patterns_length_2 = []
for perm in difficult_perms:
for pos in combinations(range(len(perm)), min(2, len(perm))):
if len(pos) == 2:
subword = [perm[i] for i in pos]
pattern = flatten(subword)
if pattern not in patterns_length_2:
patterns_length_2.append(pattern)
print(f"\nLength-2 patterns found: {patterns_length_2}")
# Check what's missing
all_length_2 = [[1, 2], [2, 1]]
missing_length_2 = [p for p in all_length_2 if p not in patterns_length_2]
print(f"Missing length-2 patterns: {missing_length_2}")
# This is a complex example - we mainly check that analysis runs
success = len(difficult_perms) == 6 # Basic sanity check
print(f"Result: {'PASS' if success else 'FAIL'} (basic analysis)")
return success
[docs]
def main():
"""Run all simple verifications."""
print("SIMPLE BISC VERIFICATION")
print("Testing pattern presence/absence in examples from the paper")
tests = [
("Stack-sortable permutations", verify_stack_sortable),
("Smooth permutations", verify_smooth_permutations),
("West-2-stack-sortable (partial)", verify_west_2_stack),
("Difficult example", verify_difficult_example),
]
results = []
for test_name, test_func in tests:
try:
success = test_func()
results.append((test_name, success))
except Exception as e:
print(f"Error in {test_name}: {e}")
results.append((test_name, False))
# Summary
print("\n" + "=" * 50)
print("VERIFICATION SUMMARY")
print("=" * 50)
for test_name, success in results:
status = "PASS" if success else "FAIL"
print(f"{test_name:30s}: {status}")
passed = sum(1 for _, success in results if success)
total = len(results)
print(f"\nOverall: {passed}/{total} tests passed")
if __name__ == "__main__":
main()