<p>I finally managed to dig out <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.87.9739&amp;rep=rep1&amp;type=pdf">a nice survey by Kitaev and Mansour</a>, which gives pointers to the literature related to permutation pattern matching on  "usual"/signed/coloured permutations and words.</p>

CC BY-SA 3.0
2011-07-04T08:33:12.420Z
2011-07-04T08:33:12.420Z
Anthony Labarre
<p>Baars, Löh, and Swierstra implemented <a href="http://journals.cambridge.org/action/displayAbstract?fromPage=online&amp;aid=254709&amp;fulltextType=RL&amp;fileId=S0956796804005143" rel="nofollow"><em>Permutation Parsers</em></a> 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.</p>

CC BY-SA 3.0
2011-06-29T13:38:26.100Z
2011-06-29T13:38:26.100Z
Dave Clarke
<p>You should start from 
Revital Eres, Gad M. Landau, Laxmi Parida: <a href="http://dx.doi.org/10.1089/cmb.2004.11.1050" rel="nofollow">Permutation Pattern Discovery in Biosequences</a>. Journal of Computational Biology 11(6): 1050-1060 (2004).</p>

CC BY-SA 3.0
2011-06-29T14:07:59.100Z
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".
Anthony Labarre
CC BY-SA 3.0
2011-06-29T15:38:08.667Z
@Labarre I agree with your comment. Should I delete my reply?
Gianluca Della Vedova
CC BY-SA 3.0
2011-06-29T15:43:54.090Z
Please don't delete.  Your answer, and Labarre's comment, helped me understand the question better.
Aaron Sterling
CC BY-SA 3.0
2011-06-29T16:20:43.763Z
@Aaron Sterling Then we should edit the question, shouldn't we?
Gianluca Della Vedova
CC BY-SA 3.0
2011-06-29T21:47:01.977Z
I think the question is relatively clear as it stands.
Suresh Venkat
CC BY-SA 3.0
2011-06-29T13:35:24.323Z
2011-06-29T13:35:24.323Z
Gianluca Della Vedova
<p>Loosely speaking, permutation pattern matching deals with problems of the following kind: </p>

<blockquote>
  <p>Given permutations $\pi$ in $S_n$ and $\sigma$ in $S_m$, with $m\leq n$, does $\pi$ contain a <a href="http://en.wikipedia.org/wiki/Subsequence">subsequence</a> $\tau$ of length $m$ whose elements are ordered according to $\sigma$?</p>
</blockquote>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2014-02-12T05:29:14.963Z
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.
abigail3306
<permutations><string-matching>
Permutation pattern matching in strings
Anthony Labarre
# Permutation pattern matching in strings

(Asked by: username_0 on 2011-06-29)

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](http://en.wikipedia.org/wiki/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.

**Tags:** permutations, string-matching

> **Comments:**
> **username_1**: 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.  

---

## 3 answers

### Answer by username_0 on 2011-07-04. Score: 5 | Accepted answer

I finally managed to dig out [a nice survey by Kitaev and Mansour](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.87.9739&rep=rep1&type=pdf), which gives pointers to the literature related to permutation pattern matching on "usual"/signed/coloured permutations and words.


---

### Answer by username_2 on 2011-06-29. Score: 3

Baars, Löh, and Swierstra implemented [*Permutation Parsers*](http://journals.cambridge.org/action/displayAbstract?fromPage=online&aid=254709&fulltextType=RL&fileId=S0956796804005143) 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.


---

### Answer by username_3 on 2011-06-29. Score: 0

You should start from
Revital Eres, Gad M. Landau, Laxmi Parida: [Permutation Pattern Discovery in Biosequences](http://dx.doi.org/10.1089/cmb.2004.11.1050). Journal of Computational Biology 11(6): 1050-1060 (2004).

> **Comments:**
> **username_0**: 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".  
> **username_3**: @Labarre I agree with your comment. Should I delete my reply?  
> **username_4**: Please don't delete.  Your answer, and Labarre's comment, helped me understand the question better.  
> **username_3**: @username_4 Then we should edit the question, shouldn't we?  
> **username_5**: I think the question is relatively clear as it stands.  

---

