TCS -TR-A-13-67

TCS Technical Report

Implicit Generation of Pattern-Avoiding Permutations
Based on πDD
byYuma Inoue, Takahisa Toda and Shin-ichi Minato

Division of Computer Science
Report Series A
September 21, 2013

Hokkaido University
Graduate School ofInformation Science and Technology
Email:

minato@ist.hokudai.ac.jp

Phone:+81-011-706-7682

Fax:+81-011-706-7682

Implicit Generation of Pattern-Avoiding Permutations
Based on πDDs
Yuma Inoue

Takahisa Toda

Division of Computer Science
Graduate School of Info. Sci. and Tech.
Hokkaido University
Sapporo 060-0814, JapanJST ERATO Minato ProjectGraduate School of Info. Sci. and Tech.
Hokkaido University
Sapporo 060-0814, Japan

Shin-ichi Minato∗
Division of Computer Science
Graduate School of Info. Sci. and Tech.
Hokkaido University
Sapporo 060-0814, Japan

September 21, 2013

Abstract
Pattern-avoiding permutations are permutations where none of the subsequences match the relative order of a given pattern. Pattern-avoiding permutations are related to practical and abstract mathematical problems and canprovide simple representations for such problems. For example, some floorplans, which are used for optimizing very-large-scale integration(VLSI) circuitdesign, can be encoded into pattern-avoiding permutations. The generation ofpattern-avoiding permutations is an important topic in eﬃcient VLSI design
and mathematical analysis of patten-avoiding permutations. In this paper,
we present an algorithm for generating pattern-avoiding permutations, andextend this algorithm beyond classical patterns to generalized patterns withmore 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 eﬃciency of our algorithm by computational experiments.

1

Introduction

A permutation π avoids a pattern σ if no subsequence in π is order isomorphic to σ.
Two numerical sequences a = a1 a2 . . . an and b = b1 b2 . . . bm are order isomorphic
if a and b have the same length and satisfy the rule ai < aj if and only if bi < bjfor all i, j. Permutations that avoid pattern σ are called σ-avoiding permutations.
∗

He also works for JST ERATO Minato Project.

1

2

Yuma Inoue, Takahisa Toda and Shin-ichi Minato

Research of pattern-avoiding permutations dates back to stack sort, which was
proposed by Knuth in [10]. 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 [9], and the double-ended queue sorting problem [15], havebeen proposed, and pattern-avoiding permutations were developed in that context.
After pattern-avoiding permutations were proposed, many researchers engaged
in studies to compute the number of the permutations that avoid given patterns.
For example, 1342-avoiding permutations have been enumerated by a mathematical approach [3], and 1324-avoiding permutations can be counted by computer
programs [12]. Moreover, the relation of classes on pattern-avoiding permutations has also been examined. Two classes A1 and A2 are Wilf-equivalent if|A1 | = |A2 |, where |S| denotes the cardinality of set S. In [16], the nontrivial
Wilf-equivalence between 4132-avoiding and 3142-avoiding was discovered. The
generation of pattern-avoiding permutations can contribute to not only the discovery of unknown Wilf-equivalent classes, but also the identification of bijectivefunctions between such classes.
Relations between pattern-avoiding permutations and mathematical problems
have been studied actively [6, 7]. In particular, Yao et al. revealed a bijection between mosaic floorplans and Baxter permutations, which are generalized patternavoiding permutations [18], and Ackerman et al. proposed a simple encoding anddecoding between them in [1]. A floorplan is a topological partition of a rectangle into multiple rectangles, and a mosaic floorplan is a subclass of floorplans.
Floorplans have practical applications in areas such as VLSI design. Storing all
pattern-avoiding permutations into a database is equivalent to preparing a databaseof floorplans. Database queries such as searching by criteria and random sampling
are useful for VLSI design. Therefore, generating pattern avoiding permutations
can contribute to solving practical problems.
Wilf provided a generating algorithm for identity patterns and posed the question about the complexity of generation of pattern-avoiding permutations for general patterns [17]. In [4], Bose et al. proved that the permutation pattern matchingproblem is NP-complete and the enumerating problem is #P-complete. They also
proposed a decision algorithm for the special case when the pattern is a separable
permutation. The complexity of this algorithm is O(kn6 ), which Ibarra[8] improved to O(kn4 ), where n is the permutation length and k is the pattern length.
However, as far as we know, no generating algorithm for general patterns except
for brute force method has been proposed.
In this paper, we provide an eﬃcient algorithm for generating pattern-avoiding
permutations. Furthermore, we extend our algorithm to handle some generalized
patterns, such as vincular patterns and bivincular patterns.
Our algorithm is based on a permutation decision diagram (πDD), which is adata structure for compact representation of sets of permutations [14]. A πDD
not only achieves high compression of sets of permutations, but also supports richImplicit Generation of Pattern-Avoiding Permutations Based on πDD3algebraic set operations such as union and intersection. The computation timeof these operations depends on the size of the πDDs and not on the number of
permutations. If the πDD is small, computation is fast especially when the numberof permutations is large.
The rest of this paper is organized as follows. Section 2 presents the notations and definitions of permutations and patterns. Section 3 describes the basics of πDDs. Section 4 presents our algorithm for generating pattern-avoiding
permutations and its extension to some generalized patterns. Section 5 presents
experimental results, and Section 6 concludes this paper.

