TCS -TR-B-14-9

TCS Technical Report

Master’s Thesis: Generating PiDDs for Indexing
Permutation Classes with Given Permutation Patterns

byYuma Inoue

Division of Computer Science
Report Series B
February 25, 2014

Hokkaido University
Graduate School ofInformation Science and Technology
Email:

yuma@mx-alg.ist.hokudai.ac.jp

Phone:+81-011-706-7681

Fax:+81-011-706-7681

Master’s Thesis
平成 25 年度 修士学位論文

Generating PiDDs for Indexing Permutation Classes
with Given Permutation Patterns

π DD を用いたパターンに基づく順列クラスの列挙索引化

Yuma Inoue井上

祐馬

Laboratory for Algorithmics, Division of Computer Science
Graduate School of Information Science and Technology
Hokkaido University
北海道大学 大学院情報科学研究科
コンピュータサイエンス専攻 アルゴリズム研究室

February 25, 2014

Contents
1

Introduction

4

1.1

Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4

1.2

Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

1.3

Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

1.4

Thesis Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6Preliminaries

7

2.1

Permutations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

2.2

Permutation Patterns . . . . . . . . . . . . . . . . . . . . . . . . . . .

82.3

π DDs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9

2.3.1

ZDDs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9

2.3.2

π DDs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

11

2.4

Multiset of Permutations . . . . . . . . . . . . . . . . . . . . . . . . .

12

2.5

π DD Vectors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

12Main Results

16

Generation of Classical Pattern-Containing Permutations . . . . . . . .

16

3.1.1

Construction of B . . . . . . . . . . . . . . . . . . . . . . . .

18

3.1.2

Construction of C . . . . . . . . . . . . . . . . . . . . . . . .

18

3.1.3

Construction of A . . . . . . . . . . . . . . . . . . . . . . . .

19

3.2

Generation of Vincular Pattern-Containing Permutations . . . . . . . . .

20

3.3

Generation of Bivincular Pattern-Containing Permutations . . . . . . . .

21

3.4

Generation of Pattern-Avoiding Permutations . . . . . . . . . . . . . .

21

2

3
3.1

3.5

3.4.1

Generation Algorithm for all n-Permutations. . . . . . . . . .

22

3.4.2

Summary of Generation Algorithm for Avn (σ ). . . . . . . . .

23

Generation of Permutations with Pattern Occurrence Counts . . . . . . .

24

3.5.1

Generation Algorithm for Pn,σ . . . . . . . . . . . . . . . . . .

24

3.5.2

(k)
Generation Algorithm for Fn (σ )

24

3.5.3

(k)
Summary of Generation Algorithm for Fn (σ )1

. . . . . . . . . . . . . . . .
. . . . . . . . .

25

4

5

Experimental Results

26

4.1

Results for Classical Pattern-Avoiding Permutations . . . . . . . . . . .

27

4.2

Results for Vincular and Bivincular Patterns . . . . . . . . . . . . . . .

28

4.3

Results for Permutations with Pattern Occurrence Counts . . . . . . . .

30Conclusion

33

2

Summary
Permutation is a basic concept in elementary combinatorics and discrete mathematics.
Permutations appear in various problems such as sorting, ordering, matching, coding andmany other real-life situations. Permutations are also important in group theory since itcorresponds 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 subsequenceof 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 withpermutation 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 apattern σ occurs exactly k times. Our approach is based on Permutation Decision Diagrams (PiDDs, or π DDs), a data structure which can represent permutation sets compactly
and support various set operations. We demonstrate the efficiency of our algorithms bycomputational experiments.

3

Chapter 1

Introduction
Permutation is a mathematical concept, which appears in various mathematical and practical problems. For example, sorting, ordering, matching, coding, and so on can be described as permutation problems. Permutations also appear in group theory. Permutations
correspond to a bijective function between two groups and generates symmetric groups.
Permutation pattern is the important topic in the research area of permutations. A
permutation pattern σ occurs in a permutation π if there is a subsequence in π which isorder isomorphic to σ . Two numerical sequences a = a1 a2 . . . an and b = b1 b2 . . . bm areorder isomorphic if a and b have the same length and satisfy ai < a j if and only if bi < b j
for all i, j. Conversely, π avoids σ if σ does not occur in π . Permutations that avoid apattern σ are called σ -avoiding permutations.

1.1

BackgroundResearch on pattern-avoiding permutations dates back to stack sort, which was proposed by Knuth in [13]. In stack sort, we can use a single stack to sort elements. Knuth
showed that a permutation is stack sortable if and only if it is a 231-avoiding permutation. Several variations of the stack sorting problem, such as the twice stack sorting
problem [22], and the double-ended queue sorting problem [18], have been considered,and pattern-avoiding permutations were developed in that context.
After pattern-avoiding permutations were first studied, many researchers worked oncomputing the number of permutations that avoid given patterns. For example, 1342avoiding permutations have been enumerated by a mathematical approach [5], and 1324avoiding permutations have been counted by computer programs [15]. Moreover, therelations between classes of pattern-avoiding permutations have also been examined. Twopatterns σ1 and σ2 are Wilf-equivalent if the number of n-permutations which avoid σ1
is same as the number of n-permutations for σ2 for all positive integers n. In [20], thenontrivial Wilf-equivalence between 4132-avoiding and 3142-avoiding was discovered.
(k)More generally, two patterns σ1 and σ2 are strongly Wilf-equivalent [11] if |Fn (σ1 )| =4

(k)|Fn (σ2 )| for all non-negative integers n and k, where |S| denotes the cardinality of a set(k)
S and Fn (σ ) denotes the set of permutations of length n in which σ occurs exactly ktimes. Unfortunately, few results are known about strong Wilf-equivalence, as stated in
the survey [21]. The generation of permutation classes with pattern occurrence counts
can contribute to not only discoveries of new strongly Wilf-equivalent classes, but also
identifications of bijective functions between such classes.
Relations between pattern-avoiding permutations and mathematical problems have also
been studied actively [8, 10]. In particular, Yao et al. [24] discovered a bijection between
mosaic floorplans and Baxter permutations, which are generalized pattern-avoiding permutations, and Ackerman et al. [1] proposed a simple encoding and decoding between
these. A floorplan is a topological partition of a rectangle into multiple rectangles, andhave practical applications in areas such as VLSI design. Mosaic floorplans are a subclassof floorplans. Bijections between other pattern-avoiding permutations and other floorplan classes are also discussed in [1, 19]. Storing all pattern-avoiding permutations ina database is equivalent to preparing a database of floorplans. Database queries such as
searching by criteria and random sampling are useful for VLSI design. Therefore, generating pattern-avoiding permutations could contribute to solving practical problems.

1.2 Contributions
In this thesis, we provide a practically efficient algorithm for generating pattern-avoiding
permutations. Furthermore, we extend our algorithm to handle some generalized patterns,
such as vincular and bivincular patterns. We also present an algorithm for generating(k)Fn (σ ) based on the above algorithms. Using experiments, we measure the performanceof our algorithms and compare with a naive method. In the experiments, we find somepatterns that are potentialy strongly Wilf-equivalent.
Our algorithms are based on Permutation Decision Diagrams (PiDDs, or π DDs), adata structure for compactly representating sets of permutations [17]. These diagrams not
only achieve high compression of sets of permutations, but also support rich algebraic
set operations such as union and intersection. The computation time of these operations
depends on the size of the π DDs and not on the number of permutations they represent. If
the π DD is small, computation is fast independently of the number of permutations. Thisis a key benefit of our algorithms given that most previous generation algorithms focusedon polynomial-delay algorithms, whose overall time complexity depends on the numberof solutions.

1.3

Related Work

Wilf [23] provided an amortized polynomial-delay algorithm that generates all permutations avoiding the identity pattern (i.e. 12 . . . n), and posed the question about thecomplexity of generation for other patterns. Bose et al. [6] proved that the enumeration5

problem for pattern-avoiding permutations is #P-complete. Theoretically efficient generation algorithms for some particular patterns have been proposed [9]. On the other hand,as an instance of practical results, Albert [2] develops PermLab, which is software enumerating and listing pattern-avoiding permutations.
Our goal differs from the above results from the following viewpoints.
• Implicit generation:
For applications such as Wilf-equivalence and floorplan databases, it is sufficient tostore some information equivalent to all pattern-avoiding permutations. We do nothave to list them explicitly.
• General patterns:
We want to analyze as many patterns as possible.
• Practical efficiency:
Theoretically fast algorithms are important. However, for practical applications,experimentally fast algorithms are also required.
• Enumeration with occurrences:(0)
The generation problem for pattern-avoiding permutations, i.e. Fn (σ ), has beenstudied extensively. However, as far as the author knows, no algorithm generating(k)Fn (σ ) for any non-negative integer k has been proposed.

