Implicit Generation of Pattern-Avoiding Permutations by Using Permutation Decision Diagrams

Yuma INOUE  Takahisa TODA  Shin-ichi MINATO  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E97-A   No.6   pp.1171-1179
Publication Date: 2014/06/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E97.A.1171
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
pattern-avoiding permutations,  generating algorithms,  decision diagrams,  πDD,  experimental algorithms,  

Full Text: PDF(1.3MB)
>>Buy this Article

Pattern-avoiding permutations are permutations where none of the subsequences matches the relative order of a given pattern. Pattern-avoiding permutations are related to practical and abstract mathematical problems and can provide simple representations for such problems. For example, some floorplans, which are used for optimizing very-large-scale integration (VLSI) circuit design, can be encoded into pattern-avoiding permutations. The generation of pattern-avoiding permutations is an important topic in efficient VLSI design and mathematical analysis of patten-avoiding permutations. In this paper, we present an algorithm for generating pattern-avoiding permutations, and extend this algorithm beyond classical patterns to generalized patterns with more restrictions. Our approach is based on the data structure πDDs, which can represent a permutation set compactly and has useful set operations. We demonstrate the efficiency of our algorithm by computational experiments.