2

Permutations and Patterns

2.1

Permutations

A permutation of length n (n-permutation for brevity) is a bijection from {1, 2, ..., n}
to itself. Let π be an n-permutation. We write a permutation in the one-line form
as π = π1 π2 . . . πn , and denote iπ = πi . For example, π = 4312 is a 4-permutationand 3π = 1.
Multiplication over permutations x and y is defined as x · y = yx1 yx2 . . . yxn ,which is y after applying x. Note that the leftmost permutation is applied first.
For example, let x = 45213 and y = 41352, then x · y = 52143 (Fig. 1). Notethat multiplication over permutations is non commutative. We denote by en theidentity permutation of length n, where en satisfies ien = i for each 1 ≤ i ≤ n.
In this paper, we use the multiplication x · y in order to permutes the numbers
in y according 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τ(i,j) = j, jτ(i,j) = i, andkτ(i,j) = k for all other numbers k. Any n-permutation can be uniquely represented as the product of at most n − 1 transpositions based on a straight selection
sorting algorithm [11]. This algorithm repeatedly swaps the value k and the kthelement from right to left. For example, consider the decomposition of the permutation 54213 into a product of transpositions (Fig. 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 thisprocedure, we finally obtain 54213 = τ(1,2) · τ(2,3) · τ(1,4) · τ(3,5) .

2.2

Permutation Patterns

A permutation π contains a pattern σ if there is at least one subsequence in π which
is order isomorphic to σ, where the subsequence need not consist of consecutive

4

Yuma Inoue, Takahisa Toda and Shin-ichi Minato

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 1: An example of the multiplication of permutations.

=

54213
1
2
3
4
5

1
2
3
4
5

τ(1,2)・τ(2,3)・τ(1,4)・τ(3,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: Decomposition of 54213
into transpositions.

numbers in π. In other words, let k be the length of σ. There are indexes 1 ≤ i1 <
i2 < . . . < ik ≤ n such that πix < πiy if and only if σx < σy , for all pairs of x andy. For example, the permutation 4213 contains 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 generalized pattern, is a well-known generalization [2]. While the defining restriction
in classical patterns is order isomorphism, vincular patterns additionally have another restriction: adjacency of element positions in the permutation. We use theunderline 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 and the vincular pattern 312. Both423 and 413 are order isomorphic to 312, but 423 does not match 312 because thesecond and third elements are not adjacent in the permutation. 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 [5]. A bivincularpattern is restricted by adjacency of positions and additionally by consecutivenessof values. We use the two-line form with bars and underlines to represent bivincularpatterns. The first row represents consecutiveness and an identical order, and thesecond row represents adjacencies and a relative order. For example, the bivincular123
pattern
represents a pattern where the 1st and the 2nd smallest values must be
312
consecutive, the 2nd and the 3rd element in a subsequence must be adjacent in a
permutation, and the relative order must match 312. Thus, the permutation 4213
123
. Indeed both subsequences 423 and 413 are order isomorphic to 312
avoids312
but 423 does not match the bivincular pattern because 2 and 3 are not adjacentin the permutation, and 413 also does not match the bivincular pattern because 1
and 3 are not consecutive.
The problem considered in this paper can be stated as follows: for given a
positive integer n and a pattern σ, generate all σ-avoiding permutations of lengthn.

5Implicit Generation of Pattern-Avoiding Permutations Based on πDD

a

0

b

c

a

1

b

c

c

x

c

x
1

0

1

F0
0

c
0

x
0

b

0 1 0 0 0 1 1 0

F0
1

Figure 3: A binary decision tree anda ZDD for a set of combinations.

3

x

F1

F0

(1) merging ruleF1F0(2) deletion ruleFigure 4: Two reduction rules on
ZDDs.

πDDs

A πDD is a data structure which canonically represents and eﬃciently manipulates
a set of permutations. The eﬃciency of our algorithm is based on the compact
representation and rich set operations of πDDs. πDDs are based on zero-suppressedbinary decision diagrams (ZDDs) [13], which are decision diagrams for sets ofcombinations (families of sets).

3.1

ZDDs

A ZDD is derived by reducing a binary decision tree. Figure 3 shows the ZDD forthe family of sets {{a, b}, {a, c}, {c}}. A ZDD has five components: internal nodes
with an item labels, 0-edges, 1-edges, the 0-terminal node, and the 1-terminal node.
Each path represents a combination of items: if a 1-edge originates from a nodewith 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 the set represented by the ZDD. On the other hand,
if a path reaches the 0-terminal node, the combination is not in the set.
A ZDD is a compact and canonical form if we fix the order of the items andapply the following two reduction rules:(1) Merging rule: share all nodes which have the same child nodes and the samelabels(2) Deletion rule: delete all nodes whose 1-edge point directly to the 0-terminal
node.
These rules are illustrated in Fig. 4. In the worst-case scenario, the size of a ZDD(the number of nodes in a ZDD) can grow exponentially with respect to the numberof items. In many practical cases, though, a ZDD provides eﬃcient compression.
In addition, ZDDs support eﬃcient set operations such as union, intersection,and set diﬀerence. Since these operations are realized by recursive algorithms withhash table techniques, the computation time of these operations depends on thenumber of nodes in ZDDs, not on the cardinality of the sets represented by the
ZDDs.

6

Yuma Inoue, Takahisa Toda and Shin-ichi Minato

τ(1,4)
τ(3,4)P ∪Q
P \Q
P.Swap(x, y)
P ×Q

Union {π | π ∈ P or π ∈ Q}.
Diﬀerence {π | π ∈ P and π ∈/ Q}.
Swap {π · τ(x,y) | π ∈ P }.
Cartesian product {α · β | α ∈ P and β ∈ Q}.

Table 1: πDD operations.

3.2

τ(2,3)

τ(1,2)

0

1

Figure 5: The πDD for{2143, 2431, 4321} ={τ(1,2) · τ(3,4) , τ(1,2) ·τ(1,4) , τ(2,3) · τ1,4) }.

πDDs

We introduce a πDD, which represents a set of permutations by deriving it from a
ZDD. As shown in Sect. 2.1, any permutation can be uniquely decomposed into a
product of transpositions. Hence, by assigning transpositions to nodes in a ZDD,
each path in the ZDD represents a permutation. This is the basic idea of a πDD.
Since the transpositions τ(i,j) into which a permutation is decomposed are ordered
in increasing order of j, the order of transpositions in a πDD can be fixed. πDDs
obtain a compact and canonical form by applying the above two reduction rules inthe same way to ZDDs, and set operations are also available. Figure 5 shows anexample of a πDD.
Table 1 shows the πDD operations used in this paper. While the union andset diﬀerence operations are available like ZDDs, the swap and Cartesian productoperations are unique to πDDs. In particular, Cartesian product is very useful
because multiplication over permutations results in rearrangement. That is, byapplying Cartesian product operator, we can execute rearrangements of multiple
numerical sequences at once.

4

Main Results

In this section, we propose an algorithm for generating all σ-avoiding n-permutations.
This algorithm makes use of the following fact: the set of σ-avoiding permutations is the complement of the set of permutations that contain σ. Hereafter,
Avn (σ) denotes the set of σ-avoiding n-permutations, Sn denotes the set of all
n-permutations, and Cn (σ) denotes the set of n-permutations that contain σ. As
stated above, Avn (σ) = Sn \ Cn (σ) holds. The generation of the set of permutations which contain σ is easily possible by simple rearrangements as shown inImplicit Generation of Pattern-Avoiding Permutations Based on πDD

7

τ(1,4)
τ(2,4)
τ(3,4)
τ(1,3)
τ(2,3)
τ(1,2)
1

Figure 6: The πDD for S4 .
Sect. 4.2. In general, the time to compute set diﬀerence depends on the cardinalities of the sets. On the other hand, the set diﬀerence operation of πDD can beeﬃcient because it depends on the size of the πDDs.
First, we introduce the algorithm for generating Sn . Next, we show the algorithm for generating Cn (σ) for classical patterns. The algorithm can be easily
extended to vincular and bivincular patterns, which is demonstrated in Sect. 4.3
and 4.4.

4.1

Generating 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 .Swap(k, n) consists of all n-permutations π such that nπ = k.
Therefore, Sn can be obtained by computing Sn−1 .Swap(1, n) ∪ Sn−1 .Swap(2, n) ∪. . . ∪ Sn−1 .Swap(n − 1, n) ∪ Sn−1 . Algorithm 1 realizes this procedure by loops.
Figure 6 shows S4 . While the cardinality of Sn is n!, the size of Sn is O(n2 ) as
shown in Fig. 6. This is demonstrating a high compression ratio of πDDs.
Algorithm 1 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 .Swap(i, j))
end forend forreturn Sn

