TCS-TR-A-14-78

Date: Mon Oct 6 21:33:52 2014

Title: Generating Sets of Permutations with Pattern Occurrence Counts Using PiDDs

Authors: Yuma Inoue, Takahisa Toda and Shin-ichi Minato

Contact:

First name: Shin-ichi
Last name: Minato
Address: Graduate School of Information Science and Technology, Hokkaido University, North 14 West 9, Sapporo, 060- 0814, Japan
Email: minato@ist.hokudai.ac.jp

Abstract. A pattern occurs in a permutation if there is a subsequence of the permutation with the same relative order as the pattern. For mathematical analysis of permutation patterns, strong Wilf-equivalence has been defined as the equivalence between permutation patterns based on the number of occurrences of a pattern. In this paper, we present an algorithm for generating permutations of length n in which a pattern occurs exactly k times. Our approach is based on permutation decision diagrams (PiDDs), which can represent and manipulate permutation sets compactly and efficiently. According to computational experiments, we gives a conjecture: all strongly Wilf-equivalent classes are trivial.