2015/09/28 by William Kuszmaul, Kuszmaul, William
Engineering · Computer Science · Biochemistry, Genetics and Molecular Biology · #graph theory and CDMA systems #Algorithms and Data Compression #Genome Rearrangement Algorithms
paper · pdf · doi:10.48550/arxiv.1509.08216
Given a set \Π of permutation patterns of length at most k, we present\nan algorithm for building S\≤ n(\Π), the set of permutations of length\nat most n avoiding the patterns in \Π, in time O(|S\≤ n - 1(\Π)|\n\⋅ k + |Sn(\Π)|). Additionally, we present an O(n!k)-time algorithm\nfor counting the number of copies of patterns from \Π in each permutation in\nSn. Surprisingly, when |\Π| = 1, this runtime can be improved to O(n!),\nspending only constant time per permutation. Whereas the previous best\nalgorithms, based on generate-and-check, take exponential time per permutation\nanalyzed, all of our algorithms take time at most polynomial per outputted\npermutation.\n If we want to solve only the enumerative variant of each problem, computing\n|S\≤ n(\Π)| or tallying permutations according to \Π-patterns, rather\nthan to store information about every permutation, then all of our algorithms\ncan be implemented in O(nk+1k) space.\n Using our algorithms, we generated |S5(\Π)|, \…, |S16(\Π)| for\neach \Π \⊆ S4 with |\Π| > 4, and analyzed OEIS matches. We\nobtained a number of potentially novel pattern-avoidance conjectures.\n Our algorithms extend to considering permutations in any set closed under\nstandardization of subsequences. Our algorithms also partially adapt to\nconsidering vincular patterns.\n