8

4.2

Yuma Inoue, Takahisa Toda and Shin-ichi Minato

Generating permutations containing a classical pattern

Hereafter, unless otherwise noted, k denotes
the length of a given pattern σ. In(n )order toCn (σ), we assign all k sequences that are order isomorphic to( generate)
σ into nk possible positions in an n-permutation. This is achieved in three steps
as follows:
A. Generate all permutations whose k-prefix is ordered in increasing order,
B. Rearrange the k-prefix of each permutation which generated in step A into
isomorphic order to σ,( )C. Distribute the k-prefix of each permutation which generated in step B over nk
possible positions in an n-permutation.
Figure 7 shows the process of generating C4 (312). Step B and C involve therearrangements of multiple permutations. This means that this process can bedone by Cartesian products of πDDs as shown in Sect. 3.2. Let A denote the πDD
for permutations which generated in step A, and let B and C denote the πDDs forthe rearrangements which correspond to step B and C respectively. Note that 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.z The same applies to C. Then, Cn (σ) can be obtained bycomputing C × B × A (Fig. 8). Note that the Cartesian products must be appliedin the reverse order of the three steps we execute, that is, we first apply B to A
and then apply C to the result of the first application.
We show the method for the construction of A at the end because it is similar
to the construction of C but more complicated.

