TCS -TR-A-14-78

TCS Technical Report

Generating Sets of Permutations
with Pattern Occurrence Counts Using πDDs
byYuma Inoue, Takahisa Toda and Shin-ichi Minato

Division of Computer Science
Report Series A
October 6, 2014

Hokkaido University
Graduate School ofInformation Science and Technology
Email:

yuma@ist.hokudai.ac.jp

Phone:+81-011-706-7681

Fax:+81-011-706-7683

Generating Sets of Permutations
with Pattern Occurrence Counts Using πDDs
Yuma Inoue
Division of Computer Science
Graduate School of Info. Sci. and Tech.
Hokkaido University
Sapporo, Japan

Takahisa Toda
Graduate School of Information Systems
The University of Electro-Communications
Chofu, Tokyo

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

October 6, 2014

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

1

Introduction

A pattern σ occurs in a permutation π if there is a subsequence in π which is orderisomorphic to σ. Two numerical sequences a = a1 a2 . . . an and b = b1 b2 . . . bm are∗

He also works for JST ERATO Minato Project.

1

2

Yuma Inoue, Takahisa Toda and Shin-ichi Minato

order isomorphic if a and b have the same length and satisfy that ai < aj if andonly if bi < bj for all i, j. Conversely, π avoids σ if σ does not occur in π.
The first research of permutation patterns in computer science is stack sort, inwhich we sort elements through a single stack [1]. Knuth showed that stack sortable
permutations avoid the pattern 231. After permutation patterns were introduced,
many researchers have actively studied the number of permutations which avoid
a given pattern [2, 3]. Moreover, classifications of permutation patterns based onsuch numbers have also been examined. Two patterns σ1 and σ2 are strongly Wilf(k)(k)
equivalent if |Fn (σ1 )| = |Fn (σ2 )| for all non-negative integers n and k, where(k)
Fn (σ) denotes the set of permutations of length n in which σ occurs exactly ktimes [4]. Unfortunately, few results are known about strong Wilf-equivalence, as
stated in the survey [5].
In order to break down the current situation, a computational method canbe useful for researches of strong Wilf-equivalence. Namely, we computationally(k)generate Fn (σ) for a given pattern σ and confirm whether or not two patterns(k)are strongly Wilf-equivalent by comparing |Fn (σ)|. This is not a formal proof,
but we can obtain counter examples to disprove or candidates, which are probably∑(k)strongly Wilf-equivalent classes. Unfortunately, k |Fn (σ)| equals n!, which ishuge even if n is small. Thus, it is important to consider an eﬃcient generation
algorithm.
(0)

The generation problem for pattern-avoiding permutations, i.e. Fn (σ), hasbeen studied actively. Theoretically eﬃcient generation algorithms for some particular patterns were proposed [6, 7]. On the other hand, as an instance of practicalresults, PermLab, which is software enumerating and listing pattern-avoiding permutations, is developed by Albert [8]. However, as far as we know, no algorithm(k)generating Fn (σ) for any k has been proposed.
In this paper, we present a practically eﬃcient algorithm for implicitly gener(k)ating Fn (σ). Our algorithm is based on a permutation decision diagram (πDD),
which is a data structure for a compact representation of sets of permutations [9].
“Implicitly generating” means computing a compressed representation of permutations as πDD, not listing permutations explicitly. πDDs also have rich algebraic
set operations such as union and intersection. The computation time of these
operations depends on the size of πDDs and not on the number of permutations
represented by πDDs. This is a key of our algorithm because almost previous
works focused on polynomial-delay generation algorithms, whose time complexity
depends on the number of permutations.
We carry out experiments to measure the performance of our algorithm. Fromthe experimental results, we guess that the following conjecture holds: all strongly
Wilf-equivalent classes are trivial, i.e., each class consists only of a permutationand its symmetric permutations. In addition, we also present some candidates ofstrongly Wilf-equivalent classes for generalized patterns, vincular patterns [10]. We
hope that our algorithm could be a useful tool for promoting researches of strong
Wilf-equivalence.

Generating Sets of Permutations

with Pattern Occurrence Counts Using π DDs

