Permutation Pattern Matching

Problem Description

Permutation Pattern Matching (PPM) is an NP-complete pattern matching problem. Given a permutation T (the text) and a permutation P (the pattern) the question is whether there exists a matching of P into T. A matching is a subsequence of T that has the same relative order as P. For example the permutation T = 53142 (written in one-line representation) contains the pattern 231, since the subsequence 342 of T is order-isomorphic to 231 (i.e. the smallest element is in the third position, the second smallest in the first position and the largest in the second position).

The permutations T and P are encoded as binary predicates, e.g. T=132 is encoded as t(1,1). t(2,3). t(3,2). Additionally, patternlength/1 describes the length of the pattern P. The output predicate solution/2 contains an encoding of the matching of P into T (if it exists).

Random instances can be easily generated for this problem.

Predicates

• Input: t/2, p/2, patternlength/1

• Output: solution/2

Input format

Output format

Example(s)

In this instance we are given the permutation 53142 as text and 231 as the pattern. The only subsequence that matches the text is 342.

Thus, the output of the solver should look like:

 solution(3,2) solution(2,4) solution(1,3) 

Problem Peculiarities

Type: Search Competition: Both

Notes and Updates

Author(s)

• Author: Andreas Pfandler
  • Affiliation: DBAI, Vienna University of Technology, Austria