n = 4, σ = 312, k = 3
Step A {1234, 1243, 1342, 2341}
Step B {3124, 4123, 4132, 4231}{3124, 3142,
Step C {3124, 3142, 3412, 4312,
4123, 4132, 4312, 3412,
3412, 4312,
4132, 4123, 4213, 2413, Remove 4123, 4132,
4231, 4213, 4123, 1423 } duplicated 4213, 2413,
permutations 4231, 1423 }= C4(312)
Figure 7: The process of generating C4 (312).

Implicit Generation of Pattern-Avoiding Permutations Based on πDD9

n = 4, σ = 312, k = 3

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

Construction of B

B is the πDD consisting only of the permutation given as a pattern. To constructthis πDD, we first decompose a given pattern into a product of transpositions asgiven in Sect. 2.1. The πDD for this decomposition can be easily constructed in abottom-up fashion.
4.2.2

Construction of C

C is the πDD for the set of n-permutations π such that there are k indexes 1 ≤p1 < p2 < . . . < pk ≤ n with pi π = i. This means that if π is in C, the numericalsequence 12 . . . k must be in π as its subsequence. A simple method to construct
C is as follows. We generate all n-permutations that satisfy the above condition,then convert each permutation to the πDD consisting only of the permutation.
We then calculate the union of all these πDDs. This algorithm is simple and easy
to implement. However,this is not eﬃcient because this algorithm has to repeat(n)union operations k times.
Our basic idea to reduce the( number) (n−1of) πDD(n−1)operations is based on Pascal’sntriangle, in which the recursion k = k + k−1 holds. Let P osi,j be the set of
all n-permutations π containing at least one subsequence πk1 πk2 . . . πkl satisfying
the following two conditions:
1. kl is less than or equal to i,
2. the subsequence matches the sequence 12 . . . j.
It is obvious that C is the πDD for P osn,k . If we can calculate P osi,j using P osi−1,jand P osi−1,j−1 like Pascal’s triangle, we can obtain C with only O(kn) operations.
In order to achieve this idea, we restrict P osi,j with the two additional conditions
as follows:
1. For any two distinct members π, π ′ ∈ P osi,j there is at least one index x suchthat px ̸= p′x .

