More restrictive Gray codes for some classes of pattern avoiding permutations. (English) Zbl 1202.68271
Summary: In a recent article [“Combinatorial Gray codes for classes of pattern avoiding permutations”, Theor. Comput. Sci. 396, No. 1–3, 35–49 (2008; Zbl 1138.68042)], W. M. B. Dukes, M. F. Flanagan, T. Mansour, and V. Vajnovszki present Gray codes for several families of pattern avoiding permutations. In their Gray codes two consecutive objects differ in at most four or five positions, which is not optimal. In this paper, we present a unified construction in order to refine their results (or to find other Gray codes). In particular, we obtain more restrictive Gray codes for the two Wilf classes of Catalan permutations of length \(n\); two consecutive objects differ in at most two or three positions which is optimal for \(n\) odd. Other refinements have been found for permutation sets enumerated by the numbers of Schröder, Pell, even index Fibonacci numbers and the central binomial coefficients. A general efficient generating algorithm is also given.
MSC:
| 68R05 | Combinatorics in computer science |
| 05A05 | Permutations, words, matrices |
| 68W05 | Nonnumerical algorithms |
Keywords:
algorithms; Gray code; pattern avoiding permutation; generating algorithm; Catalan numbers; Schröder numbers; central binomial coefficientsCitations:
Zbl 1138.68042References:
| [1] | Akl, S. G., A new algorithm for generating derangements, BIT, 20, 2-7 (1980) · Zbl 0432.68048 |
| [2] | Baril, J.-L., Gray code for permutations with a fixed number of cycles, Discrete Math., 30, 13, 1559-1571 (2007) · Zbl 1128.90039 |
| [3] | Baril, J.-L.; Vajnovszki, V., Gray code for derangements, Discrete Appl. Math., 140, 207-221 (2004) · Zbl 1044.05002 |
| [4] | Barcucci, E.; Del Lungo, A.; Pergola, E.; Pinzani, R., A methodology for the enumeration of combinatorial objects, Discrete J. Difference Equations Appl., 5, 435-490 (1999) · Zbl 0944.05005 |
| [5] | Barcucci, E.; Del Lungo, A.; Pergola, E.; Pinzani, R., From Motzkin to Catalan permutations, Discrete Math., 217, 1-3, 33-49 (2000) · Zbl 0965.05004 |
| [6] | Barcucci, E.; Bernini, A.; Poneti, M., From Fibonacci to Catalan permutations, PuMA, 17, 1-2, 1-17 (2006) · Zbl 1224.05020 |
| [7] | Bauslaugh, B.; Ruskey, F., Generating alternating permutations lexicographically, BIT, 30, 17-26 (1990) · Zbl 0692.68026 |
| [8] | Bernini, A.; Grazzini, E.; Pergola, E.; Pinzani, R., A general exhaustive generation algorithm for Gray structures, Acta Inform., 44, 5, 361-376 (2007) · Zbl 1127.68113 |
| [9] | Bona, M., Combinatorics of Permutations (2004), Chapman & Hall · Zbl 1052.05001 |
| [10] | Chow, T.; West, J., Forbidden sequences and Chebyshev polynomials, Discrete Math., 204, 119-128 (1999) · Zbl 0932.05007 |
| [11] | Dukes, W. M.B.; Flanagan, M. F.; Mansour, T.; Vajnovszki, V., Combinatorial Gray codes for classes of pattern avoiding permutations, Theoret. Comput. Sci., 396, 35-49 (2008) · Zbl 1138.68042 |
| [12] | Effler, S.; Ruskey, F., A CAT algorithm for generating permutations with a fixed number of inversions, Inform. Process. Lett., 86, 107-112 (2003) · Zbl 1173.68587 |
| [13] | O. Guibert, Combinatoire des permutations à motifs exclus en liaison avec mots, cartes planaires et tableaux de Young, PhD thesis, Universit’e Bordeaux 1, 1995; O. Guibert, Combinatoire des permutations à motifs exclus en liaison avec mots, cartes planaires et tableaux de Young, PhD thesis, Universit’e Bordeaux 1, 1995 |
| [14] | Johnson, S. M., Generation of permutations by adjacent transpositions, Math. Comp., 17, 282-285 (1963) · Zbl 0114.01203 |
| [15] | Juarna, A.; Vajnovszki, V., Some generalizations of a Simion-Schmidt bijection, Comput. J., 50, 574-580 (2007) |
| [16] | Korsh, J. F., Constant time generation of derangements, Inform. Process. Lett., 90, 4, 181-186 (2004) · Zbl 1171.05301 |
| [17] | Korsh, J. F., Loopless generation of up-down permutations, Discrete Math., 240, 1-3, 97-122 (2001) · Zbl 1020.05004 |
| [18] | Kremer, D., Permutations with forbidden subsequences and a generalized Schröder number, Discrete Math., 218, 1-3, 121-130 (2000) · Zbl 0949.05003 |
| [19] | Roelants van Baronaigien, D.; Ruskey, F., Generating permutations with given ups and downs, Discrete Appl. Math., 36, 1, 57-65 (1992) · Zbl 0790.05001 |
| [20] | F. Ruskey, U. Taylor, Fast generation of restricted classes of permutations, Manuscript, 1995; F. Ruskey, U. Taylor, Fast generation of restricted classes of permutations, Manuscript, 1995 |
| [21] | Simion, R.; Schmidt, F. W., Restricted permutations, European J. Combin., 6, 383-406 (1985) · Zbl 0615.05002 |
| [22] | Trotter, H. F., PERM (Algorithm 115), Comm. ACM, 5, 8, 434-435 (1962) |
| [23] | Vajnovszki, V., Gray visiting Motzkins, Acta Inform., 38, 793-811 (2002) · Zbl 1018.05002 |
| [24] | Vajnovszki, V., A loopless algorithm for generating the permutations of a multiset, Theoret. Comput. Sci., 307, 415-431 (2003) · Zbl 1081.68064 |
| [25] | Walsh, T., Gray codes for involutions, J. Combin. Math. Combin. Comput., 36, 95-118 (2001) · Zbl 0979.68046 |
| [26] | West, J., Generating trees and the Catalan and Schröder numbers, Discrete Math., 146, 247-262 (1994) · Zbl 0841.05002 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
