
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Implicit Generation of PatternAvoiding Permutations by Using Permutation Decision Diagrams
Yuma INOUE Takahisa TODA Shinichi MINATO
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E97A
No.6
pp.11711179 Publication Date: 2014/06/01
Online ISSN: 17451337
DOI: 10.1587/transfun.E97.A.1171
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications) Category: Keyword: patternavoiding permutations, generating algorithms, decision diagrams, πDD, experimental algorithms,
Full Text: PDF(1.3MB) >>Buy this Article
Summary:
Patternavoiding permutations are permutations where none of the subsequences matches the relative order of a given pattern. Patternavoiding 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 verylargescale integration (VLSI) circuit design, can be encoded into patternavoiding permutations. The generation of patternavoiding permutations is an important topic in efficient VLSI design and mathematical analysis of pattenavoiding permutations. In this paper, we present an algorithm for generating patternavoiding 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.