10Yuma Inoue, Takahisa Toda and Shin-ichi Minato

2. For each i + 1 ≤ x ≤ n, x is fixed, i.e., xπ = x.
Although the two conditions are not necessary to step C, these conditions simplify
our algorithm. Here, we can partition P osi,j into the two sets: the set including πwith πi ̸= j and the other set. The former set equals P osi−1,j , and the latter one
can be obtained by assigning j into the ith position of permutations in P osi−1,j−1 .
Hence, let Pi,j denote the πDD for P osi,j , this is achieved by Pi−1,j−1 .Swap(i, j)because the ith element is i from the second condition and j is not assigned yet.
Thus, Pi,j = Pi−1,j ∪ Pi−1,j−1 .Swap(i, j) holds. The dynamic programming for thisrecursion is encoded in Algorithm 2.
Algorithm 2 Construct C.
P0,0 ← πDD for {en }for i = 1 to n do
for j = 0 to k do
if j > 0 thenPi,j ← Pi−1,j ∪ Pi−1,j−1 .Swap(i, j)
else
Pi,j ← Pi−1,jend ifend forend forreturn Pn,k4.2.3

Construction of A

Let Inci,j denote the set of all i-permutations in which the j-prefix is ordered inincreasing order. More precisely, π ∈ Inci,j satisfies 1 ≤ π1 < π2 < . . . < πj ≤ i.
Inci,j can be obtained in a similar way to P osi,j . Let Ii,j denote the πDD for
Inci,j . Inci,j is dividable into two sets: the set including π with πj = i and theother set. Unfortunately, however, Ii,j ̸= Ii−1,j ∪ Ii−1,j−1 .Swap(i, j) does not holds
while Pi,j = Pi−1,j ∪ Pi−1,j−1 .Swap(i, j) holds. This diﬀerence is caused by thefact that π ∈ Inci−1,j−1 can be πj ̸= j. For example, we suppose that we want toobtain π such that π1 = 2 and π2 = 3, π = τ1,2 · τ2,3 = 312 does not satisfy π2 = 3
because 2τ1,2 ̸= 2. This is avoidable by performing calculations in the decreasingorder, for example, π = τ2,3 · τ1,2 = 231. Thus, we start from In,k and end to I0,0
in the construction of A.
There is one more diﬀerence from the construction of Pi,j as follows: the (i − j)suﬃx( i ) of each permutation in Inci,j is in any order. In other words, |Inci,j | =j · (i − j)!. Hence, after we construct Incn,k , then rearrange (n − k)-suﬃx of each
permutation in Incn,k into any orders. The πDD for this rearrangement can beobtained by the construction like Algorithm 1. Algorithm 3 describes the entire
process.

Implicit Generation of Pattern-Avoiding Permutations Based on πDD

11

Algorithm 3 Construct A.
In,k ← πDD for {en }for i = n − 1 to 0 do
for j = k to 0 do
if j < k thenIi,j ← Ii+1,j ∪ Ii+1,j+1 .Swap(i, j)
else
Ii,j ← Ii+1,j
end ifend forend forsufk ← πDD for {en }for i = k + 1 to n do
sufi = sufi−1
for j = k + 1 to i − 1 dosufi ← sufi ∪ sufi−1 .Swap(i, j)
end forend forreturn sufn × I0,0

4.3

Generating permutations containing a vincular pattern

The additional restriction of vincular patterns is adjacency of positions. Therefore,
we can generate vincular pattern-avoiding permutations by a slight modification of
step C from Sect. 4.2.2. We call the modified step C’. C′ denotes the πDD whichcorrespond to step C’.
If the jth and the (j − 1)th elements must be adjacent, we define Pi,j =Pi−1,j−1 .Swap(i, j), which is not united Pi−1,j . Hence,
Pi+1,j+1 = Pi,j+1 ∪Pi,j .Swap(i, j)= Pi,j+1 ∪Pi,j−1 .Swap(i−1, j −1).Swap(i, j)
That is, π ∈ Pi−1,j−1 .Swap(i − 1, j − 1).Swap(i, j) must be πj−1 = i − 1 and πj = i.
Pi,j+1 is dividable into Pi−1,j+1 and Pi−1,j−1 .Swap(i − 2, j − 1).Swap(i − 1, j), in
which πj−1 = i − 2 and πj = i − 1, as in Pi+1,j+1 , and so forth. This recursive
structure shows that π ∈ Pi+1,j+1 must be πj = πj−1 + 1: the jth and the (j − 1)th
elements are adjacent. Therefore, we obtain Algorithm 4 for C′ by adding a branch
to Algorithm 2.

