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

DOI10.1016/J.DAM.2019.04.014MaRDI QIDQ2274076zbMATH OpenOpenAlexWikidataFDO

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)

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

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)

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.

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

Cites work

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

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

Describes a project that uses

Uses Software

• OEIS
• InsEnc

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)