3

The rest of this paper is organized as follows. Section 2 introduces permutation(k)patterns and πDDs. Section 3 presents our algorithm for generating Fn (σ). Section 4 shows experimental results by a program based on our algorithm. Section 5
concludes this paper.

2

Preliminaries

2.1

Permutations

A permutation of length n is a bijection from {1, 2, ..., n} to itself, and hereafter,
we call it an n-permutation for brevity. Let π be an n-permutation. We write apermutation in the one-line form as π = π(1)π(2) . . . π(n), and denote πi = π(i).
For example, π = 3421 is a 4-permutation and π3 = 2. We define Sn as the set of
all n-permutations.
Multiplication on permutations x and y is defined as x·y = yx1 yx2 . . . yxn , whichis y after applying x. In other words, if we consider a one-line form of a permutation
as a numerical sequence, a multiplication x · y is a rearrangement of y according tothe order of x. For example, let π be a 5-permutation, then 54321 · π = π5 π4 π3 π2 π1
is the reverse of π.
A transposition is a permutation by which exactly two elements are swapped.
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 of at most n−1 transpositions using a straight selection
sorting algorithm. This algorithm repeats to swap the value k and the kth element,
where k runs from n to 1. For example, we consider a decomposition of the
permutation 43152 into a product of transpositions. The 5th element of 43152
is 2, hence we exchange 5 and 2, and obtain 43152 = 43125 · τ2,5 . Since the 4th
element of 43125 is 2, we then obtain 43152 = 23145 · τ2,4 · τ2,5 . Repeating thisprocess, we finally obtain 43152 = τ1,2 · τ1,3 · τ2,4 · τ2,5 .

2.2

Permutation Patterns

A permutation σ occurs in a permutation π if there is at least one subsequence in
π which is order isomorphic to σ, where such a subsequence does not have to beconsecutive in π. In other words, let l be the length of σ, then σ occurs in π if there
are indices 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 pattern 312
occurs in the permutation 4213 because 423 and 413 are order isomorphic to thepattern 312. On the other hand, a permutation π avoids a pattern σ if there is no
occurrence of σ in π.
The pattern occurrence count of σ in π is the number of distinct subsequences in(k)the permutation π which are order isomorphic to the pattern σ. Hereafter, Fn (σ)

4Yuma Inoue, Takahisa Toda and Shin-ichi Minato

denotes the set of n-permutations in which σ occurs exactly k times. Two patterns
σ1 and σ2 are Wilf-equivalent if they have the same number of n-permutations(0)(0)
which avoid the patterns, i.e., |Fn (σ1 )| = |Fn (σ2 )| holds for all positive integers n. More generally, two patterns σ1 and σ2 are strongly Wilf-equivalent if(k)(k)|Fn (σ1 )| = |Fn (σ2 )| holds for all non-negative integers n and k.
The problem considered in this paper can be stated as follows: given a positive(k)integer n and a pattern σ, generate Fn (σ) for all non-negative integers k.

2.3

Permutation Decision Diagrams

A permutation decision diagram (πDD) is a data structure representing a set of
permutations canonically [9]. πDDs have eﬃcient set operations for permutation
sets. Our algorithm is based on the compact representation and rich set operations of πDDs. πDDs are derived from zero-suppressed binary decision diagrams(ZDDs) [11], which are decision diagrams for sets of combinations. πDDs consistof five components: internal nodes with a transposition label, 0-edges, 1-edges, the0-sink, and the 1-sink. An example of a πDD is shown in Fig. 1.
A πDD forms a binary decision diagram: each internal node has exactly a 0edge and a 1-edge. Each path on a πDD represents a permutation: if a 1-edge
originates from τx,y , the decomposition of the permutation contains τx,y , while a0-edge from τx,y means that the decomposition excludes τx,y . If a path reaches the1-sink, the permutation corresponding to the path is in the set represented by the
πDD. On the other hand, if a path reaches the 0-sink, the permutation is not in
the set. For a node N , we call the subgraph pointed to by its 0-edge and 1-edge
the left subgraph and the right subgraph of N , respectively.
A πDD has a compact and canonical form if we fix the order of transpositions
and apply the following two reduction rules:(1) Merging rule: share all nodes having the same labels, left subgraphs, and right
subgraphs.
(2) Deletion rule: delete all nodes whose 1-edge points directly to the 0-sink.
These rules are illustrated in Fig. 2. We introduce the order of transpositions <so that τx1 ,y1 < τx2 ,y2 is true if y1 > y2 holds or y1 = y2 and x1 < x2 holds.
The size of a πDD (i.e. the number of nodes in a πDD) can grow exponentiallywith respect to the length of permutations. In many practical cases, though, a
πDD demonstrates high compression ratio.
In addition, πDDs support eﬃcient set operations such as union and intersection. Table 1 shows the πDD operations used in this paper. The computation timeof πDD operations depends on only the size of πDDs, not on the cardinality of thesets represented by the πDDs. Note that Cartesian product of πDDs diﬀers fromusual Cartesian product of sets: Cartesian product of two πDDs P and Q means
the set of all products for all pairs of permutations in P and Q.