4.4

Generating permutations containing a bivincular pattern

Bivincular patterns have the three restrictions: a relative order, adjacencies of
positions and consecutiveness of values. Hence, we use step C’ in Sect. 4.3 andchange step A to A’ in the same way as C was changed to C’.

12Yuma Inoue, Takahisa Toda and Shin-ichi Minato

Algorithm 4 Construct C′ .
P0,0 ← πDD {en }for i = 1 to n do
for j = 0 to k do
if j > 0 thenif j-th and (j − 1)-th elements must be adjacent thenPi,j ← Pi−1,j−1 .Swap(i, j)
else
Pi,j ← Pi−1,j ∪ Pi−1,j−1 .Swap(i, j)
end ifelse
Pi,j ← Pi−1,jend ifend forend forreturn Pn,kIf the ith and the (i+1)th values must be consecutive, we define Ii,j = Ii+1,j+1 .Swap(i, j),
as in C’. Algorithm 5 describes the process to obtain A′ .
Algorithm 5 Construct A′ .
In,k ← πDD for {en }for i = n − 1 to 0 do
for j = k to 0 do
if j < k thenif j-th and (j + 1)-th element must be consecutive thenIi,j ← Ii+1,j+1 .Swap(i, j)
else
Ii,j ← Ii+1,j ∪ Ii+1,j+1 .Swap(i, j)
end ifelse
Ii,j ← Ii+1,j
end ifend forend forsufk ← πDD for {en }for i = k + 1 to n do
sufi = sufi−1
for j = k + 1 to i − 1 dosufi ← sufi ∪ sufi−1 .Swap(i, j)
end forend forreturn sufn × I0,0

Implicit Generation of Pattern-Avoiding Permutations Based on πDD13n,σ1. Generate Sn
2. Generate Cn(σ)
3. Calculate Sn＼Cn(σ)

classical
vincularclassical

Step C
Step C’
vincularbivincular

Step B

Step A
Step A’bivincular

Avn(σ)

Figure 9: The summary of our algorithms.

4.5

Summary of our algorithms

Our algorithms can be summarized as the 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 diﬀerence of Sn and Cn (σ),
and hence obtain Avn (σ). This procedure is illustrated in Fig. 9.

5Experimental Results

We implemented our algorithm in C++ and carried out computational experiments. We compared the performance of our algorithm to that of the naive method,which generates all n-permutations and, for each n-permutation, decides whether
it contains σ by checking the order isomorphism between all k-subsequences andσ.
Tables 2 and 3 show the results for the generating permutations avoiding aclassical pattern. The tables show the best, the worst, and the average computation
time and memory consumption for generating all patterns with length k = 2,3,4,
and 5. Note that the naive method both stores and outputs all pattern-avoiding
permutations as a list of arrays. In almost all cases, our algorithm is more eﬃcientthan the naive method. For example, in n = 11, our method requires only 0.3% of
the time and 1% of the memory required by the naive one. It should be noted that
there are diﬀerences between the best and worst performance for the same case in
the results of our algorithm, while the naive method hardly shows any diﬀerences.
However, in almost all worst-case scenarios, the performance of our algorithm isbetter than the best-case scenario of the naive one. Computation time and memory
consumption of both methods increase exponentially with respect to n, but ouralgorithm has a smaller growth rate than the naive method.

14

Yuma Inoue, Takahisa Toda and Shin-ichi Minato

Table 3: Memory consumption (kB) 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
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
k
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
1072
1072
1072
1072
1072
1072
1072
1072
1072
1072
1072
1072
—
—
—
—
—
—
—
—
—
—
—
—

