Fast algorithms for finding pattern avoiders and counting pattern occurrences in permutations
William Kuszmaul · Mathematics of Computation · 2016
Given a set Π \Pi of permutation patterns of length at most k k , we present an algorithm for building S ≤ n ( Π ) S_{\le n}(\Pi ) , the set of permutations of length at most n n avoiding the patterns in Π \Pi , in time O ( | S ≤ n − 1 ( Π ) | ⋅ k + | S n ( Π ) | ) O(|S_{\le n - 1}(\Pi )| \cdot k + |S_{n}(\Pi )|) . Additionally, we present an O ( n ! k ) O(n!k) -time algorithm for counting the number of copies of patterns from Π \Pi in each permutation in S n S_n . Surprisingly, when | Π