Fast algorithms for finding pattern avoiders and counting pattern occurrences in permutations

DOI10.1090/mcom/3216zbMath1377.05004arXiv1509.08216OpenAlexW2964183276MaRDI QIDQ4600719

William Kuszmaul

Publication date: 12 January 2018

Published in: Mathematics of Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1509.08216

zbMATH Keywords

permutation patternsvincular patterns

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) General topics in the theory of algorithms (68W01)

Related Items

Classical length-5 pattern-avoiding permutations, Catalan intervals and uniquely sorted permutations, Fast algorithms for finding pattern avoiders and counting pattern occurrences in permutations, Unnamed Item, Automatic discovery of structural rules of permutation classes

Uses Software

• SageMath
• OEIS
• PermLab

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding pattern matchings for permutations
• Pattern matching for permutations
• A fast algorithm for permutation pattern matching based on alternating runs
• Major index distribution over permutation classes
• A linear time algorithm for consecutive permutation pattern matching
• Upper bounds for the Stanley-Wilf limit of 1324 and other layered patterns
• Excluded permutation matrices and the Stanley-Wilf conjecture
• Patterns in permutations and words.
• An efficient parallel algorithm for building the separating tree
• Generalized permutation patterns and a classification of the Mahonian statistics
• Parallel algorithms for separable permutations
• Order-preserving matching
• Wilf-equivalence for singleton classes
• The computational landscape of permutation patterns
• On Complexity of the Subpattern Problem
• Fast algorithms for finding pattern avoiders and counting pattern occurrences in permutations
• Finding small patterns in permutations in linear time
• Restricted permutations
• Generalized pattern avoidance