More restrictive Gray codes for some classes of pattern avoiding permutations |
| |
Authors: | Jean-Luc Baril |
| |
Affiliation: | LE2I UMR-CNRS 5158, Université de Bourgogne, B.P. 47 870, 21078 Dijon Cedex, France |
| |
Abstract: | In a recent article W.M.B. Dukes, M.F. Flanagan, T. Mansour, V. Vajnovszki, Combinatorial Gray codes for classes of pattern avoiding permutations, Theoret. Comput. Sci. 396 (2008) 35-49], Dukes, Flanagan, Mansour and 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. |
| |
Keywords: | Algorithms Gray code Pattern avoiding permutation Generating algorithm Catalan numbers Schrö der numbers Central binomial coefficients |
本文献已被 ScienceDirect 等数据库收录! |
|