Naive Method
k
3
4
5
1332
2160
5756
1336
2162
5759
1340
2164
5764
1600
10316
19460
1600
10319
19463
1600
10324
19468
3476
74684
2959403476
74686
2959433476
74688
2959486796 361444 2884764
6796 361447 2884767
6796 361448 2884768
—
—
—
—
—
—
—
—
——
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—

Table 2: Computation time (s) 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
k
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

2
0.012
0.014
0.016
0.056
0.058
0.060
0.492
0.494
0.496
5.420
5.446
5.512
—
—
—
—
—
—
—
—
—
—
—
—

Naive Method
k
3
4
0.012
0.032
0.017
0.038
0.024
0.044
0.120
0.420
0.121
0.448
0.124
0.480
1.148
5.684
1.170
6.135
1.184
6.596
13.12987.94613.29294.40613.457 100.654
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—

5
0.044
0.050
0.064
0.732
0.776
0.836
15.77316.97018.525409.694429.715452.252
—
—
——
—
—
—
—
—
—
—
—

15

100
10
1
0.1
0.01
0.001
0

naive
πDD

1

2

3

4

5

6

k

7

8

9

10

Figure 10: Computation time whenn = 10.

average memory usage (byte)

average computation time (sec)Implicit Generation of Pattern-Avoiding Permutations Based on πDD

1G
100M

naive
πDD

10M
1M

1

2

3

4

5

6

7

8

9

10

k

Figure 11: Memory consumption
when n = 10.

Figure 10 and 11 show the results for classical patterns. These results show theaverage time and memory consumption for all pattern, where n is fixed at 10 and k
is varied. Memory consumption of the naive method is proportional to the numberof pattern-avoiding permutations, but that of the πDD method decreases whenk ≥ 5. This shows that πDD can achieve high compression when the cardinality ofthe 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, the computation time of the naive)nmethod is in proportion to k , which is the number of subsequences that must be
checked.
Table 4 presents the results for vincular patterns. We generated Baxter permutations, because there are the huge number of vincular patterns for each k,which is k! · 2k−1 . Baxter permutations are defined as avoiding the two vincularpatterns, 31 42 and 24 13, and appear in many mathematical problems [1, 6, 7].
Our algorithm generates Avn (31 42, 24 13) = Sn \ (Cn (31 42) ∪ Cn (24 13)). On
the other hand, the naive method checks the order isomorphism between all ksubsequences 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 forclassical patterns. Our algorithm is faster and consumes less memory than thenaive method.
When n = 15, the time for calculating the diﬀerence Sn \ Cn (σ) is 1.110 s,
which is about 2% of the entire computation time. In general, calculating the set
diﬀerence for sets with a large cardinality without πDDs is not eﬃcient, but, πDD’s
diﬀerence operation is not bottleneck in this problem. Most of the computation
time is due to the Cartesian product operations between three πDDs, which require
46.020 s.
The number of permutations and the size of the corresponding πDD are shownin Table 5, where it is clear that πDD achieves a high compression ratio.

16

Yuma Inoue, Takahisa Toda and Shin-ichi Minato

Table 4: Experimental results for generating Baxter permutations.
πDD Method
Naive MethodnB(n) Time (s) Memory (kB) Time (s) Memory (kB)
8
10754
0.016
2760
0.036
2752
9
58202
0.028
4164
0.380
5676
0.060
12984
4.888
37864
10
32624011
1882960
0.212
26828
65.556
1811120.908
98924
941.331144290412
11140560
1367329992
3.678
383272——14414499438
13.419824732——152593341586
50.4993151164——
193.704
12403488——
16
16458756586
17 105791986682
745.77940788188——

Table 5: the πDD for Baxter permutations (n = 15).
#permutations #nodes in πDD
Sn1307674368000
105
Cn (31 42) ∪ Cn (24 13)1305081026414
4094585
Avn (31 42, 24 13) = Baxter perm.
2593341586
2158472

n
8
9
10
11
12
13
14
15
16
17
18

( )
123
Table 6: Experimental results for generating Avn.
231
πDD Method
Naive Method
( )
123
#Avn
time (sec) memory (KB) time (sec) memory (KB)
231
5335
0.004
3084
0.024
3080
31240
0.004
3084
0.188
3972
0.020
4196
2.260
20080
20160814220740.052
12948
30.63815656810886503
0.184
26436
444.364
119171289903100
0.916
98656
6962.859
9834280
796713190
3.808
382712——7541889195
15.3571510640——75955177642
62.4083327380——810925547354
254.89612887884——
9148832109645
1016.13250354060
—
—