Generating Sets of Permutations

0

τ3,4
0
0

τx,y

τ1,4

τx,y

τx,y

0

1

0

1

P0
0

1

τ1,2

5

τx,y

1

1 0 τ2,3

P0

1

0

1

P1

P0

(1) merging ruleFigure 1:
The πDDfor a permutation set{4132, 2143, 3412}.

2.4

with Pattern Occurrence Counts Using π DDs

P1

P0(2) deletion ruleFigure 2: Two reduction rules on πDDs.

Multiset of Permutations

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 a function. Here, f (π) is a multiplicity of a permutation π and we use thenotation 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 multiplication of 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 means Cartesian
product of permutation sets like that of πDDs.
A set of permutations weighted by pattern occurrence counts can be represented
by a multiset. Given a positive integer n and a pattern σ, Pn,σ = ⟨Sn , fσ ⟩ denotes
the set of n-permutations weighted by the pattern occurrence counts of σ, i.e.,fσ (π) equals the pattern occurrence counts of σ in π. Our algorithm which will(k)
be described in Sect. 3 generates Pn,σ at first, and next computes Fn (σ) = {π |Pn,σ (π) = k} from Pn,σ .

2.5

πDD Vector

In this paper, we want to handle multisets of permutations. But πDDs cannot
represent multisets. To overcome this problem, we use a πDD vector, proposedin [12]. A πDD vector represents a multiset of permutations based on a binary

Table 1: πDD operations on two πDDs P and Q.
P.T op
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 diﬀerence {π | π ∈ P and π ∈/ Q}.
return swap {π · τx,y | π ∈ P }.
return Cartesian product {α · β | α ∈ P and β ∈ Q}.

6

Yuma Inoue, Takahisa Toda and Shin-ichi Minato
P2

P1

P0

τ2,4

τ3,4

τ2,4
Permutation

τ1,3

τ2,3
τ1,2

0

1
{1342}

0

τ2,3
τ1,2

1

0

1342
2134
2143
4213
4132

