Грубо говоря, сопоставление шаблонов перестановок имеет дело с проблемами следующего вида:
При заданных перестановках в S n и в с содержит ли подпоследовательность длины , элементы которой упорядочены по σ ? m
Например, если и σ = ⟨ 2 1 3 ⟩ , то подпоследовательность 3 1 4 матча сг . Как вы можете видеть, мы ищем не точное совпадение, а нечто, «похожее» на указанный шаблон.
Кто-нибудь знает, проводилась ли работа по распространению проблем сопоставления шаблонов перестановок на строки? К сожалению, Google не помог, так как хорошо известная проблема сопоставления с образцом в строках не имеет к этому никакого отношения.
permutations
string-matching
Энтони Лабарре
источник
источник
Ответы:
Мне наконец удалось найти хороший обзор Китаева и Мансура , который дает ссылки на литературу, связанную с сопоставлением шаблонов перестановок для «обычных» / подписанных / цветных перестановок и слов.
источник
Baars, Löh и Swierstra внедрили анализаторы перестановок для Haskell (Журнал функционального программирования / Том 14 / Выпуск 06, с. 635 - 646). Их можно использовать для указания перестановки коллекции синтаксических анализаторов. Если каждый из этих синтаксических анализаторов является необязательным синтаксическим анализатором для одного символа (т. Е. Соответствует ему или ничего), то у вас будут нужные компоненты. Я считаю, что их библиотека доступна с GHC.
источник
Вы должны начать с Revital Eres, Gad M. Landau, Laxmi Parida: Обнаружение модели перестановки в биопоследовательностях . Журнал вычислительной биологии 11 (6): 1050-1060 (2004).
источник