The search functionality is under construction.
The search functionality is under construction.

Author Search Result

[Author] Yuma INOUE(1hit)

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

    Yuma INOUE  Takahisa TODA  Shin-ichi MINATO  

     
    PAPER

      Vol:
    E97-A No:6
      Page(s):
    1171-1179

    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.