( )
123
We show the results for bivincular patterns. Specifically, we generated Avn,
231
which is known to be related to chord diagrams, (2+2)-free( posets) and ascent se123
quences [5]. Table 6 presents the result of generating Avn. Both our algo231
rithm and the naive method show better performance than the result on Baxter

Implicit Generation of Pattern-Avoiding Permutations Based on πDD

17permutations( ) because the pattern length, number of patterns, and the cardinality
123of Avnare all decreasing. For n = 13, the πDD method can generate the231
permutations in under 1 s while the naive one requires about 2 h.

6Conclusion

In this paper, we proposed an algorithm for generating several pattern-avoiding
permutations using πDDs. Experimental results show that our algorithm is fasterand consumes less memory than the naive method. In addition, our approach
outputs a πDD on memory, which has rich set operations. This means that we cansubmit additional queries such as membership test or random sampling for the setof pattern-avoiding permutations eﬃciently and immediately.
A future work is to improve further the computation time and memory consumption of our algorithm. Moreover, we are also interested in analyzing the relationship between pattern-avoiding permutations and floorplans. In future work, weplan to develop several functions such as search by criteria and random sampling
to use πDDs to populate a floorplan database.

References[1] E. Ackerman, G. Barequet, and R. Pinter. A Bijection Between Permutations and Floorplans, and its Applications. Discrete Applied Mathematics,
154(12):1674–1684, 2006.
[2] E. Babson and E. Steingrı́msson. Generalized Permutation Patterns and aClassification of the Mahonian Statistics. Séminaire Lotharingien de Combinatoire, 44, 2000.
[3] M. Bóna. Exact Enumeration of 1342-Avoiding Permutations: A Close Link
with Labeled Trees and Planar Maps. Journal of Combinatorial Theory, Series
A, 80(2):257 – 272, 1997.
[4] P. Bose, J. Buss, and A. Lubiw. Pattern matching for permutations. Information Processing Letters, 65(5):277–283, 1998.
[5] M. Bousquet-Mélou, A. Claesson, M. Dukes, and S. Kitaev. (2+2)-free posets,
ascent sequences and pattern avoiding permutations. J. Comb. Theory Ser.
A, 117(7):884–909, Oct. 2010.
[6] H. Canary. Aztec Diamonds and Baxter Permutations. The Electronic Journalof Combinatorics, 17, 2010.
[7] E. Fusy. Bijective Counting of Involutive Baxter Permutations. Fundam. Inf.,
117(1-4):179–188, Jan. 2012.

18

Yuma Inoue, Takahisa Toda and Shin-ichi Minato[8] L. Ibarra. Finding pattern matchings for permutations. Information Processing Letters, 61(6), 1997.
[9] J.West. Sorting twice through a stack. Theoretical Computer Science, 117:303–
313, 1993.
[10] D. E. Knuth. The Art of Computer Programming, volume 1. Addison-Wesley,
1968.
[11] D. E. Knuth. The Art of Computer Programming, volume 3. Addison-Wesley,1973.
[12] D. Marinov and R. Radoičić. Counting 1324-avoiding permutations. The
Electronic Journal of Combinatorics, 9(2), 2003.
[13] S. Minato. Zero-suppressed BDDs for set manipulation in combinatorial problems. Proc. of 30th ACM/IEEE Design Automation Conf.(DAC-93), pages
272–277, 1993.
[14] S. Minato. πDDs: A New Decision Diagram for Eﬃcient Problem Solving in
Permutation Space. Proc. of 14th International Conference on Theory andApplications of Satisfiability Testing, pages 90–104, 2011.
[15] V. R. Pratt. Computing permutations with double-ended queues, parallel
stacks and parallel queues. Proc. of the fifth annual ACM symposium on
Theory of computing, pages 268–277, 1973.
[16] Z. E. Stankova. Forbidden subsequences. Discrete Math., 132:291–316, 1994.
[17] H. Wilf. The patterns of permutations. Discrete Math., 257:575–583, 2002.
[18] B. Yao, H. Chen, C. K. Cheng, and R. L. Graham. Floorplan representations:
Complexity and connections. ACM Transactions on Design Automation ofElectronic Systems, 8(1):55–80, 2003.