(P2,P1,P0) Multiplicity(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 3: An example of a πDD vector.

⃗
Table 2: πDD operations on πDD vectors P⃗ and Q.
⃗ ⊎Q
⃗
P
⃗
P · τ (x, y)⃗ .numberof (π)
P⃗ such that R(π)⃗⃗ (π) + Q(π)⃗
Return multiset sum R=Pholds.
′⃗
Return swap P = (P0 · τ (x, y), P1 · τ (x, y), . . . , Pm · τ (x, y)).
⃗ (π).
Return P

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 the multiplicity of π in P⃗ . If a permutation π is in Pi , theith bit of the binary representation of P⃗ (π) is 1, and otherwise 0. In other words,∑iP⃗ (π) = m
i=0 2 · [π ∈ Pi ] holds, where [x] equals 1 if x is true, and otherwise 0.
Figure 3 shows an example of a πDD vector. πDD vectors have multiset operations.
Table 2 shows some πDD vector operations which were proposed in [12].

3Main Results

Our algorithm is divided into two parts: generation of Pn,σ and generation of(k)
Fn (σ) from Pn,σ . The first part is described in Sects. 3.1 and 3.2. The second
part is described in Sect. 3.3.

3.1

Existing Method and Its Extension

We proposed a generation algorithm for non-weighted occurrence using πDD in [13].
In [13], in order to generate pattern-avoiding permutations, we generate Sn andCn (σ), which is the set of all n-permutations in which a given patten occurs atleast once, and calculate the set diﬀerence Sn \ Cn (σ). Thus, in order 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 σ.

Generating Sets of Permutations

with Pattern Occurrence Counts Using π DDs

7

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
for i = 0 to l do
if ki = 1 then
⃗ ←R
⃗ ⊎ P⃗
R
end ifP⃗ ← (∅, P0 , P1 , . . . , Pm+i )end for⃗return R
The algorithm for generating Cn (σ) in [13] is sketched as follows. Let l be thelength of σ. At first, we generate all numerical sequences satisfying the following
conditions: it is order isomorphic to σ and all the elements(n) in it are less than orequal to n. The number of such numerical sequences is l . Next, we generate alln-permutations such that the above numerical sequences appears as their subsequence. In order to do this, it is suﬃcient to embed the numerical sequences insequences of length n without changing their order. Here, we assign other numbers with other positions in any order. Since all order isomorphic sequences areembedded in all possible positions, this process generates Cn (σ).
In [13], we used Cartesian product operations of πDDs to realize this process.
As described in Sect. 2.1, a multiplication of permutations can be considered as arearrangement. Since the above embedding can be considered as a rearrangement,
we can generate Cn (σ) by calculating the Cartesian product of the two πDDs: thepermutations which represent all possible positions and the permutations which
represent all order isomorphic numerical sequences. These correspond to the πDDs
C and B ∗ A in [13], respectively.
Here, note that some embeddings cause duplications. For example, both 413
and 524, which are order isomorphic to 312, are embedded in 52413. In otherwords, 312 occurs (at least) 2 times in 52413. The number of such duplications isequal to pattern occurrence counts of a given pattern in a permutation. Since theexisting method uses πDD, such duplications are not counted. But by using theCartesian product of πDD vectors instead of πDDs, we can generate the multisetof permutations whose multiplicity represents the pattern occurrence count, i.e.
Pn,σ . Unfortunately, however, Cartesian product of πDD vectors have not everbeen proposed. We introduce the operation in the next subsection.

3.2

Cartesian Product of πDD Vector

Cartesian product between two πDDs P and Q was defined as follows ([9]):P ∗ Q = (P ∗ Ql ) ∪ ((P ∗ Qr ) · τ (x, y)),

8

Yuma Inoue, Takahisa Toda and Shin-ichi Minato

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 werealready proposed in [12] as shown in Table 2. However, some Qi in the array of⃗ can have distinct transpositions in their root nodes. We need to define Q⃗ L andQR⃗
Q , and the pair (x, y) for τ (x, y) appropriately.
We use the pair (xs , ys ) such that τxs ,ys is the smallest transposition in theroot nodes of Q1 , Q2 , . . . , Qm , where the order of transpositions is introduced in
Sect. 2.2. For example, for the πDD vector illustrated in Fig. 3, (xs , ys ) is (2, 4)
because the root nodes of P0 , P1 , and P2 are τ2,4 , τ3,4 , and τ2,4 , respectively, and⃗ L and Q⃗ R as follows:
the smallest transposition is τ2,4 . Here, we define Q{
Qi if Qi .T op ̸= τxs ,ys ,
L
L
L
L
L
⃗
Q
= (Q0 , Q1 , . . . Qm ), where Qi =Qli otherwise.
{∅ if Qi .T op ̸= τxs ,ys ,
R
R
R
R
R
⃗
Q
= (Q0 , Q1 , . . . Qm ), where Qi =Qri otherwise.
It works because Qi whose root node is not labeled by τx,y is equivalent to theπDD whose root node has the label τx,y and Qi as the left subgraph, the 0-sink as
the right subgraph due to the deletion rule in Sect. 2.2.
We also need to define the recursion basis. The recursion basis means thatfor all i, Qi consists only of a sink node. If every root node is a 0-sink, the⃗⃗Cartesian product is an empty set. Otherwise, Q(12. . . n) = k and Q(π)= 0 for⃗⃗the other permutations π hold, and then P ∗ Q equals the scalar multiplication
k · P⃗ . Algorithm 1 represents an algorithm for a scalar multiplication of a πDD
vector based on the multiset sum of 2i · P⃗ = (∅, . . . , ∅, P0 , . . . , Pm ).
| {z }i

Cartesian product for πDD vectors is described in Algorithm 2. In conclusion,by using this Cartesian product of πDD vectors, we can implicitly generate Pn,σ .

3.3

(k)

Generation of Fn (σ)

We propose an algorithm generating Pn,σ . However, in order to computationallycheck whether or not strong Wilf-equivalence between σ1 and σ2 holds, we must(k)(k)
calculate the cardinalities of Fn (σ1 ) and Fn (σ2 ) for 0 ≤ k ≤ M , where M
denotesthe maximum number of occurrences of a given pattern. Note that M ≤(n )l holds, where l is the length of the pattern. In this subsection, we propose the(k)algorithm constructing the πDDs for Fn (σ) for 0 ≤ k ≤ M from the πDD vector
for Pn,σ .

Generating Sets of Permutations

with Pattern Occurrence Counts Using π DDs

9Algorithm 2 Cartesian product of two πDD vectors P⃗ = (P0 , P1 , . . . , Pm′ ) and⃗ = (Q0 , Q1 , . . . , Qm ).
Q{We suppose the 0-sink with τ0,0 and the 1-sink with τ1,1 for convenience.}transposition t ← τ0,0
for i = 0 to m do
if Qi .T op < t thent ← Qi .T op
end ifend for
if t = τ0,0 thenreturn (∅)
else if t = τ1,1 then⃗return Q.numberof(12 . . . n) · P⃗else
for i = 0 to m do
if Qi .T op = t thenlRr
QL
i ← Qi , Qi ← Qi
else
R
QL
i ← Qi , Qi ← ∅end ifend for⃗ L ) ⊎ ((P⃗ ∗ Q⃗ R ) · t)
return (P⃗ ∗ Q
end if(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:∩∪
Fn(k) (σ) ={Pi | ki = 1} \{Pi | ki = 0},
0≤i≤m

0≤i≤m

where ki means ith bit of the binary representation of k. This algorithm costs(k)O(m) πDD operations. Hence, computation of Fn (σ) for 0 ≤ k ≤ M costsO(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⃗ . 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 =∅ 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
calculations of the above recursions. An algorithm generating Sn is also shown10

Yuma Inoue, Takahisa Toda and Shin-ichi Minato

Algorithm 3 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 \ Wbinend forend forinput:n,ComputeCartesian product~
P~ , Q

Algorithms in [13]Pn,

C, B ⇤ A

Transform into
πDD vector

Algorithm 3

output:Fn(k) ( )Figure 4: The summary of our algorithm.
in [13]. The number of valid binary representations whose prefix can be consecutive“don’t care” symbols is 20 +21 +. . .+2m = 2m+1 −1 = O(M ). For each calculation(k)of Wk , we use only one πDD operation. Therefore, we can generate Fn (σ) for0 ≤ k ≤ M by O(M ) πDD operations based on the recursions. Algorithm 3 showsa pseudo code of this algorithm. This algorithm temporarily uses W(0...0ki ...k0 )2 torepresent W(∗...∗ki ...k0 )2 .

3.4

Summary of Our Algorithm and Its Extension

Our algorithm can be summarized as follows. First, we construct the πDDs for C
and B ∗ A by the algorithms described in [13]. Second, we transform these πDDs
⃗ = (B ∗ A). Third, we calculate theinto the πDD vectors, that is, P⃗ = (C) and Q⃗ which is the πDD vector for Pn,σ . Finally, we calculate
Cartesian product P⃗ ∗ Q,(k)the πDDs for Fn (σ) from the πDD vector for Pn,σ using Algorithm 3. This
process is illustrated in Fig. 4.
In addition, we can easily extend our algorithm for other generalized patterns
such as vincular patterns [10] and bivincular patterns [14]. In [13], in order toextend the algorithm to deal with such patterns, we only change A and C to A′(k)
and C′ , respectively. Thus, by using A′ and C′ in [13], we can generate Fn (σ) forsuch patterns.

Generating Sets of Permutations with Pattern Occurrence Counts Using π DDs

11

(k)

Table 3: Computation time (sec) for generating Fn (σ).
n

9

10

11

12

4

best
averageworst
best
averageworst
best
averageworst
best
average
worst

2
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.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.068
0.087
0.120
0.956
1.232
1.524
11.67315.68319.809144.141231.141301.135

2
0.316
0.322
0.328
3.792
3.900
4.008
51.59553.67355.752———

Naive Method
l
3
4
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.968
1.037
1.128
25.52227.31429.482750.307774.683
806.186———-

Experimental Results

We implemented our algorithms in C++ and carried out experiments on a 3.20 GHz
CPU machine with 64 GB memory. We compared the performance of our algorithm
to that of a naive method. The naive method generates all n-permutations and, foreach n-permutation, enumerates the pattern occurrence counts of σ by checking
the order isomorphism between all k-subsequences and σ.
(k)

Table 3 shows computation time for the entire process of generating Fn (σ).
The table represents the best, the worst, and the average computation time overall patterns with length l = 2,3,4, and 5, respectively. Note that computation timeof our πDD method only include the constructions of πDDs, meaning that we do(k)not output permutations explicitly. The naive method only counts |Fn (σ)|, andnot explicitly outputs permutations too. For n = 10 and l = 5, our algorithm isabout 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 that this is because the diﬀerence of theparameters dominating computation time: the computation time of a πDD depends
on the size of the πDD( ) while that of the naive method depends on the number ofsubsequences, i.e. nl . In practical cases, the size of a πDD tends to become small
when the set of permutations is sparse or very dense. When σ is a long pattern,(k)Fn (σ) tends to be dense for small k and to be sparse for large k. That is, thelonger the length of a pattern is, the smaller the πDDs for the pattern tend to be.
Table 4 describes memory consumption and the size of πDDs for generat(k)ing Fn (σ). We do not describe memory consumption of the naive method because
the naive method does not store the permutations and uses a small memory. Tables 3 and 4 confirm the computation time is proportional to the size of πDDs.
Memory consumption of our algorithm grows exponentially with respect to n. We(k)cannot calculate F13 (σ) because of memory shortage. However the total size of(k)πDDs for Fn (σ) is smaller than the number of all n-permutations n!. This shows(k)that πDDs achieve compact representations of Fn (σ).

12Yuma Inoue, Takahisa Toda and Shin-ichi Minato(k)

Table 4: Memory consumption and the size of πDDs for generating Fn (σ).
∑M

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

(k)

memory consumption (kB)
k=0 {the size of πDDs for Fn (σ)}
l
l
2
3
4
5
2
3
4
5
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 5: Candidates of strongly Wilf-equivalent classes for vincular patterns.
124-3,134-2,2-134,2-431,3-124,3-421,421-3,431-2 132-4,1-324,142-3,2-314,3-241,413-2,423-1,4-231
2-14-3,2-41-3,3-14-2,3-41-2
1342,1432,2341,2431,3124,3214,4123,4213
13-24,24-13,31-42,42-31
1-423,231-4,241-3,2-413,314-2,3-142,324-1,4-132

In the experiments, we could not find non-trivial classes for 2 ≤ l ≤ 8. In otherwords, we computationally prove that there are only trivial strongly Wilf-equivalentclasses for 2 ≤ l ≤ 8. Note that it is trivial that a pattern and its symmetricpermutations, i.e. its reverse, complement, and inverse, are always strongly Wilfequivalent. Since we carried out experiments only for 2 ≤ n ≤ 12, many non-trivial
candidates are found for l = 9. But the experiments for n > 12 may confirm there
are only trivial classes for l = 9. In fact, in the case l = 8, the results for n < 12
has many non-trivial candidates while the result for n = 12 confirms there are only
trivial classes. Therefore, we propose a conjecture: all strongly Wilf-equivalentclasses are trivial for all l. As far as we know, this conjecture have never been
proven.
We also carried out experiments for vincular pattens [10] for 2 ≤ n ≤ 12.
Vincular patterns are generalized patterns with adjacent constraints: if there isno hyphen (-) between σi and σi+1 , the corresponding elements in a permutationmust be adjacent. Table 5 provides non-trivial candidates for the vincular pattens
with length 4. The classes in the left column have been proved in [4]. On theother hand, the classes in the right column have never been proven as far as weknow. Thus, we propose the following conjectures: the vincular pattens (1342,
1432), (1-423, 2-413), and (132-4, 142-3) are strongly Wilf-equivalent respectively.

5

Conclusion

In this paper, we proposed an algorithm implicitly generating Pn,σ for given nand σ using πDD vectors. Furthermore, we provided an algorithm computing the(k)πDDs representing Fn (σ) for each k from the πDD vector for Pn,σ . Experimental

Generating Sets of Permutations with Pattern Occurrence Counts Using π DDs

13results present that our algorithm is practically faster than a naive method, andsuggest conjectures about strongly Wilf-equivalence.
Future work is to improve the performance of our algorithms, especially memory
consumption which is a bottleneck of our algorithm. Experiments for larger n andk, multiple patterns, and other general patterns are also interesting for us. We
wish that someone will prove our conjectures.

References[1] Knuth, D.E.: Fundamental Algorithms. Third edn. Volume 1 of The Art ofComputer Programming. Addison-Wesley, Reading, Massachusetts (1997)[2] Bóna, M.: Exact enumeration of 1342-avoiding permutations: A close linkwith labeled trees and planar maps. Journal of Combinatorial Theory, Series
A 80(2) (1997) 257–272[3] Marinov, D., Radoičić, R.: Counting 1324-avoiding permutations. The Electronic Journal of Combinatorics 9(2) (2003)[4] Kasraoui, A.: New Wilf-equivalence results for vincular patterns. European
Journal of Combinatorics 34(2) (2013) 322–337[5] Steingrı́msson, E.: Some open problems on permutation patterns. London
Mathematical Society Lecture Note Series (2013) 239–263[6] Wilf, H.: The patterns of permutations. Discrete Math. 257 (2002) 575–583[7] Dukes, W., Flanagan, M., Mansour, T., Vajnovszki, V.: Combinatorial graycodes for classes of pattern avoiding permutations. Theoretical Computer
Science 396(13) (2008) 35–49[8] Albert, M.:
Permlab:Software for permutation
http://www.cs.otago.ac.nz/staﬀpriv/malbert/permlab.php (2012)

patterns.

[9] Minato, S.: πDDs: A new decision diagram for eﬃcient problem solving in
permutation space. Proc. of 14th International Conference on Theory andApplications of Satisfiability Testing (2011) 90–104[10] Babson, E., Steingrı́msson, E.: Generalized permutation patterns and a classification of the Mahonian statistics. Séminaire Lotharingien de Combinatoire
44 (2000)[11] Minato, S.: Zero-suppressed BDDs for set manipulation in combinatorial
problems. Proc. of 30th ACM/IEEE Design Automation Conf.(DAC-93)(1993) 272–277

14Yuma Inoue, Takahisa Toda and Shin-ichi Minato[12] Kawahara, J., Saitoh, T., Yoshinaka, R., Minato, S.: Counting primitive
sorting networks by πDDs. Technical Report TCS-TR-A-11-54, Division ofcomputer science, Hokkaido University (2011)[13] Inoue, Y., Toda, T., Minato, S.: Implicit generation of pattern-avoiding
permutations based on πDD. Technical Report TCS-TR-A-13-67, Division ofcomputer science, Hokkaido University (2013)[14] Bousquet-Mélou, M., Claesson, A., Dukes, M., Kitaev, S.: (2+2)-free posets,
ascent sequences and pattern avoiding permutations. J. Comb. Theory Ser. A
117(7) (Oct 2010) 884–909