|
Size: 1665
Comment: Permutation Pattern Matching added
|
← Revision 9 as of 2013-03-22 08:01:13 ⇥
Size: 2113
Comment:
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 2: | Line 2: |
<<TableOfContents>> |
|
| Line 17: | Line 15: |
| 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). |
Note that: |
| Line 22: | Line 17: |
| Random instances can be easily generated for this problem. | 1. Both text and pattern consist only of numbers. 1. A text of length {{{m}}} is a permutation on {{{ {1,...,m} }}}, i.e., every element appears exactly once. 1. A pattern of length {{{n}}} is a permutation on {{{ {1,...,n} }}}. Hence {{{241}}} is not a pattern. But note that {{{241}}} might be matching! (For example: {{{241}}} is a matching from the pattern {{{231}}} into the text {{{32451}}}.) |
| Line 31: | Line 29: |
| 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. |
|
| Line 34: | Line 34: |
| The output predicate {{{solution/2}}} contains an encoding of the matching of P into T (if it exists). |
|
| Line 41: | Line 43: |
{{{ solution(3,2) solution(2,4) solution(1,3) }}} |
{{{ solution(1,3). solution(2,4). solution(3,2). }}} |
| Line 48: | Line 51: |
Random instances can be easily generated for this problem. |
|
| Line 55: | Line 61: |
| * Author: Andreas Pfandler | * Author: Martin Lackner, Andreas Pfandler |
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).
Note that:
- Both text and pattern consist only of numbers.
A text of length m is a permutation on {1,...,m} , i.e., every element appears exactly once.
A pattern of length n is a permutation on {1,...,n} . Hence 241 is not a pattern. But note that 241 might be matching! (For example: 241 is a matching from the pattern 231 into the text 32451.)
Predicates
Input: t/2, p/2, patternlength/1
Output: solution/2
Input format
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.
Output format
The output predicate solution/2 contains an encoding of the matching of P into T (if it exists).
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(1,3). solution(2,4). solution(3,2).
Problem Peculiarities
Type: Search Competition: Both
Random instances can be easily generated for this problem.
Notes and Updates
Author(s)
- Author: Martin Lackner, Andreas Pfandler
- Affiliation: DBAI, Vienna University of Technology, Austria