TCS-TR-B-14-9Date: Tue Feb 25 19:24:23 2014 Title: Master's Thesis: Generating PiDDs for Indexing Permutation Classes with Given Permutation Patterns Authors: Yuma Inoue Contact:
Abstract. Permutation is a basic concept in elementary combinatorics and discrete mathematics. Permutations appear in various problems such as sorting, ordering, matching, coding and many other real-life situations. Permutations are also important in group theory since it corresponds to a bijective function and generates symmetric groups. Permutation pattern is an important topic about permutations in which many researchers are interested. A permutation pattern occurs in a permutation if there is a subsequence of the permutation with the same relative order as the pattern. Otherwise, a permutation avoids a permutation pattern. Permutation patterns 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 designs, can be encoded as pattern-avoiding permutations. On the other hand, strong Wilf-equivalence has been proposed for analysis of permutation classes with permutation patterns. The generation of permutation classes with given permutation patterns is therefore an important topic in efficient VLSI design and mathematical analysis of permutation patterns. In this thesis, we present an algorithm for generating pattern-avoiding permutations, and extend this algorithm beyond classical patterns to generalized patterns with more restrictions. Moreover, we present an algorithm for generating permutations in which a pattern s occurs exactly k times. Our approach is based on Permutation Decision Diagrams (PiDDs), a data structure which can represent permutation sets compactly and support various set operations. We demonstrate the efficiency of our algorithms by computational experiments. ©Copyright 2014 Authors |