| PATTERN MATCHING FOR PERMUTATIONS # Prosenjit Bose 1 (2007) | |||||||||||||||
Abstract | |||||||||||||||
| Given a permutation T of 1 to n, and a permutation P of 1 to k, for k n, we wish to find a k-element subsequence of T whose elements are ordered according to the permutation P. For example, if P is (1, 2,..., k), then we wish to find an increasing subsequence of length k in T; this special case can be done in time O(n log log n) [CW]. We prove that the general problem is NP-complete. We give a polynomial time algorithm for the decision problem, and the corresponding counting problem, in the case that P is separable---i.e. contains neither the subpattern (3, 1, 4, 2) nor its reverse, the subpattern (2, 4, 1, 3). | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||