Patrón de permutación que coincide en cadenas

10

Hablando en términos generales, la coincidencia de patrones de permutación se ocupa de problemas del siguiente tipo:

Dadas las permutaciones en S n y σ en S m , con m n , ¿ contiene π una subsecuencia τ de longitud m cuyos elementos están ordenados de acuerdo con σ ?πSnorteσSmetrometronorteπ τmetroσ

Por ejemplo, si y σ = 2 1 3 , a continuación, la subsecuencia 3 1 4 partidos sigma . Como puede ver, no estamos buscando una coincidencia exacta, sino algo que "parezca" el patrón especificado.π=3 1 5 5 4 4 2 8 6 6 7 7σ=2 1 33 1 4 4σ

¿Alguien sabe si se ha realizado un trabajo para extender los problemas de coincidencia de patrones de permutación a las cadenas? Desafortunadamente, Google no ayudó, ya que el conocido problema de coincidencia de patrones en las cadenas no tiene nada que ver con esto.

Anthony Labarre
fuente
Actualmente estoy investigando en patrones de permutación afines. Hay algo de trabajo por ahí, pero la mayoría solo está disponible para aquellos en la academia.
abigail3306

Respuestas:

5

Finalmente logré desenterrar una buena encuesta de Kitaev y Mansour , que da consejos sobre la literatura relacionada con la coincidencia de patrones de permutación en permutaciones y palabras "usuales" / firmadas / coloreadas.

Anthony Labarre
fuente
3

Baars, Löh y Swierstra implementaron Permutation Parsers para Haskell (Journal of Functional Programming / Volume 14 / Issue 06, pp 635 - 646). Se pueden usar para especificar la permutación de una colección de analizadores. Si cada uno de estos analizadores es un analizador opcional para un solo personaje (es decir, coincide con el personaje o nada), entonces tendría los ingredientes que está buscando. Creo que su biblioteca está disponible con GHC.

Dave Clarke
fuente
0

Deberías comenzar con Revital Eres, Gad M. Landau, Laxmi Parida: Descubrimiento de patrones de permutación en biosecuencias . Journal of Computational Biology 11 (6): 1050-1060 (2004).

Gianluca Della Vedova
fuente
Esto no parece ser lo mismo: están interesados ​​en localizar grupos de caracteres que ocurren juntos, sin tener en cuenta el orden . El mismo problema en las permutaciones se denomina "identificación de intervalos comunes".
Anthony Labarre
@Labarre Estoy de acuerdo con tu comentario. ¿Debo eliminar mi respuesta?
Gianluca Della Vedova
1
Por favor no borres. Su respuesta y el comentario de Labarre me ayudaron a comprender mejor la pregunta.
Aaron Sterling
@ Aaron Sterling Entonces deberíamos editar la pregunta, ¿no?
Gianluca Della Vedova
2
Creo que la pregunta es relativamente clara en su forma actual.
Suresh Venkat