Dopasowanie wzorca permutacji w ciągach

Luźno mówiąc, dopasowanie wzorców permutacji dotyczy następujących problemów:

Biorąc pod uwagę permutacje w S n i w , przy , czy zawiera podsekwencję o długości której elementy są uporządkowane według ?$\pi$$S_n$S m m ≤ n π τ m $\sigma$$S_m$$m\leq n$$\pi$ $\tau$$m$$\sigma$

Na przykład, jeśli i , to podsekwencja pasuje do . Jak widać, nie szukamy tutaj dokładnego dopasowania, ale raczej czegoś, co „wygląda” na określony wzór.σ = ⟨ 2 1 3 ⟩ 3 1 4 $\pi=\langle 3\ 1\ 5\ 4\ 2\ 8\ 6\ 7\rangle$$\sigma=\langle 2\ 1\ 3\rangle$$3\ 1\ 4$$\sigma$

Czy ktoś wie, czy przeprowadzono prace nad rozszerzeniem problemów dopasowywania wzorców permutacji do łańcuchów? Google niestety nie pomogło, ponieważ dobrze znany problem z dopasowywaniem wzorców w łańcuchach nie ma z tym nic wspólnego.

W końcu udało mi się wykopać fajną ankietę Kitaeva i Mansoura , która daje wskazówki do literatury związanej z dopasowaniem wzoru permutacji do „zwykłych” / podpisanych / kolorowych permutacji i słów.

Baars, Löh i Swierstra zaimplementowali Permutation Parsers for Haskell (Journal of Functional Programming / Volume 14 / Issue 06, str. 635 - 646). Można ich użyć do określenia permutacji zbioru parserów. Jeśli każdy z tych parserów jest parserem opcjonalnym dla pojedynczej postaci (to znaczy pasuje do znaku lub nie ma nic), to masz składniki, których szukasz. Uważam, że ich biblioteka jest dostępna z GHC.

Powinieneś zacząć od Revital Eres, Gad M. Landau, Laxmi Parida: Permutation Pattern Discovery in Biosequences . Journal of Computational Biology 11 (6): 1050-1060 (2004).