1993

# Pattern matching for permutations

## Publication

### Publication

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).

Additional Metadata | |
---|---|

Lecture Notes in Computer Science | |

Organisation | School of Computer Science |

Bose, P, Buss, J.F. (Jonathan F.), & Lubiw, A. (Anna). (1993). Pattern matching for permutations. In
Lecture Notes in Computer Science. |