1.4 Thesis Structure
The rest of this thesis is organized as follows. Chapter 2 introduces permutation patterns and π DDs. Chapter 3 presents our generation algorithms. Chapter 4 shows experimental results. The results include some candidates of strongly Wilf-equivalent classes.
Chapter 5 concludes this thesis.

6Chapter 2

Preliminaries
In this chapter, we give some notations and definitions for permutation patterns. We
also define some generalized patterns, which have more restrictions besides order isomorphism. We also introduce π DDs and its extension for multisets of permutations. Our
generation algorithms, which will be described in Chapter 3, are based on these data structures.

2.1

Permutations

A permutation of length n (n-permutation for brevity) is a bijection from {1, 2, ..., n} toitself. Hereafter, we write permutations in one line as π = π (1)π (2) . . . π (n), and denote
πi = π (i). The k-prefix of π denotes the first k numbers in π , and the k-suffix of π denotes
the last k numbers in π . For example, π = 4312 is a 4-permutation, π3 = 1, and the 2-prefixof π is 43. An element πi in π is fixed if πi = i holds.
Multiplication over permutations x and y is defined as x · y = yx1 yx2 . . . yxn , which isapplying y after x. Note that the leftmost permutation is applied first. For example, let
x = 45213 and y = 41352, then x·y = 52143 (see Figure 2.1). Note that multiplication overpermutations is non-commutative. We denote by en the identity permutation of length n,
where en satisfies en (i) = i for each 1 ≤ i ≤ n.

45213 ・ 41352 = 52143
1
2
3
4
5

1
2
3
4
5

1
2
3
4
5

1
2
3
4
5

1
2
3
4
5

1
2
3
4
5

Figure 2.1. An example of multiplication of permutations.

7

Figure 2.2. Decomposition of 54213 into transpositions.

In this thesis, we use the multiplication x · y in order to permute the numbers in yaccording to the order of numbers in x, that is, yi is placed in the kth position with xk = i.
We call this operation the rearrangement of y according to x. For example, let r = 54321,
which is the reverse of e5 , and π = π1 π2 π3 π4 π5 . Then we obtain r · π = π5 π4 π3 π2 π1 ,which is the reverse of π .
A transposition is a permutation that exchanges only two elements. More precisely,a transposition τi, j is a permutation such that τi, j (i) = j, τi, j ( j) = i, and τi, j (k) = k for
all other numbers k. Any n-permutation can be uniquely represented as the product ofat most n − 1 transpositions based on a straight selection sorting algorithm [14]. Thisalgorithm repeatedly swaps the value k and the kth element from right to left. For example,
consider the decomposition of the permutation 54213 into a product of transpositions(Figure 2.2). The 5th element of 54213 is 3, hence we exchange 5 and 3, and obtain
54213 = 34215 · τ3,5 . Since the 4th element of 34215 is 1, we then obtain 54213 = 31245 ·τ1,4 · τ3,5 . Repeating this procedure, we finally obtain 54213 = τ1,2 · τ2,3 · τ1,4 · τ3,5 .

2.2

Permutation Patterns

A permutation π contains a permutation σ , or σ occurs in π if there is at least one
subsequence in π which is order isomorphic to σ , where the subsequence need not consistof consecutive numbers in π . In other words, let l be the length of σ . Then, π contains σ if
there are indexes 1 ≤ i1 < i2 < . . . < il ≤ n such that πix < πiy if and only if σx < σy , for all
pairs of x and y. Such σ is called a pattern. For example, the permutation 4213 contains
the pattern 312 because 423 and 413 are order isomorphic to the pattern. Conversely, π
avoids σ if π does not contain σ .
The above pattern is called a classical pattern because some generalizations have been
proposed. For example, the vincular pattern, which is also called the generalized pattern,
is a well-known generalization [3]. While the defining restriction in classical patterns isorder isomorphism, vincular patterns additionally have another restriction: adjacency ofelement positions in the permutation. We use the underline notation to represent adjacencies. If the ith and the (i + 1)th elements are underlined, the corresponding numbers in
the permutation must be adjacent. For example, we consider the permutation 4213 andthe vincular pattern 312. Both 423 and 413 are order isomorphic to 312, but 423 does
not match 312 because the second and third elements are not adjacent in the permutation.
8

In contrast, 413 matches the pattern because 1 and 3 are adjacent in 4213. Thus, 4213
contains 312.
Vincular patterns have been extended to bivincular patterns [7]. A bivincular patternis restricted by adjacency of positions and additionally by consecutiveness of values. We
use a two-line form with bars and underlines to represent bivincular patterns. The firstrow represents consecutiveness and an identical order, and the second row represents ad123
jacencies and a relative order. For example, the bivincular patternrepresents a pattern
312
where the 1st and the 2nd smallest values must be consecutive, the 2nd and the 3rd elements in a subsequence must be adjacent in a permutation, and the relative order must123
match 312. Thus, the permutation 4213 avoids. Indeed, both subsequences 423 and312
413 are order isomorphic to 312 but 423 does not match the bivincular pattern because
2 and 3 are not adjacent in the permutation, and 413 also does not match the bivincularpattern because 1 and 3 are not consecutive.
The pattern occurrence count of σ in π is the number of distinct subsequences in the
permutation π which are order isomorphic to the pattern σ . For example, the pattern(k)occurrence count of 312 in 4213 is 2 as described above. Hereafter, Fn (σ ) denotes theset of n-permutations in which σ occurs exactly k times. Two patterns σ1 and σ2 are Wilfequivalent if they have the same number of n-permutations which avoid the patterns, i.e.,(0)(0)|Fn (σ1 )| = |Fn (σ2 )| holds for all positive integers n. More generally, two patterns σ1(k)(k)
and σ2 are strongly Wilf-equivalent if |Fn (σ1 )| = |Fn (σ2 )| holds for all non-negative
integers n and k.
The problem considered in this thesis can be stated as follows: given a positive integer(k)n and a pattern σ , implicitly generate Fn (σ ) for all non-negative integers k.

2.3

π DDs

A Permutation Decision Diagram (PiDD, or π DD) [17] is a data structure which canonically represents and efficiently manipulates a set of n-permutations. The efficiency of ouralgorithms is based on the compact representation and rich set operations of π DDs. The
structure of π DDs is based on Zero-suppressed Binary Decision Diagrams (ZDDs) [16],which are decision diagrams for sets of combinations (families of sets).

2.3.1 ZDDs
A ZDD is derived by reducing a binary decision tree. Figure 2.3 shows the ZDD forthe family of sets {{a, b}, {a, c}, {c}}. A ZDD has five components: internal nodes withan item label, 0-edges, 1-edges, the 0-terminal node, and the 1-terminal node.
A ZDD forms a connected DAG (Directed Acyclic Graph) with a single root node.
Each node except the two terminal nodes has exactly one 0-edge and one 1-edge. Each
9

a

0
0
0

c

b

1

0

c

c

1 0

a

1

1 0

b
1 0

0

reduce

1

c

1

1

c 1

0

0 1 0 0 0 1 1 0

1

b
0

0

1

Figure 2.3. A binary decision tree and a ZDD for a set of combinations.

xx
0 1 0 1

x
0

x
1

0

1

F0
0

F0

F1

F0

F1

(1) merging rule

F0(2) deletion ruleFigure 2.4. Two reduction rules on ZDDs.

path represents a combination of items: if a 1-edge originates from a node with label x,
the combination contains x, while a 0-edge from x means that the combination excludes x.
If a path reaches the 1-terminal node, the combination represented by the path is in theset represented by the ZDD. On the other hand, if a path reaches the 0-terminal node, thecombination is not in the set. For a node N, we call the subgraph pointed to by its 0-edge
the left subgraph of N and the subgraph pointed to by its 1-edge the right subgraph of N
for convenience. Then, we can consider that the 0-terminal node represents an empty set,the 1-terminal node represents a singleton of a combination which has no item, and a nodewith label x represents the union of the left subgraph and the right subgraph whose eachcombination added the item x to.
A ZDD is canonical, and often compact representation if we fix the order of the items
and apply the following two reduction rules:(1) Merging rule: Share all nodes which have the same left subgraphs, the same right
subgraphs, and the same labels(2) Deletion rule: Delete all nodes whose 1-edge point directly to the 0-terminal node.
These rules are illustrated in Figure 2.4. In the worst-case scenario, the size of a ZDD(i.e. the number of nodes in a ZDD) can grow exponentially with respect to the number of
items. In many practical cases, though, ZDDs provide efficient compression.
In addition, ZDDs support efficient set operations such as union, intersection, and set
difference. Since these operations are realized by recursive algorithms with hash table
techniques, the computation time of these operations depends on the number of nodes in
the ZDDs, not on the cardinality of the sets they represent.
10

