A permutation of length ![]()
is a bijective mapping
![]()
; one way to represent it is as the
sequence of numbers ![]()
.
A permutation ![]()
contains permutation ![]()
if ![]()
has a (not necessarily consecutive) subsequence where the relative
ordering of the elements is the same as in ![]()
.
In this case, ![]()
is a subpattern of ![]()
;
otherwise, ![]()
avoids ![]()
.
For example, ![]()
contains the pattern ![]()
, since the subsequence
![]()
is ordered the same way as ![]()
.
On the other hand, the permutation avoids ![]()
: it does
not contain a descending subsequence of 4 elements.
Given permutation ![]()
and ![]()
, the Permutation Pattern problem
is to decide if ![]()
contains ![]()
.
The Permutation Pattern problem is NP-complete.
It can be solved by brute force in time ![]()
, where
![]()
and ![]()
.
This has been improved to ![]()
by Ahal and Rabinovich.
Guillemot and Marx proved that the Permutation Pattern problem
can be solved in time ![]()
(i.e., the Permutation Pattern problem is fixed-parameter tractable
parameterized by the size of the pattern).