О палиндромах и их генерации
Оригинал взят у marinol в О палиндромах и их генерации
Неформально палиндром определяют как 'текст, который одинаково читается в обоих направлениях’ : слева - направо и справа налево.
Это определение вроде бы утверждает равенство-тождественность обоих направлений в палиндроме. Но это не совсем так. Возьмем один из самых известных палиндромов “А роза упала на лапу Азора”. Из него видно, что под ‘одинаковым прочтением’ имеется, только одинаковый порядок букв, не более того. Разбиение на слова, определенное в прямом порядке, при обратном прочтении меняется. Точнее берётся таким, каким оно было при прямом прочтении. Хотя конечно бывает, что они совпадают.
Пусть Rev() это функция реверсирования текста, то есть перечисление букв текста в обратном порядке. А Rs() - это функция удаления пробелов (делящих текст на слова). Считаем, что знаки препинания в тексте палиндрома отсутствуют. Тогда формальное определение палиндрома можно записать как :
Т - палиндром, если Rev(Rs(T)) == Rs(T). В принципе ничего нового, только для определённости. Вместо функции удаления пробелов можно было бы использовать функцию конкатенации слов, на которые разбивается текст. В дальнейшем для описания алгоритмов может еще потребоваться функция Len(T) - длина текста T.
Разберемся в существующей классификации линейных (нециклических) палиндромов. При этом не рассматриваются отдельно 'оборотни', как особенная форма палиндрома, так как они прямо приводятся к обычной форме палиндрома. Мы рассматриваем только монопалиндромы, которые представляют собой один палиндром, в отличие от полипалиндромов, которые являются упорядоченным множеством монопалиндромов.
Используемая ниже система обозначения палиндромов необщепринятая, к тому же, скорее всего, неокончательная. Просто она для меня пока удобнее всего.
Простейший палиндром это слово, которое одинаково читается в обоих направлениях. В данном случае 'одинаково читается' это не фигура речи, а точное определение - нет пробелов, слово одно. По терминологии известного палиндромиста willich, это 'монада'. У автора докторской диссертации по палиндромам Бубнова Александра, это палиндром с признаком 'двоичности' равным 1 - п1. Я буду использовать похожее обозначение - w1 (w - word).
Следующими по сложности будут палиндромы из двух слов (‘дидромы’ в терминологии willich). Дидромы, или палиндромы типа W2. Это более сложные образования и из них можно выделять подтипы.
Пусть дидром состоит из слов A и B. Тогда если Len(A) = Len(B), то это палиндром типа
w1|w1 или ‘челюсть’ (в терминологии willich). Здесь цифрой обозначается, как и раньше, количество слов в соответствующей части палиндрома. Главной особенностью таких палиндромов является то, что они могут легко вкладываться в палиндромы из большего количества слов путем вложения друг в друга. В обозначении палиндрома w1|w1 символ точки '|' обозначает условный центр палиндрома, он находится между словами. В центр челюсти можно вставлять не только другую челюсть, но и вообще любой палиндром, например монаду. При этом образуется более длинный палиндром.
Если Len(A) > Len(B), то это, по терминологии willich, ‘хвостик’ - если у первого слова на конце есть остаток (неслово), который ничему не соответствует во втором слове и который будет палиндромом - тип w1.p|w1 Если Len(A) < Len(B), то это ‘носик’ (willich) - аналогично хвостику, но палиндром в начале второго слова - w1|p.w1. Здесь p - палиндромный остаток. Он может находиться в начале и конце слова и является его частью.
Любые челюсти очевидным образом могут вкладываться друг в друга, образовывая палиндром. Возникает вопрос - могут ли вкладываться друг в друга ‘хвостики’ или 'носики', с тем чтобы образовать палиндром большей сложности? В промежуток между словами 'носика' (‘хвостика’) нельзя вставить палиндром, в котором имеется две или более различных букв. Можно вставить только палиндром с одной буквой, хотя и в нескольких экземплярах. Для образования более сложных палиндромов в смещенный центр 'хвостика' или 'носика' надо вставлять соответствующий непалиндром. Willich указывает на такую возможность - действительно можно вставить непалиндром, но сделанный в точности из палиндрома, с помощью операции перемены слов палиндрома местами.
Таким образом, возникает еще одно свойство палиндромов - разложимость. Палиндром (напомню, речь идет только о монопалиндромах) называется 'разложимым', если он состоит из двух или более палиндромов. Для монопалиндромов, как легко видеть, существует только один способ комбинирования - вложение одного палиндрома в другой, как в матрёшке.
При этом челюсти можно вкладывать друг в друга как есть, а носики или хвостики можно вкладывать друг в друга, если равны между собой их палиндромные остатки, и слова в палиндроме нужно поменять местами.
Поскольку для челюстей остаток пустой, а слова можно менять местами, то фактически способ комбинирования (willich) один - вложить друг в друга два палиндрома (челюсть, носик, хвостик), соответствующие друг другу и поменять слова местами.
Все палиндромы типа W2 будут либо челюстями (w1|w1), либо 'носиками', либо 'хвостиками'.
w1.p|w1 - это 'хвостик'
w1|p.w1 - это 'носик'
где p - пусто или палиндромный остаток, а Rev(w1) = Rs(w2)
Далее идут палиндромы из трёх слов. Множество ВСЕХ палиндромов из 3-х слов я буду обозначать как W3 (w - заглавное). Они могут быть
w1.p|w2
w1|p.w2,
w2.p|w1,
w2|p.w1,
либо это может быть просто ‘тридром’ (willich), то есть, палиндромом типа 'w3’ (w - строчное).
где p - пусто или палиндромный остаток, а Rev(w1) = Rs(w2)
Палиндромы из 4 слов (W4) могут быть палиндромами типов
w1.p|w3
w1|p.w3
w3.p|w1
w3|p.w1
w1.p(Inv(w1.p|w1))w1
w1(Inv(w1|p.w1))p-w1
w2.p|w2
w2|p.w2
где p - либо пусто, либо палиндромный остаток,
Inv - операция замены порядка слов на обратный.
либо палиндромом типа w4 (если он не принадлежит к множеству палиндромов, указанных выше).
Здесь w1.p(Inv(w1.p|w1))w1 это разложимый палиндром, представляющий матрёшку из двух палиндромов типа w1.p|w1.
Можно было бы продолжать дальше (по количеству слов), но с точки зрения определения понятий, необходимых для описания сути палиндромов (без внутренней структуры), этого вполне достаточно.
Рассмотрим алгоритмы перечисления палиндромов.
w1 - простой цикл по всем словам словаря с проверкой каждого слова на палиндромность.
w1.p|w1
w1|p.w1
Предварительно строится индекс всех слов словаря. Потом делается один проход по словарю с проверкой на присутствие в индексе (очень быстрая операция) реверсированного слова или непалиндромного начала или конца слова (включая слово целиком).
w1.p|w2
w1|p.w2
Проход по словарю. Непалидромная часть каждого слова (включая слово целиком) реверсируется и делается попытка сегментации слова - цикл по длине слова. Сегментация удачная, если оба сегмента являются словами, то есть находятся по индексу слов словаря.
В случае w1|p.w2 второе слово нужно искать не в словаре слов, в словаре непалиндромных начал слов.
w1.p|w3
w1|p.w3
Проход по словарю. Непалидромная часть каждого слова реверсируется и делается попытка сегментации слова - два вложенных цикла по длине слова. Сегментация удачная, если все три сегмента являются словами, то есть находятся по индексу слов словаря.
В случае w1|p.w3 третье слово нужно искать не в словаре слов, в словаре непалиндромных начал слов.
w2.p|w1
w2|p.w1
Здесь w2.p = S1 + S2, где второе слово может на конце может иметь концевую часть - палиндротекст (может и пустой).
Строится множество слов S1, которые будучи реверсированными, являлись бы началами каких-либо слов словаря. Строится множество слов S2, которые будучи реверсированными, являлись бы концами каких либо слов словаря.
Строятся все комбинации S1 с S2, с проверкой комбинаций на палиндромность.
w2 состоит только из
w1.p|w1
w1|p.w1
Алгоритм их поиска уже описан.
w2|w2
У нас есть палиндром из четырех слов: S1 S2 S3 S4.
Если Len(S1) == Len(S4), то мы имеем две челюсти w1|w1, вложенные друг в друга. Множество таких палиндромов можно сгенерировать взяв декартово произведение палиндромов типа w1|w1. Этого делать мы не будем, так как генерируем пока только неразложимые палиндромы.
Предположим что Len(S1) > Len(S4). Пусть S1 = S11 + S12 и Rev(11) = S4.
Если S12 палиндротекст, то есть Rev(S12) = S12, то S1 S4 - это палиндром типа w1.p|w1. Соответственно S3 S2 будет тоже палиндромом типа w1.p|w1.
То есть это два вложенных 'хвостика'. То есть это тоже разложимый палиндром.
Аналогично, пусть Len(S1) < Len(S4). Пусть S4 = S41 + S42 и Rev(41) = S1.
Если S41 палиндротекст, то есть Rev(S41) = S41, то S1 S4 - это палиндром типа w1|p.w1. Соответственно S3 S2 будет тоже палиндромом типа w1|p.w1.
То есть это два вложенных 'носика'. Тоже разложимый палиндром.
Следующий шаг - смысловая фильтрация полученных списков.
Текст был существенно исправлен после переписки-обсуждения с willich.
Неформально палиндром определяют как 'текст, который одинаково читается в обоих направлениях’ : слева - направо и справа налево.
Это определение вроде бы утверждает равенство-тождественность обоих направлений в палиндроме. Но это не совсем так. Возьмем один из самых известных палиндромов “А роза упала на лапу Азора”. Из него видно, что под ‘одинаковым прочтением’ имеется, только одинаковый порядок букв, не более того. Разбиение на слова, определенное в прямом порядке, при обратном прочтении меняется. Точнее берётся таким, каким оно было при прямом прочтении. Хотя конечно бывает, что они совпадают.
Пусть Rev() это функция реверсирования текста, то есть перечисление букв текста в обратном порядке. А Rs() - это функция удаления пробелов (делящих текст на слова). Считаем, что знаки препинания в тексте палиндрома отсутствуют. Тогда формальное определение палиндрома можно записать как :
Т - палиндром, если Rev(Rs(T)) == Rs(T). В принципе ничего нового, только для определённости. Вместо функции удаления пробелов можно было бы использовать функцию конкатенации слов, на которые разбивается текст. В дальнейшем для описания алгоритмов может еще потребоваться функция Len(T) - длина текста T.
Разберемся в существующей классификации линейных (нециклических) палиндромов. При этом не рассматриваются отдельно 'оборотни', как особенная форма палиндрома, так как они прямо приводятся к обычной форме палиндрома. Мы рассматриваем только монопалиндромы, которые представляют собой один палиндром, в отличие от полипалиндромов, которые являются упорядоченным множеством монопалиндромов.
Используемая ниже система обозначения палиндромов необщепринятая, к тому же, скорее всего, неокончательная. Просто она для меня пока удобнее всего.
Простейший палиндром это слово, которое одинаково читается в обоих направлениях. В данном случае 'одинаково читается' это не фигура речи, а точное определение - нет пробелов, слово одно. По терминологии известного палиндромиста willich, это 'монада'. У автора докторской диссертации по палиндромам Бубнова Александра, это палиндром с признаком 'двоичности' равным 1 - п1. Я буду использовать похожее обозначение - w1 (w - word).
Следующими по сложности будут палиндромы из двух слов (‘дидромы’ в терминологии willich). Дидромы, или палиндромы типа W2. Это более сложные образования и из них можно выделять подтипы.
Пусть дидром состоит из слов A и B. Тогда если Len(A) = Len(B), то это палиндром типа
w1|w1 или ‘челюсть’ (в терминологии willich). Здесь цифрой обозначается, как и раньше, количество слов в соответствующей части палиндрома. Главной особенностью таких палиндромов является то, что они могут легко вкладываться в палиндромы из большего количества слов путем вложения друг в друга. В обозначении палиндрома w1|w1 символ точки '|' обозначает условный центр палиндрома, он находится между словами. В центр челюсти можно вставлять не только другую челюсть, но и вообще любой палиндром, например монаду. При этом образуется более длинный палиндром.
Если Len(A) > Len(B), то это, по терминологии willich, ‘хвостик’ - если у первого слова на конце есть остаток (неслово), который ничему не соответствует во втором слове и который будет палиндромом - тип w1.p|w1 Если Len(A) < Len(B), то это ‘носик’ (willich) - аналогично хвостику, но палиндром в начале второго слова - w1|p.w1. Здесь p - палиндромный остаток. Он может находиться в начале и конце слова и является его частью.
Любые челюсти очевидным образом могут вкладываться друг в друга, образовывая палиндром. Возникает вопрос - могут ли вкладываться друг в друга ‘хвостики’ или 'носики', с тем чтобы образовать палиндром большей сложности? В промежуток между словами 'носика' (‘хвостика’) нельзя вставить палиндром, в котором имеется две или более различных букв. Можно вставить только палиндром с одной буквой, хотя и в нескольких экземплярах. Для образования более сложных палиндромов в смещенный центр 'хвостика' или 'носика' надо вставлять соответствующий непалиндром. Willich указывает на такую возможность - действительно можно вставить непалиндром, но сделанный в точности из палиндрома, с помощью операции перемены слов палиндрома местами.
Таким образом, возникает еще одно свойство палиндромов - разложимость. Палиндром (напомню, речь идет только о монопалиндромах) называется 'разложимым', если он состоит из двух или более палиндромов. Для монопалиндромов, как легко видеть, существует только один способ комбинирования - вложение одного палиндрома в другой, как в матрёшке.
При этом челюсти можно вкладывать друг в друга как есть, а носики или хвостики можно вкладывать друг в друга, если равны между собой их палиндромные остатки, и слова в палиндроме нужно поменять местами.
Поскольку для челюстей остаток пустой, а слова можно менять местами, то фактически способ комбинирования (willich) один - вложить друг в друга два палиндрома (челюсть, носик, хвостик), соответствующие друг другу и поменять слова местами.
Все палиндромы типа W2 будут либо челюстями (w1|w1), либо 'носиками', либо 'хвостиками'.
w1.p|w1 - это 'хвостик'
w1|p.w1 - это 'носик'
где p - пусто или палиндромный остаток, а Rev(w1) = Rs(w2)
Далее идут палиндромы из трёх слов. Множество ВСЕХ палиндромов из 3-х слов я буду обозначать как W3 (w - заглавное). Они могут быть
w1.p|w2
w1|p.w2,
w2.p|w1,
w2|p.w1,
либо это может быть просто ‘тридром’ (willich), то есть, палиндромом типа 'w3’ (w - строчное).
где p - пусто или палиндромный остаток, а Rev(w1) = Rs(w2)
Палиндромы из 4 слов (W4) могут быть палиндромами типов
w1.p|w3
w1|p.w3
w3.p|w1
w3|p.w1
w1.p(Inv(w1.p|w1))w1
w1(Inv(w1|p.w1))p-w1
w2.p|w2
w2|p.w2
где p - либо пусто, либо палиндромный остаток,
Inv - операция замены порядка слов на обратный.
либо палиндромом типа w4 (если он не принадлежит к множеству палиндромов, указанных выше).
Здесь w1.p(Inv(w1.p|w1))w1 это разложимый палиндром, представляющий матрёшку из двух палиндромов типа w1.p|w1.
Можно было бы продолжать дальше (по количеству слов), но с точки зрения определения понятий, необходимых для описания сути палиндромов (без внутренней структуры), этого вполне достаточно.
Рассмотрим алгоритмы перечисления палиндромов.
w1 - простой цикл по всем словам словаря с проверкой каждого слова на палиндромность.
w1.p|w1
w1|p.w1
Предварительно строится индекс всех слов словаря. Потом делается один проход по словарю с проверкой на присутствие в индексе (очень быстрая операция) реверсированного слова или непалиндромного начала или конца слова (включая слово целиком).
w1.p|w2
w1|p.w2
Проход по словарю. Непалидромная часть каждого слова (включая слово целиком) реверсируется и делается попытка сегментации слова - цикл по длине слова. Сегментация удачная, если оба сегмента являются словами, то есть находятся по индексу слов словаря.
В случае w1|p.w2 второе слово нужно искать не в словаре слов, в словаре непалиндромных начал слов.
w1.p|w3
w1|p.w3
Проход по словарю. Непалидромная часть каждого слова реверсируется и делается попытка сегментации слова - два вложенных цикла по длине слова. Сегментация удачная, если все три сегмента являются словами, то есть находятся по индексу слов словаря.
В случае w1|p.w3 третье слово нужно искать не в словаре слов, в словаре непалиндромных начал слов.
w2.p|w1
w2|p.w1
Здесь w2.p = S1 + S2, где второе слово может на конце может иметь концевую часть - палиндротекст (может и пустой).
Строится множество слов S1, которые будучи реверсированными, являлись бы началами каких-либо слов словаря. Строится множество слов S2, которые будучи реверсированными, являлись бы концами каких либо слов словаря.
Строятся все комбинации S1 с S2, с проверкой комбинаций на палиндромность.
w2 состоит только из
w1.p|w1
w1|p.w1
Алгоритм их поиска уже описан.
w2|w2
У нас есть палиндром из четырех слов: S1 S2 S3 S4.
Если Len(S1) == Len(S4), то мы имеем две челюсти w1|w1, вложенные друг в друга. Множество таких палиндромов можно сгенерировать взяв декартово произведение палиндромов типа w1|w1. Этого делать мы не будем, так как генерируем пока только неразложимые палиндромы.
Предположим что Len(S1) > Len(S4). Пусть S1 = S11 + S12 и Rev(11) = S4.
Если S12 палиндротекст, то есть Rev(S12) = S12, то S1 S4 - это палиндром типа w1.p|w1. Соответственно S3 S2 будет тоже палиндромом типа w1.p|w1.
То есть это два вложенных 'хвостика'. То есть это тоже разложимый палиндром.
Аналогично, пусть Len(S1) < Len(S4). Пусть S4 = S41 + S42 и Rev(41) = S1.
Если S41 палиндротекст, то есть Rev(S41) = S41, то S1 S4 - это палиндром типа w1|p.w1. Соответственно S3 S2 будет тоже палиндромом типа w1|p.w1.
То есть это два вложенных 'носика'. Тоже разложимый палиндром.
Следующий шаг - смысловая фильтрация полученных списков.
Текст был существенно исправлен после переписки-обсуждения с willich.