Exhaustive generation for permutations avoiding (colored) regular sets of patterns

DOI10.1016/J.DAM.2019.04.014zbMATH Open1419.05007arXiv1809.00742OpenAlexW2892050462WikidataQ127926922 ScholiaQ127926922MaRDI QIDQ2274076FDOQ2274076

Authors: Phan Thuan Do, Thi Thu Huong Tran, Vincent Vajnovszki 

Publication date: 19 September 2019

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Abstract: Despite the fact that the field of pattern avoiding permutations has been skyrocketing over the last two decades, there are very few exhaustive generating algorithms for such classes of permutations. In this paper we introduce the notions of regular and colored regular set of forbidden patterns, which are particular cases of right-justified sets of forbidden patterns. We show the (colored) regularity of several sets of forbidden patterns (some of them involving variable length patterns) and we derive a general framework for the efficient generation of permutations avoiding them. The obtained generating algorithms are based on succession functions, a notion which is a byproduct of the ECO method introduced in the context of enumeration and random generation of combinatorial objects by Barcucci et al. in 1999, and developed later by Bacchelli et al. in 2004, for instance. For some classes of permutations falling under our general framework, the corresponding counting sequences are classical in combinatorics, such as Pell, Fibonacci, Catalan, Schr"oder and binomial transform of Padovan sequence.

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

Recommendations

• Right-justified characterization for generating regular pattern avoiding permutations
• Combinatorial Gray codes for classes of pattern avoiding permutations
• Fast algorithms for finding pattern avoiders and counting pattern occurrences in permutations
• A generating tree for permutations avoiding the pattern \(122^+3\)
• scientific article; zbMATH DE number 2188398

zbMATH Keywords

ECO methodpattern avoiding permutationexhaustive generating algorithmright-justified forbidden patternsuccession function

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15)

Cites Work

• Title not available (Why is that?)
• Finding regular insertion encodings for permutation classes
• The art of computer programming. Volume 4A. Combinatorial algorithms. Part 1.
• Patterns in permutations and words.
• Generating trees and the Catalan and Schröder numbers
• ECO:a methodology for the enumeration of combinatorial objects
• Exhaustive generation of combinatorial objects by ECO
• ECO-generation for \(p\)-generalized Fibonacci and Lucas permutations
• Combinatorial Gray codes for classes of pattern avoiding permutations
• Forbidden subsequences and Chebyshev polynomials
• From Fibonacci to Catalan permutations
• Right-justified characterization for generating regular pattern avoiding permutations

Cited In (4)

• Coloured permutations containing and avoiding certain patterns
• Combinatorial generation via permutation languages. I: Fundamentals
• Right-justified characterization for generating regular pattern avoiding permutations
• Combinatorial Gray codes for classes of pattern avoiding permutations

Uses Software

• InsEnc
• OEIS

This page was built for publication: Exhaustive generation for permutations avoiding (colored) regular sets of patterns

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2274076)