τ1,4

0

τ3,4
0
0

1

1 0 τ2,3

τ1,2

0

1
1

1

Figure 2.5. The π DD for {2143, 2431, 4321} = {τ1,2 · τ3,4 , τ1,2 · τ1,4 , τ2,3 · τ1,4 }.

2.3.2 π DDs
We introduce π DDs, which represent a set of n-permutations, by deriving them froma ZDD. As shown in Section 2.1, any permutation can be uniquely decomposed into a
product of transpositions. Hence, by assigning transpositions to nodes in a ZDD, eachpath in the ZDD represents a permutation. This is the basic idea of π DDs. We introduce
the order of transpositions < so that τx1 ,y1 < τx2 ,y2 is true if y1 > y2 holds, or y1 = y2 andx1 < x2 holds, and use this order as the fixed order in a π DD. In π DDs, the 0-terminal
node represents an empty set and the 1-terminal node represents a singleton of the identity permutation en . We obtain compact and canonical π DDs by applying the above two
reduction rules in the same way to ZDDs, and set operations are also available. Figure 2.5
shows an example of a π DD.
Table 2.1 shows the π DD operations used in this thesis. Here the Cartesian product of
π DDs differs from the usual Cartesian product of sets: the set of multiplications for all
pairs of permutations in one permutation set and those in the other permutation set. Whilethe union and set difference operations are available like ZDDs, the swap and Cartesian
product operations are unique to π DDs. In particular, the Cartesian product is very useful
because multiplications over permutations results in rearrangements. That is, by applying
the Cartesian product operator, we can simultaneously execute rearrangements of multiple
numerical sequences.
Table 2.1. π DD operations on two π DDs P and Q.

P.Top
P∩Q
P∪Q
P\Q
P · τx,y
P×Q

return the transposition τx,y by which the root node is labeled.
return intersection {π | π ∈ P and π ∈ Q}.
return union {π | π ∈ P or π ∈ Q}.
return difference {π | π ∈ P and π ∈/ Q}.
return swap {π · τx,y | π ∈ P}.
return Cartesian product {α · β | α ∈ P and β ∈ Q}.

11

2.4 Multiset of Permutations
In this section, we introduce some definitions and notations for multisets of permutations. Let P = ⟨P, f ⟩ be a multiset over P, where P is a permutation set and f : P → N is afunction. Here, f (π ) is the multiplicity of permutation π and we use the notation P(π ) instead of f (π ) for convenience. We define P ⊎ Q as the multiset sum of two multisets P and
Q, where (P ⊎ Q)(π ) = P(π ) + Q(π ) holds for all permutations π . Scalar multiplicationof an integer k and a multiset P is defined by k · P = ⟨P, k · f ⟩. Cartesian product of two
multisets P = ⟨P, f ⟩ and Q = ⟨Q, g⟩ is defined by P × Q = ⟨P × Q, h(π · π ′ ) = f (π ) · g(π ′ )⟩,where π ∈ P, π ′ ∈ Q, and P × Q means Cartesian product of permutation sets like that of
π DDs.
A set of permutations weighted by pattern occurrence counts can be represented by amultiset. Given a positive integer n and a pattern σ , Pn,σ = ⟨Sn , fσ ⟩ denotes the set of npermutations weighted by the pattern occurrence count of σ , i.e., fσ (π ) equals the patternoccurrence counts of σ in π . Our algorithm, which will be described in Section 3.5, first(k)generates Pn,σ , and then computes Fn (σ ) = {π | Pn,σ (π ) = k} from Pn,σ .

2.5

π DD Vectors

In this thesis, we want to handle multisets of permutations. But π DDs cannot represent multisets. To overcome this problem, we use π DD vectors, which were proposedin [12]. A π DD vector is a data structure for a multiset of permutations based on a binary
representation using multiple π DDs. A π DD vector consists of an array of π DDs. Let
M be the maximum multiplicity of a permutation in a given multiset. We denote a π DD
vector by ⃗P = (P0 , P1 , . . . , Pm ), where each Pi is a π DD and m = ⌊log M⌋. Let ⃗P(π ) be themultiplicity of π in ⃗P. If a permutation π is in Pi , the ith bit of the binary representationiof ⃗P(π ) is 1, and otherwise 0. In other words, ⃗P(π ) = ∑mi=0 2 · [π ∈ Pi ] holds, where [x]equals 1 if x is true, and otherwise 0. Figure 2.6 shows an example of a π DD vector. In
actuality, π DDs in a π DD vector share common subgraphs as illustrated in [12]. Thus,
more efficient compression can be expected.

π DD vectors have multiset operations. Table 2.2 shows some π DD vector operations
which were used in this thesis. Most operations in Table 2.2 were proposed in [12]. Un-⃗
Table 2.2. π DD operations on π DD vectors ⃗P and Q.

