10
$\begingroup$

Loosely speaking, permutation pattern matching deals with problems of the following kind:

Given permutations $\pi$ in $S_n$ and $\sigma$ in $S_m$, with $m\leq n$, does $\pi$ contain a subsequence $\tau$ of length $m$ whose elements are ordered according to $\sigma$?

For example, if $\pi=\langle 3\ 1\ 5\ 4\ 2\ 8\ 6\ 7\rangle$ and $\sigma=\langle 2\ 1\ 3\rangle$, then the subsequence $3\ 1\ 4$ matches $\sigma$. As you can see, we're not looking here for an exact match, but rather for something that "looks like" the specified pattern.

Does anyone know whether work has been conducted on extending permutation pattern matching problems to strings? Google unfortunately did not help, since the well-known pattern matching problem on strings has nothing to do with this.

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ I'm currently doing research in affine permutation patterns. There is some work out there but most of it is only available to those in academia. $\endgroup$ – abigail3306 Feb 12 '14 at 5:29
5
$\begingroup$

I finally managed to dig out a nice survey by Kitaev and Mansour, which gives pointers to the literature related to permutation pattern matching on "usual"/signed/coloured permutations and words.

| cite | improve this answer | |
$\endgroup$
3
$\begingroup$

Baars, Löh, and Swierstra implemented Permutation Parsers for Haskell (Journal of Functional Programming / Volume 14 / Issue 06, pp 635 - 646). These can be used to specify the permutation of a collection of parsers. If each of these parsers is an optional parser for a single character (that is, matches the character or nothing), then you'd have the ingredients you are looking for. I believe that their library is available with GHC.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

You should start from Revital Eres, Gad M. Landau, Laxmi Parida: Permutation Pattern Discovery in Biosequences. Journal of Computational Biology 11(6): 1050-1060 (2004).

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ This does not seem to be the same thing: they are interested in locating groups of characters which occur together, without taking order into account. The same problem on permutations is referred to as "identifying common intervals". $\endgroup$ – Anthony Labarre Jun 29 '11 at 14:07
  • $\begingroup$ @Labarre I agree with your comment. Should I delete my reply? $\endgroup$ – Gianluca Della Vedova Jun 29 '11 at 15:38
  • 1
    $\begingroup$ Please don't delete. Your answer, and Labarre's comment, helped me understand the question better. $\endgroup$ – Aaron Sterling Jun 29 '11 at 15:43
  • $\begingroup$ @Aaron Sterling Then we should edit the question, shouldn't we? $\endgroup$ – Gianluca Della Vedova Jun 29 '11 at 16:20
  • 2
    $\begingroup$ I think the question is relatively clear as it stands. $\endgroup$ – Suresh Venkat Jun 29 '11 at 21:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.