⃗⃗P ⊎ Q⃗P · τx,y⃗P.numberof(π )⃗⃗P × Q⃗ π ) holds.
Return multiset sum ⃗R such that ⃗R(π ) = ⃗P(π ) + Q(′
Return swap ⃗P = (P0 · τx,y , P1 · τx,y , . . . , Pm · τx,y ).
Return ⃗P(π ).
⃗ β ).
Return Cartesian product ⃗R such that ⃗R(α · β ) = ⃗P(α ) · Q(

12

P1

P2
τ2,4

0 0

τ3,4

1

0
τ1,2

1 0
1
{1342}

τ2,4

1

0

0 τ1,3

τ2,3

0

P0

0

1

τ1,2

1
1

0

1

Permutation (P2,P1,P0) Multiplicity

0 τ2,3

1342
2134
2143
4213
4132

1 1

0

(1,0,1)(0,1,1)(0,1,0)(0,1,0)(0,0,1)

5
3
2
2
1

1

{2134,2143,4213} {2134,4132,1342}

Figure 2.6. An example of a π DD vector.

fortunately, however, the Cartesian product operation of π DD vectors has not ever been
proposed. We introduce the Cartesian product operation.
Cartesian product operation between two π DDs P and Q was defined as follows ([17]):
P × Q = (P × Ql ) ∪ ((P × Qr ) · τx,y ),where Ql and Qr are the left and the right subgraphs of the root node of Q, respectively,and τx,y is the transposition associated with the root node of Q.
We extend Cartesian product to π DD vectors as follows:⃗ = (⃗P × Q⃗ L ) ⊎ ((⃗P × Q⃗ R ) · τx,y ),⃗P × Q
where multiset sum ⊎ and swap τx,y are π DD vector operations which were already defined⃗ can have distinct
in [12] as shown in Table 2.2. However, some Qi in the array of Q
L
R⃗⃗
transpositions in their root nodes. We need to define Q and Q , and τx,y appropriately.
We use τxs ,ys which is the smallest transposition in the root nodes of Q1 , Q2 , . . . , Qm ,where the order of transpositions is introduced in Section 2.3.2. For example, for theπ DD vector illustrated in Figure 2.6, τxs ,ys is τ2,4 because the transpositions on the root
nodes of P0 , P1 , and P2 are τ2,4 , τ3,4 , and τ2,4 , respectively, and the smallest transposition⃗ L and Q⃗ R as follows:
among them is τ2,4 . Here, we define QQ if Q .Top ̸= τ ,xs ,ysii⃗ L = (QL0 , QL1 , . . . QLm ), where QLi =QQl otherwise.
i0/ if Q .Top ̸= τ ,i
xs ,ys⃗ R = (QR0 , QR1 , . . . QRm ), where QRi =QrQ otherwise.
i

If the root node in Qi is not labeled by τx,y , it is equivalent to the π DD whose root node
has the label τx,y , Qi as the left subgraph, and the 0-terminal node as the right subgraph.
This implies correctness of the above definition.
13

We must also define the base case of the above recursion. The base case means every
root node of Qi is not labeled by a transposition, that is, each Qi consists only of a terminal node. Since each Qi consists only of the 0-terminal node or the 1-terminal node,⃗ n ) ≥ 0 and Q(⃗ π ) = 0 for the otheri.e. an empty set or a singleton of en , respectively, Q(e⃗ equals the scalar multiplication Q(e⃗ n ) · ⃗P. Here, we depermutations π hold. Then, ⃗P × Q
fine (kl kl−1 . . . k0 )2 as a binary representation of non-negative integer k, where l = ⌊log k⌋.
Algorithm 1 gives an algorithm for a scalar multiplication of a π DD vector based on themultiset sum of 2i · ⃗P = (0,/ . . . , 0/ , P , . . . , Pm ). In conclusion, Algorithm 2 shows how to| {z } 0icompute the Cartesian product of π DD vectors.
Algorithm 1 Scalar multiplication of a non-negative integer k = (kl kl−1 . . . k0 )2 and a π DD
vector ⃗P = (P0 , P1 , . . . , Pm ).
π DD vector ⃗R ← (0)/for i = 0 to l do
if ki = 1 then⃗R ← ⃗R ⊎ ⃗P
end if⃗P ← (0,/ P0 , P1 , . . . , Pm+i )end forreturn ⃗R14⃗ =Algorithm 2 Cartesian product of two π DD vectors ⃗P = (P0 , P1 , . . . , Pm′ ) and Q(Q0 , Q1 , . . . , Qm ).
{Calculate the smallest transposition.}{We suppose the 0-terminal node is labeled by τ0,0 and the 1-terminal node is labeledby τ1,1 for convenience.}transposition t ← τ0,0
for i = 0 to m do
if Qi .Top < t thent ← Qi .Top
end ifend for{Branch based on t.}
if t = τ0,0 then{Every Qi consists only of the 0-terminal node.}
return (0)/else if t = τ1,1 then{Every Qi consists only of the 0-terminal node or the 1-terminal node.}⃗
return Q.numberof(ePn) · ⃗
else{There is at least one Qi whose root node is not a terminal node.}for i = 0 to m do
if Qi .Top = t thenQLi ← Qli , QRi ← Qrielse
QLi ← Qi , QRi ← 0/
end ifend for⃗ L ) ⊎ ((⃗P × Q⃗ R ) · t)
return (⃗P × Q
end if15

Chapter 3

Main Results
In this chapter, we gives generation algorithms for pattern-containing permutations, patternavoiding permutations, and permutations with pattern occurrence counts. We also present
the extension for some general patterns.

3.1 Generation of Classical Pattern-Containing Permutations
Hereafter, unless otherwise noted, l denotes the length of a given pattern σ and Cn (σ )denotes the set of n-permutations that contain σ . The algorithm for generating Cn (σ ) is
sketched as follows. First, we generate all numerical sequences satisfying the following
conditions:• It is order isomorphic to σ .
• The elements in it are less than or equal to n.
()
The number of such numerical sequences is nl . For example, if we suppose that n = 5
and σ = 312, then there are ten such numerical sequences: 312, 412, . . . , 534. Next, we
generate all n-permutations such that the above numerical sequences appear as a subsequence. In order to do this, it is sufficient to embed the numerical sequences in sequencesof length n without changing their order. For example, the numerical sequence 524 canbe embedded in the following ways: 524 ∗ ∗, 52 ∗ 4∗, . . . , ∗ ∗ 524. Here, we assign otherpositive integers to the ∗ positions in any order. Then, we obtain all n-permutations whichhave 524 as their subsequence: 52413, 52431, 52143, 52341, . . ., 13524, 31524. Since allorder isomorphic sequences are embedded in all possible positions, this process generates
Cn (σ ).
Replacing all numerical sequences in the above process by permutations, this process
is described as the three steps as follows:
A. Generate all permutations whose l-prefix is ordered in increasing order,16n = 4, σ = 312, l = 3
Step A {1234, 1243, 1342, 2341}
Step B {3124, 4123, 4132, 4231}
Step C {3124, 3142, 3412, 4312,
4123, 4132, 4312, 3412,
4132, 4123, 4213, 2413,
4231, 4213, 4123, 1423 }{3124, 3142,
3412, 4312,
4123, 4132,
Remove4213, 2413,
duplications
4231, 1423 }= C4(312)
Figure 3.1. The process of generating C4 (312).

B. Rearrange the l-prefix of each permutation which was generated in step A into theorder isomorphic to σ ,()C. Distribute the l-prefix of each permutation π which was generated in step B over nl
possible positions in π .
()Figure 3.1 shows the process of generating C4 (312). Step A generates all nl combinations in the l-prefix of the permutations. Step B rearranges the l-prefix of each permutation
into the numerical sequence order isomorphic to σ . All possible numerical sequences order isomorphic to σ appear in the l-prefix of the permutations which are generated in step()
B. The distribution by step C generates all permutations π such that at least one of nl
subsequences in π exactly matches one of the numerical sequences order isomorphic to
σ . They may be some duplications. But we do not have to consider the duplications whenusing π DDs because π DDs represent the set, not multiset.
Steps B and C involve the rearrangements of multiple permutations. This means that
this process can be done by Cartesian products of π DDs as shown in Section 2.3.2. Let A
denote the π DD for permutations which are generated in step A, and let B and C denotethe π DDs for the rearrangements which correspond to steps B and C, respectively. Notethat the permutations represented in B are not the permutations obtained after step B byrearranging those in A. The permutations in B are the permutations as operations to apply
those in A. The same applies to C. Then, Cn (σ ) can be obtained by computing C × B × A(Figure 3.2). Note that the Cartesian products must be applied in the reverse order of thethree steps we execute, that is, we first apply B to A and then apply C to the result of thefirst application.
We show the method for the construction of A last because it is similar to the construction of C but more complicated.

17n = 4, σ = 312, l = 3

×= C4(312)

×{3124, 3142,
3412, 4312,{1234, 1243,{1234, 1243,
× {3124} ×= 4123, 4132,
1342, 2341}
1423, 4123}
4213, 2413,
4231, 1423 }Figure 3.2. Cartesian product in generating C4 (312).

3.1.1 Construction of B
In order to rearrange the l-prefix of all permutations in A into the order isomorphic to
σ , we define B to be the π DD consisting only of the permutation whose l-prefix is σ and(n−l)-suffix is fixed. To construct this π DD, we first decompose σ into a product of transpositions as given in Section 2.1. The π DD forms one path based on this decomposition,and can be easily constructed in a bottom-up fashion.

3.1.2

Construction of C

We define C to be the π DD for the set of n-permutations π such that there are l indixes
1 ≤ p1 < p2 < . . . < pl ≤ n with π pi = i. This means that each permutation in C must havethe numerical sequence 12 . . . l as a subsequence. There is a simple method to construct
C. First, for each n-permutation which satisfies the above condition, we construct one
π DD like the construction of B. And then, we take the union of the π DDs. This algorithm
is simple and easy to implement. (However,this is not efficient because it must repeat)nconstructions and union operations l times.
Our idea to reduce (theis based on Pascal’s rule, which is the) number(n−1) of(operations)nn−1
combinatorial identity l = l + l−1 . Let Posi, j be the set of all n-permutations π
containing at least one subsequence πl1 πl2 . . . πl j satisfying the following two conditions:
1. 1 ≤ l1 < l2 < . . . < l j ≤ i.
2. πl1 πl2 . . . πl j = 12 . . . j,
It is obvious that C is the π DD for Posn,l . If we can calculate Posi, j using Posi−1, j andPosi−1, j−1 as in the identity above, we can obtain C with only O(nl) operations. In orderto make this idea work, we restrict Posi, j with the additional condition as follows:
3. For each i + 1 ≤ x ≤ n, x is fixed, i.e., πx = x.

18Here, we can partition Posi, j into the two sets: the set including π with πi ̸= j and theother set. The former set equals Posi−1, j , and the latter one can be obtained by assigning j
to the ith position of permutations in Posi−1, j−1 . Hence, if Pi, j denotes the π DD for Posi, j ,this is achieved by Pi−1, j−1 · τi, j because the ith element is i from the third condition and j
is not assigned yet. Thus, Pi, j = Pi−1, j ∪ Pi−1, j−1 · τi, j holds. The dynamic programming
for this recursion is encoded in Algorithm 3.
Algorithm 3 Construct C.
P0,0 ← π DD for {en }for i = 1 to n do
for j = 0 to l do
if j > 0 thenPi, j ← Pi−1, j ∪ Pi−1, j−1 · τi, j
else
Pi, j ← Pi−1, j
end ifend forend forreturn Pn,l3.1.3 Construction of A
As shown in Section 3.1, A is the π DD for the set of all n-permutations whose l-prefixis ordered in increasing order. More precisely, a permutation π in A satisfies 1 ≤ π1 <π2 < . . . < πl ≤ n.
We can obtain A by repeating assignments in a similar way to the construction of C.
However, this does not work if we assign elements in increasing order. In order to assign
v to pth position by τ p,v , p must be fixed to pth position. But given that p ≤ v, othertranspositions could result in p being in another position. In the construction of P p,v ,there is no such problem because after τ p,v assigns v to pth position, there are no further
assignments to vth position due to v ≤ p. Therefore, we reverse the order of assignments
in order to fix the position of elements which will be used in the future. Let Inci, j be theset of all n-permutations satisfying the following conditions:
1. i + 1 ≤ π j+1 < π j+2 < . . . < πl ≤ n,
2. For each 1 ≤ x ≤ j, x is fixed, i.e., πx = x.
These conditions mean that for each permutation π in Inci, j , the (l − j)-suffix of the lprefix of π is already used and the j-prefix of the l-prefix of π is fixed. We executethe constructions from Incn,l = {en } to Inc0,0 . If Ii, j denotes the π DD for Inci, j , then19

Ii, j = Ii+1, j ∪ Ii+1, j+1 · τi+1, j+1 holds because Ii, j can be partitioned into the set including
π with π j+1 = i + 1, which is Ii+1, j+1 · τi+1, j+1 and the other set, which is Ii+1, j , like Pi, j .
The construction of A is not completed yet because the (n − l)-suffix of each permutation in I0,0 is in one fixed order. We must generate all orders of the (n − l)-suffix of each
permutation in I0,0 . This is realized by su fn,l × I0,0 , where su fn,l is the π DD for the set
including the n-permutations π in which πi = i holds for 1 ≤ i ≤ l and the (n − l)-suffix
is in any order. We can obtain su fn,l by a construction like Algorithm 7, which will be
precisely described in Section 3.4.1. Algorithm 4 describes the entire process.
Algorithm 4 Construct A.
In,l ← π DD for {en }for i = n − 1 to 0 do
for j = l to 0 do
if j < l thenIi, j ← Ii+1, j ∪ Ii+1, j+1 · τi+1, j+1
else
Ii, j ← Ii+1, j
end ifend forend forsu fl,l ← π DD for {en }for i = l + 1 to n do
su fi,l = su fi−1,lfor j = l + 1 to i − 1 do
su fi,l ← su fi,l ∪ su fi−1,l · τi, j
end forend forreturn su fn,l × I0,0

3.2 Generation of Vincular Pattern-Containing Permutations
Recall that the additional restriction of vincular patterns is adjacency of positions.
Therefore, we can generate vincular pattern-containing permutations by a slight modification of step C from Section 3.1.2. We call the modified step C′ . C′ denotes the π DD
which corresponds to step C′ .
If the jth and the ( j + 1)th elements must be adjacent, j + 1 is the right-hand neighborof j for all permutations in C′ . In other words, if we assign j to ith position, we mustassign ( j + 1) to (i + 1)th position. For C′ , we define P′i, j = P′i−1, j−1 · τi, j if the jth andthe ( j + 1)th elements must be adjacent, and otherwise P′i, j = P′i−1, j ∪ P′i−1, j−1 · τi, j as Pi, j .
20

As shown in Section 3.1.2, P′i−1, j consists only of permutations π such that πi ̸= j, andP′i−1, j−1 · τi, j consists only of π such that πi = j. Thus, if the jth and the ( j + 1)th elements
must be adjacent, P′i, j includes only permutations π such that πi = j, and P′i, j · τi+1, j+1
includes only permutations π such that πi = j and πi+1 = j + 1, that is, j and j + 1 areadjacent. Therefore, P′i+1, j+1 = P′i, j+1 ∪ P′i, j · τi+1, j+1 includes only the permutations inwhich j and j + 1 are adjacent because P′i, j · τi+1, j+1 satisfies the adjacency as above,
and P′i, j+1 also satisfies the adjacency recursively. Therefore, we obtain C′ = P′n,l by
Algorithm 5, which is Algorithm 3 with one additional branch.
Algorithm 5 Construct C′ .
P′0,0 ← π DD {en }for i = 1 to n do
for j = 0 to l do
if j > 0 thenif jth and ( j + 1)th elements must be adjacent thenP′i, j ← P′i−1, j−1 · τi, jelse
P′i, j ← P′i−1, j ∪ P′i−1, j−1 · τi, j
end ifelse
P′i, j ← P′i−1, j
end ifend forend forreturn P′n,l3.3 Generation of Bivincular Pattern-Containing Permutations
Bivincular patterns have the three restrictions: a relative order, adjacencies of positions
and consecutiveness of values. Hence, we use step C′ as in Section 3.2 and change step
A to A′ in the same way as C was changed to C′ . If the jth and the ( j + 1)th values must
be consecutive, we define I′i, j = I′i+1, j+1 · τi+1, j+1 . Algorithm 6 gives the details of thisalgorithm.

3.4 Generation of Pattern-Avoiding Permutations
In this section, we give an algorithm for generating all σ -avoiding n-permutations.
This algorithm makes use of the following fact: the set of σ -avoiding permutations is thecomplement of the set of permutations that contain σ . Hereafter, Avn (σ ) denotes the set of21

Algorithm 6 Construct A′ .
In,l ← π DD for {en }for i = n − 1 to 0 do
for j = l to 0 do
if j < l thenif jth and ( j + 1)th elements must be consecutive thenIi, j ← Ii+1, j+1 · τi+1, j+1
else
Ii, j ← Ii+1, j ∪ Ii+1, j+1 · τi+1, j+1
end ifelse
Ii, j ← Ii+1, j
end ifend forend forsu fl,l ← π DD for {en }for i = l + 1 to n do
su fi,l = su fi−1,lfor j = l + 1 to i − 1 do
su fi,l ← su fi,l ∪ su fi−1,l · τi, j
end forend forreturn su fn,l × I0,0

σ -avoiding n-permutations and Sn denotes the set of all n-permutations. As stated above,
Avn (σ ) = Sn \Cn (σ ) holds. The generation of the set of permutations which contain σ wasshown above in Sections 3.1 to 3.3 . In general, the time needed to compute set difference
depends on the cardinalities of the sets. On the other hand, the set difference operation of
π DD can be efficient because it depends on the size of the π DDs. We now introduce thealgorithm for generating Sn .

3.4.1

Generation Algorithm for all n-Permutations

Let Sn denote the π DD for Sn . We can recursively construct Sn . Suppose we obtained Sn−1 . We consider (n − 1)-permutations as n-permutations with πn = n. Thus,
Sn−1 · τk,n consists of all n-permutations π such that πn = k. Therefore, Sn can be obtainedby computing Sn−1 · τ1,n ∪ Sn−1 · τ2,n ∪ . . . ∪ Sn−1 · τn−1,n ∪ Sn−1 . Algorithm 7 realizes thisprocedure, using loops. Figure 3.3 shows S4 . While the cardinality of Sn is n!, the size of
Sn is O(n2 ) as shown in Figure 3.3. This demonstrates a high compression ratio of π DDs.
22

τ1,4

0
0

τ3,4

τ2,4

1

1

1
0

τ2,3

0

τ1,3

1

1

τ1,2

0
0

1

1

Figure 3.3. The π DD for S4 .

Algorithm 7 Construct Sn .
S0 ← π DD for {en }for i = 1 to n do
Si ← Si−1
for j = 1 to i − 1 do
Si ← Si ∪ (Si−1 · τi, j )end forend forreturn Sn

3.4.2 Summary of Generation Algorithm for Avn (σ )Our algorithm for Avn (σ ) can be summarized as follows. First, we construct the π DD
for Sn . Next, we construct the π DD for Cn (σ ) by choosing the steps to take according to
the pattern to avoid. Finally, we calculate the set difference of Sn and Cn (σ ), and hence
obtain Avn (σ ). This procedure is illustrated in Figure 3.4.
input:

n,

1. Generate Sn

2. Generate Cn ( )3. Calculate Sn \ Cn ( )classical
Step C
Step C0
vincularbivincular

Step B

classical
vincular
Step A
Step A0

bivincular

output: Avn ( )Figure 3.4. The summary of our algorithms for Avn (σ ).

233.5 Generation of Permutations with Pattern Occurrence Counts(k)

In this section, we give an algorithm generating Fn (σ ). Our algorithm is divided(k)into two parts: first we generates Pn,σ , and then computes Fn (σ ) = {π | Pn,σ (π ) = k}from Pn,σ .

3.5.1

Generation Algorithm for Pn,σWe gave a generation algorithm for non-weighted occurrence using π DD. Thus, inorder to construct the π DD vector for Pn,σ , we want to extend the generation algorithm
for Cn (σ ) to handle multiplicities as the pattern occurrence counts of σ .
Here, note that some embeddings in the generation of Cn (σ ) cause duplications. For
example, both 413 and 423, which are order isomorphic to 312, are embedded in 4213,
and there is no other numerical sequence order isomorphic to 312 which is embedded
in 4213. In other words, 312 occurs twice in 4213. The number of such duplications
is equal to the pattern occurrence count of a given pattern in a permutation. Since thealgorithm described in Section 3.1 uses π DD, such duplications are not counted. But by
using the Cartesian product of π DD vectors instead of π DDs, we can generate the multisetof permutations whose multiplicity represents the pattern occurrence count, i.e. Pn,σ .

3.5.2

(k)

Generation Algorithm for Fn (σ )We can obtain Pn,σ by using Cartesian product of π DD vectors as described in theprevious subsection. However, in order to computationally check whether or not strong(k)
Wilf-equivalence between σ1 and σ2 holds, we must calculate the cardinalities of Fn (σ1 )(k)and Fn (σ2 ) for 0 ≤ k ≤ M, where(n) M denotes the maximum number of occurrences of agiven pattern. Note that M ≤ l holds, where l is the (lengthof the pattern, because the)number of subsequences of length l in n-permutation is nl . In this subsection, we present(k)an algorithm constructing the π DDs for Fn (σ ) for 0 ≤ k ≤ M from the π DD vector for
Pn,σ which was constructed by the algorithm in the previous subsection.
(k)

Let m be ⌊log M⌋. If k is fixed, it is easy to calculate Fn (σ ) from the π DD vector⃗P = (P0 , P1 , . . . , Pm ) as follows:(k)

Fn (σ ) =∩0≤i≤m

{Pi | ki = 1} \∪{Pi | ki = 0},0≤i≤mwhere ki means the ith bit of the binary representation of k. This algorithm costs O(m)(k)π DD operations. Hence, computation of Fn (σ ) for 0 ≤ k ≤ M costs O(mM) π DD operations.
We improve the number of π DD operations from O(mM) to O(M). Let Wk be theπ DD for the set of permutations whose multiplicity is k in the given π DD vector ⃗P.
24

We introduce don’t care * to the binary representation of integers. Here, W(∗...∗0ki ...k0 )2 ∪W(∗...∗1ki ...k0 )2 = W(∗...∗∗ki ...k0 )2 and W(∗...∗0ki ...k0 )2 ∩W(∗...∗1ki ...k0 )2 = 0/ hold. Hence,W(∗...∗1ki ...k0 )2= W(∗...∗∗ki ...k0 )2 ∩ Pi+1 ,W(∗...∗0ki ...k0 )2= W(∗...∗∗ki ...k0 )2 \W(∗...∗1ki ...k0 )2 .

Therefore, we can calculate Wk for 0 ≤ k ≤ M from W(∗...∗)2 = Sn by repeating calculationsof the above recursions. The number of valid binary representations whose prefix canbe consecutive “don’t care" symbols is 20 + 21 + . . . + 2m = 2m+1 − 1 = O(M). For each(k)calculation of Wk , we use only one π DD operation. Therefore, we can generate Fn (σ )for 0 ≤ k ≤ M by O(M) π DD operations based on the recursions. Algorithm 8 gives a
pseudo code of this algorithm. This algorithm temporarily uses W(0...0ki ...k0 )2 to representW(∗...∗ki ...k0 )2 .
Algorithm 8 Generate Wk for all 0 ≤ k ≤ M from ⃗P = (P0 , P1 , . . . , Pm ).
W0 ← π DD for Sn
for i = 0 to m dofor bin = 2i to 2i+1 − 1 do
Wbin ← Wbin−2i ∩ Pi
Wbin−2i ← Wbin−2i \Wbin
end forend for(k)

3.5.3 Summary of Generation Algorithm for Fn (σ )Our algorithm can be summarized as follows. First, we construct the π DDs for A, B,
and C by the algorithms described in Section 3.1. Second, we transform these π DDs into
⃗ = (B × A). Third, we calculate the Cartesianthe π DD vectors, that is, ⃗P = (C) and Q⃗⃗
product P × Q, which is the π DD vector for Pn,σ . Finally, we calculate the π DDs for(k)Fn (σ ) from the π DD vector for Pn,σ using Algorithm 8. This process is illustrated in
Figure 3.5.

input:n,ComputeCartesian product~
P~ , Q

Algorithms 3 or 5
Algorithms 4 or 6
C, B ⇥ A

Pn,

Transform into
πDD vector

Algorithm 8

output:Fn(k) ( )(k)Figure 3.5. The summary of our algorithm for Fn (σ ).

25Chapter 4

Experimental Results
We implemented our algorithm in C++ and carried out computational experiments on
a 3.20 GHz Intel Core i7-3930K CPU machine with Ubuntu 12.04 LTS 64-bit OS and
64 GB memory. We compared the performance of our algorithm to that of the naive
method. The naive method generates all n-permutations and, for each n-permutation,
enumerates pattern occurrence count of σ by checking the order isomorphism between all
k-subsequences and σ .
Table 4.1. Computation time (sec) for generating classical pattern-avoiding permutations.

n

8

9

10

11

12

13

14

15

best
averageworst
best
averageworst
best
averageworst
best
averageworst
best
averageworst
best
averageworst
best
averageworst
best
average
worst

2
0.000
0.000
0.000
0.000
0.004
0.008
0.004
0.008
0.012
0.000
0.008
0.016
0.004
0.014
0.024
0.016
0.022
0.022
0.008
0.032
0.056
0.016
0.052
0.088

π DD Method
l
3
4
0.000
0.000
0.002
0.004
0.008
0.012
0.000
0.004
0.005
0.009
0.016
0.016
0.004
0.016
0.011
0.028
0.020
0.044
0.012
0.044
0.029
0.101
0.052
0.152
0.024
0.152
0.087
0.444
0.156
0.780
0.048
0.568
0.284
1.787
0.544
3.072
0.116
1.960
1.029
6.769
1.968
12.021
0.300
5.688
3.513
24.7716.860
48.415

5
0.000
0.001
0.008
0.004
0.009
0.024
0.024
0.036
0.060
0.092
0.174
0.276
0.428
0.921
1.392
1.824
4.309
6.888
6.448
19.03632.37023.81485.655160.562

26

2
0.000
0.008
0.016
0.052
0.056
0.060
0.472
0.478
0.484
5.240
5.290
5.340
—
—
—
—
—
—
—
—
—
—
—
—

Naive Method
l
3
4
0.000
0.000
0.017
0.053
0.020
0.064
0.116
0.468
0.119
0.499
0.124
0.540
1.140
6.000
1.173
6.453
1.200
6.932
13.05389.49413.21695.72713.365 101.878
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—

5
0.000
0.007
0.080
0.880
0.926
1.004
17.08918.22319.697417.958435.211453.604
—
—
——
—
—
—
—
—
—
—
—

Table 4.2. Memory consumption (kB) for generating classical pattern-avoiding permutations.
|Avn (σ )|
l

n

8

9

10

11

12

13

14

15

best
averageworst
best
averageworst
best
averageworst
best
averageworst
best
averageworst
best
averageworst
best
averageworst
best
average
worst

2
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1

3
1430
1430
1430
4862
4862
4862
16796
16796
16796
58786
58786
58786
208012208012208012742900742900742900267444026744402674440969484596948459694845

4
15485
15656
15793
91245
93096
94776
55566257415059195034750903648275
382411222214707
23771768
25431452
144640291
158260498
173453058
956560748
1073474327
1209639642
6411521056
7401901167
8604450011

5
33184
33277
33325
25875726074226186321369782171460
219239018478134
19011623
19358590
165857600
173553425
178904675
1535336290
1641499314
1720317763
14584260700
16006197603
17132629082
141603589300
160274747099
176055309619

2
1600
1600
1600
1600
1600
1600
1600
1784
1968
1600
2186
2772
1976
3112
4248
2764
4954
7144
2760
7754
12748
4228
9112
13996

π DD Method
l
3
4
1596
1596
1598
1916
1600
1972
1964
2748
2233
2933
2768
4208
2760
4212
3509
6856
4260
7444
4208
7676
5876
17641
6792
25084
7112
25316
16106
48405
25084
94788
12708
51436
32130
16884851084
20126424440
18737211163454262119046077964047620
38914023483615607204064403092572

5
1596
1599
1600
2744
2768
2792
7156
7376
7700
13720
25233
27000
49108
93525
1029401884163371234084603964321282547
1587600
1543108
4986352
6471388

2
1068
1068
1068
1072
1072
1072
1068
1070
1072
1072
1072
1072
—
—
—
—
—
—
—
—
—
—
—
—

Naive Method
l
3
4
1064
1064
1067
1067
1068
1072
1068
1068
1071
1071
1072
1076
1068
1068
1071
1071
1072
1076
1072
1068
1072
1071
1072
1072
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—

5
1064
1067
1072
1068
1071
1076
1068
1071
1076
1068
1071
1076
—
—
——
—
—
—
—
—
—
—
—

4.1 Results for Classical Pattern-Avoiding Permutations
Tables 4.1 and 4.2 show the results for generating permutations avoiding a classicalpattern. The tables show the best, the worst, and the average computation time and memory consumption over all patterns with length l = 2, 3, 4, and 5. Note that computation
time of our π DD method is time to construct Avn (σ ), and computation time of the naive
method is time to output all pattern-avoiding permutations to /dev/null. Since output is not
required for our purpose as described in Section 1.3, computation time of π DD method
does not include output time.
For computation time, in almost all cases, our algorithm is faster than the naive method.
For example, in n = 11, our method requires only 0.3% of the time required by the naive
one. It should be noted that there are differences between the best and worst performancefor the same case in the results of our algorithm, while the naive method hardly shows
any differences. However, in almost all worst-case scenarios, the performance of ouralgorithm is better than the best-case scenario of the naive one. Computation time of bothmethods increase exponentially with respect to n, but our algorithm has a smaller growthrate than the naive method.
Figures 4.1 and 4.2 also show the results for classical patterns. These results show
the average time and memory consumption for all patterns, where n is fixed at 10 andl varies. Estimate represents the estimated memory consumption for storing all patternavoiding permutation on memory, where we suppose that the representation of one number
costs one byte, i.e. n · |Avn (σ )|. Naive method hardly uses memory, because it stores noinformation. Memory consumption of the π DD method is greater than naive method, but
it is very smaller than the estimate especially when l is near n. This shows that π DD canachieve high compression when the cardinality of the set is near n!, such as in the case of
Sn . The results also show the computation time depends on the size of π DDs. In contrast,
27

Figure 4.1. Computation time when n = 10.

Figure 4.2. Memory usage when n = 10.

the computation time of the naive method is in proportion tosubsequences that must be checked.

(n)l, which is the number of

4.2 Results for Vincular and Bivincular Patterns
Table 4.3 presents the results for vincular patterns. We only generated Baxter permutations, because there are a huge number of vincular patterns for each l, namely l! ·2l−1 . Baxter permutations are defined as avoiding the two vincular patterns, 3142 and
2413, and appear in many mathematical problems [1, 8, 10]. Our algorithm generates
Avn (3142, 2413) = Sn \ (Cn (3142) ∪ Cn (2413)). On the other hand, the naive method
checks the order isomorphism between all l-subsequences and the two patterns simultaneously. B(n) denotes the number of Baxter permutations of length n.
The performance of our algorithm for vincular patterns is as good as that for classicalpatterns. Our algorithm is faster than the naive method.
28

Table 4.3. Experimental results for generating Baxter permutations.

π DD Method
Naive Method
Time (s) Memory (kB) Time (s) Memory (kB)
810754 0.016
2760
0.052
3124
9
58202 0.028
4164
0.448
3128
10
326240 0.060
12984
5.792
3124
11
1882960 0.212
26828 79.4053128
1211140560 0.908
98924 1147.583
3124
1367329992 3.678
383272——14414499438 13.419
824732——15 2593341586 50.499
3151164——
16 16458756586 193.704
12403488——
17 105791986682 745.779
40788188
—
—
n

B(n)

Table 4.4. the π DD for Baxter permutations (n = 15).

SnCn (3142) ∪Cn (2413)
Avn (3142, 2413)#permutations
1307674368000
1305081026414
2593341586#nodes in π DD
10540945852158472

When n = 15, the time for calculating the difference Sn \Cn (σ ) is 1.110 seconds, which
is about 2% of the entire computation time. In general, calculating the set difference forsets with large cardinality without π DDs is not efficient, but, π DD’s difference operation
is not a bottleneck in this problem. Most of the computation time is due to the Cartesian
product operations between three π DDs, which require 46.020 seconds.
The number of permutations and the size of the corresponding π DD are shown in
Table 4.4, where it is clear that π DD achieves a high compression ratio.
()
123
We show the results for bivincular patterns. Specifically, we generated Avn,
231
which is known to be related with chord diagrams, (2+2)-free posets and ascent sequences [7].
( )123Table 4.5 presents the result of generating Avn. Both our algorithm and the naive
231
method show better performance than the result on Baxter permutations because the pat( )123tern length, number of patterns, and the cardinality of Avn
are all decreasing. For
231
n = 13, the π DD method can generate the permutations in less than 1 second while thenaive one requires about 2 hours.

29

Table 4.5. Experimental results for bivincular pattern.
()
π DD Method
Naive Method
123
Time (s) Memory (kB) Time (s) Memory (kB)
231
8
5335
0.004
3084
0.028
3128
9
31240
0.004
3084
0.208
3128
10
201608
0.020
4196
2.428
3128
11
14220740.052
12948 32.298
3128
1210886503
0.184
26436 474.1733128
13899031000.916
98656 7458.2703128
14796713190
3.808
382712——157541889195 15.357
1510640——
16 75955177642 62.408
3327380——
17 810925547354 254.896
12887884——
18 9148832109645 1016.132
50354060
—
—
n

Avn

4.3 Results for Permutations with Pattern Occurrence Counts(k)

Table 4.6 shows computation time for the entire process of generating Fn (σ ). The
table represents the best, the worst, and the average computation time over all patterns withlength l = 2, 3, 4, and 5, respectively. Note that computation time for our π DD method
only include the constructions of π DDs, meaning that we do not decompress π DDs and(k)thus do not output permutations explicitly. The naive method only counts |Fn (σ )|, andnot explicitly outputs permutations too. For n = 10 and l = 5, our algorithm is about 20
times faster than the naive method. Our algorithm takes the maximum computation time
when l is near n/3, while the naive method takes the maximum time when l is near n/2.
We consider the reasons for the difference as follows. At first, the computation time of
π DD depends on (the) size of π DD, while that of the naive method depends on the numberof subsequences nl . In practical cases, the size of a π DD tends to become small when
the set of permutations is sparse or very dense. The longer the length of a pattern is, thefewer the pattern occurrence counts of the pattern in each permutation is. This means that(k)
Fn (σ ) tends to be dense for small k and to be sparse for large k when σ is a long pattern.
We imagine this is a reason why l on the peak of computation time of our algorithm issmaller than l on the peak of the naive method.
(k)

Table 4.7 shows memory consumption and the size of π DDs for generating Fn (σ ).
We do not describe the memory consumption of the naive method because the naive
method does not store the permutations, and uses a small memory. Tables 4.6 and 4.7
suggest the computation time of π DDs is proportional to the size of π DDs. Memory consumption of our algorithm grows exponentially with respect to n. We cannot calculate(k)(k)
F13 (σ ) because of insufficient memory. However the total size of π DDs for Fn (σ ) issmaller than the number of all n-permutations n!. Moreover, since some π DDs share theirequivalent subgraphs, the actual number of the total nodes of the π DDs on memory may
be smaller than the results in Table 4.7. This shows that π DDs achieve compact represen(k)tations of Fn (σ ).

30

(k)

Table 4.6. Computation time (sec) for generating Fn (σ ).
nbestaverageworst
best
averageworst
best
averageworst
best
averageworst
best
average
worst

8

9

10

11

12

2
0.032
0.036
0.040
0.076
0.078
0.080
0.276
0.310
0.344
1.436
1.642
1.848
6.316
7.064
7.812

π DD Method
l
3
4
0.044
0.032
0.052
0.043
0.064
0.056
0.212
0.232
0.295
0.274
0.356
0.308
1.912
2.820
2.604
3.390
3.288
3.908
14.16530.19018.94338.81424.09848.33196.114365.275
136.343494.926
180.711655.829

5
0.016
0.021
0.028
0.068
0.087
0.120
0.956
1.232
1.524
11.67315.68319.809144.141231.141301.135

2
0.036
0.038
0.040
0.316
0.322
0.328
3.792
3.900
4.008
51.59553.67355.752———

Naive Method
l
3
4
0.052
0.060
0.057
0.071
0.064
0.080
0.676
1.012
0.714
1.088
0.740
1.164
10.301
20.141
10.891
21.48911.39323.013
169.331 467.185
179.724 488.088
188.248 509.804
—
—
—
—
—
—

5
0.044
0.054
0.072
0.968
1.037
1.128
25.52227.31429.482750.307774.683
806.186
—
—
—-

(k)

Table 4.7. Memory consumption and the size of π DDs for generating Fn (σ ).
(k)

n
best
averageworst
best
9 average
worst
best
10 average
worst
best
11 average
worst
best
12 average
worst
8

memory consumption (kB)∑M
k=0 {the size of π DDs for Fn (σ )}
l
l
2
3
4
5
2
3
4
5
37548
37812
37808
37236
37548
38075
37819
37280
10535
20941
11501
4144
37548
38340
38024
37288
38340
41528
41392
38604
38736
42542
42372
39076
42496
139315
86321
30843
39132
43156
42940
39660
42480 152316
26834878532
43272 212905
275364141172 167368
96294572651026283344064 275604
279712154728152328 1032672 2064776 1031504
152484 1092093 2142647 1067605 658823 6684948 6807355 2548799
152640 1160728 2224848 1128760
520216 4209304 16461940 8263752
527320 6863648 18459651 9723839 2585682 45156225 69564400 27639470
534424 8232056 32355008 16375948

Table 4.8 provides candidates of strongly Wilf-equivalent classes. Two patterns σ1(k)(k)
and σ2 are placed in the same cell of the table if |Fn (σ1 )| = |Fn (σ2 )| was confirmed
for 1 ≤ n ≤ 12 and non-negative integers k. It is trivial that a pattern π and its reverse
π r are always strongly Wilf-equivalent. Note that a pattern π and its inverse π −1 are
not necessarily strong Wilf-equivalent, while these are always Wilf-equivalent. Table 4.8
shows many non-trivial and unproved candidates of strongly Wilf-equivalent classes.

31

Table 4.8. Candidates of strongly Wilf-equivalent classes according to the experimental results.
l
2
3
4

5

candidates of strongly Wilf-equivalent classes
12,21
123,321132,213,231,312
1234,4321
1243,2134,3421,4312
1324,4231
1342,1423,2314,2431,3124,3241,4132,4213
1432,2341,3214,4123
2143,3412
2413,3142
12345,54321
12354,21345,45321,54312
12435,13245,53421,54231 12453,12534,23145,31245,35421,43521,54132,54213
12543,32145,34521,54123 13524,14253,24135,31425,35241,42531,52413,53142
13425,14235,52431,53241 13452,15234,23415,25431,41235,43251,51432,53214
13254,21435,45231,53412 13542,15243,24531,32415,34251,42135,51423,53124
14325,52341
14352,15324,24315,25341,41325,42351,51342,52314
14523,32541,34125,52143 14532,15423,23541,32451,34215,43125,51243,52134
15342,24351,42315,51324 15432,23451,43215,51234
21354,45312
21453,21534,23154,31254,35412,43512,45132,45213
21543,32154,34512,45123 23514,25134,25413,31452,35214,41253,41532,43152
24153,31524,35142,42513 24513,25143,31542,32514,34152,35124,41523,42153
25314,41352

32

Chapter 5

Conclusion
In this thesis, we introduced algorithms for generating several pattern-avoiding permutations using π DDs. Experimental results show that our algorithms are faster than thenaive method and cost less memory than the naive storing. In addition, our approaches
output π DDs on memory, which has rich operations. This means that we can submit additional queries such as membership test or random sampling for the set of pattern-avoiding
permutations efficiently and immediately.
Furthermore, we gave an algorithm implicitly generating Pn,σ for given n and σ using(k)
π DD vectors, and an algorithm computing the π DDs representing Fn (σ ) for each k fromthe π DD vector for Pn,σ . These algorithms was practically faster than a naive method, andprovided some candidates of strongly Wilf-equivalent classes.
Future work is to improve further the computation time and memory consumption of
our algorithms, and to compare our algorithms and other algorithms for some particularpatterns, for example Baxter permutations [4]. Moreover, we are also interested in analyzing the relationship between pattern-avoiding permutations and floorplans. In future work,
we plan to develop several functions such as search by criteria and random sampling to(k)use π DDs as floorplan databases. For the algorithm generating Fn (σ ), experiments forlarger n and k, multiple patterns, and other general patterns are also interesting for us. We
wish that someone will prove some strong Wilf-equivalences which are described in thispaper as candidates.

33

Acknowledgements
I am indebted to my supervisor, Prof. Shin-ichi Minato, for his advise and help, which
improved both my research life and this thesis. I am grateful to Prof. Zeugmann Thomas
and Prof. Hiroki Arimura, who help me to suggest research ideas and improve my writing
skill. I am also indebted Dr. Takahisa Toda, Dr. Charles Harold Jordan, and all membersof JST ERATO Minato Project and Laboratory for Algorithmics, who help me with myresearch and this thesis. Finally, I thank my family for their love and support.

34

Bibliography[1] Eyal Ackerman, Gill Barequet, and Ron Y. Pinter. A bijection between permutations
and floorplans, and its applications. Discrete Applied Mathematics, 154(12):1674–
1684, 2006.
[2] Michael Albert.
Permlab:Software for permutation
http://www.cs.otago.ac.nz/staffpriv/malbert/permlab.php, 2012.

patterns.

[3] Eric Babson and Einar Steingrímsson. Generalized permutation patterns and a classification of the Mahonian statistics. Séminaire Lotharingien de Combinatoire, 44,
2000.
[4] Andrew M. Baxter and Lara K. Pudwell. Enumeration schemes for vincular patterns.
Discrete Mathematics, 312(10):1699–1712, 2012.
[5] Miklós Bóna. Exact enumeration of 1342-avoiding permutations: A close linkwith labeled trees and planar maps. Journal of Combinatorial Theory, Series A,
80(2):257–272, 1997.
[6] Prosenjit Bose, Jonathan F. Buss, and Anna Lubiw. Pattern matching for permutations. Information Processing Letters, 65(5):277–283, 1998.
[7] Mireille Bousquet-Mélou, Anders Claesson, Mark Dukes, and Sergey Kitaev. (2+2)free posets, ascent sequences and pattern avoiding permutations. Journal of Combinatorial Theory, Series A, 117(7):884–909, Oct 2010.
[8] Hal Canary. Aztec diamonds and Baxter permutations. The Electronic Journal of
Combinatorics, 17(1), 2010.
[9] W.M.B. Dukes, M.F. Flanagan, T. Mansour, and V. Vajnovszki. Combinatorial Graycodes for classes of pattern avoiding permutations. Theoretical Computer Science,
396(1-3):35–49, 2008.
[10] Éric Fusy. Bijective counting of involutive Baxter permutations. Fundamenta Informaticae, 117(1-4):179–188, 2012.
[11] Anisse Kasraoui. New Wilf-equivalence results for vincular patterns. European
Journal of Combinatorics, 34(2):322–337, 2013.

35

[12] Jun Kawahara, Toshiki Saitoh, Ryo Yoshinaka, and Shin-ichi Minato. Counting
primitive sorting networks by π DDs. Technical Report TCS-TR-A-11-54, Divisionof Computer Science, Hokkaido University, 2011.
[13] Donald E. Knuth. Fundamental Algorithms, volume 1 of The Art of Computer Programming. Addison-Wesley, Reading, Massachusetts, third edition, 1997.
[14] Donald E. Knuth. Sorting and Searching, volume 3 of The Art of Computer Programming. Addison-Wesley, Reading, Massachusetts, second edition, 1998.
[15] Darko Marinov and Radoš Radoičić. Counting 1324-avoiding permutations. The
Electronic Journal of Combinatorics, 9(2), 2003.
[16] Shin-ichi Minato. Zero-suppressed BDDs for set manipulation in combinatorial
problems. Proc. of 30th ACM/IEEE Design Automation Conf. (DAC 1993), pages
272–277, 1993.
[17] Shin-ichi Minato. π DDs: A new decision diagram for efficient problem solving in
permutation space. Proc. of 14th International Conference on Theory and Applications of Satisfiability Testing (SAT 2011), pages 90–104, 2011.
[18] Vaughan R. Pratt. Computing permutations with double-ended queues, parallel
stacks and parallel queues. Proc. of the Fifth Annual ACM Symposium on Theoryof Computing (STOC 1973), pages 268–277, 1973.
[19] Nathan Reading. Generic rectangulations. European Journal of Combinatorics,
33(4):610–623, 2012.
[20] Zvezdelina E. Stankova. Forbidden subsequences. Discrete Mathematics, 132(13):291–316, 1994.
[21] Einar Steingrímsson. Some open problems on permutation patterns. London Mathematical Society Lecture Note Series, pages 239–263, 2013.
[22] Julian West. Sorting twice through a stack. Theoretical Computer Science, 117:303–
313, 1993.
[23] Herbert S. Wilf. The patterns of permutations. Discrete Mathematics, 257(2):575–
583, 2002.
[24] Bo Yao, Hongyu Chen, Chung-Kuan Cheng, and Ronald Graham. Floorplan representations: Complexity and connections. ACM Trans. Des. Autom. Electron. Syst.,
8(1):55–80, 2003.

36