?

Log in

No account? Create an account

Entries by category: it

Здесь (далее) находится список (пополняемый) полезных программ и файлов данных,
написанных и созданных автором в помощь любителям комбинаторной поэзии,
точнее, словесной комбинаторики.

Анимация анаграмм: https://marinol.livejournal.com/1027746.html
Порядкограммы: https://marinol.livejournal.com/1026724.html

Статья "Конструирование анаграмм": http://www.olegmarin.ru/teranag.pdf

Новая книга анаграмм.

Онлайн база данных анаграмм.
Онлайн база данных равнобуквиц (пантограмм).
Онлайн база данных палиндромов.
Онлайн база данных разнобуквиц.
Онлайн база данных слоговых палиндромов.
Онлайн база данных слоговых анаграмм.
Слоговые анаграммы (простые). (сгенерировано программой)
Слоговые палиндромы в одно слово. (сгенерировано программой)
Слоговые палиндромные челюсти в два слова. (сгенерировано программой)
Слоговые палиндромные челюсти в два слова. (сгенерировано программой)
Слова анаграммы (сгенерировано программой по словарю Зализняка)

Списки слов для начально-концевых тавтограмм: http://www.olegmarin.ru/tavtend/

О длине анаграмм.
http://marinol.livejournal.com/861155.html

Палиндрогены
http://marinol.livejournal.com/791756.html

Новая папка для комбинаторных файлов:
http://marinol.livejournal.com/492012.html

Выложил базу данных палиндромистов и палиндромов.
http://marinol.livejournal.com/276744.html

Новая (диалоговая) версия комбинаторных программ:
http://marinol.livejournal.com/165386.html

Компьютерная палиндромная антология:
http://marinol.livejournal.com/197021.html

Список палиндромистов:
http://marinol.livejournal.com/225541.html

Метод генерации палиндромов с помощью решения задачи ЦЛП:
http://marinol.livejournal.com/196763.html

Способ создания рифмованных анаграмм
http://marinol.livejournal.com/305170.html

Read more...Collapse )
Ранее я уже показывал, как задача поиска разнобуквиц сводится
к задаче ЦЛП - целочисленного линейного программирования.

http://marinol.livejournal.com/165386.html


Чем это хорошо? Тем, что для решения таких задач существуют
эффективные алгоритмы, реализованные в виде работающих, отлаженных
пакетов программ.
Те, кто считает, что это представляет чисто теоретический интерес,
могут познакомиться с программой "Комбинаторный Поэт".
В этой программе такой подход реализован практически и позволяет быстро
находить разнобуквицы необходимого качества.

Здесь же мы попробуем применить аналогичный подход к задаче
создания палиндромов. Можно ли свести проблему создания палиндромов
к линейной задаче, для которой, как я уже сказал, имеются эффективные
алгоритмы и отлаженные программы? Ответ на этот вопрос положительный.

В этой заметке я приведу логику создания линейной модели для генерации
палиндромов. Вопросы её практического использования использования будут
освещены в другой (следующей) заметке. И, возможно, подход будет реализован
в одной из следующих версий программы Комбинаторный Поэт.

Глупо утверждать, что этот подход заменит умение и искусство опытных
палиндромистов. Но, наверное, он сможет быть для них каким-то существенным
подспорьем.

Итак, пусть мы имеем словарь слов S[i],i=1:N, N-количество слов в словаре.
И хотим создать палиндром длиной в M букв. В текущем варианте модели я буду
фиксировать длину палиндрома. Идея заключается в том, что мы вводим
целочисленную переменную X[i,j], которая означает, что слово с индексом i,
начинается в палиндроме с (буквенной) позиции j, если эта переменная имеет значение 1.
И 0, если слово S[i] не входит в палиндром с позиции j.

Ясно, что если не вводить никаких ограничений на вхождение слова в палиндром,
то будет хаос - разные слова смогут начинаться (и продолжаться) с одной и той же
позиции. Для того, чтобы прекратить это безобразие мы вводим матрицу структурных
ограничений R[j,k], где j=1,M - индекс строки матрицы, k=1:M*N. Каждой строке
матрицы соответствует позиция палиндрома, поэтому их M. Каждому столбцу матрицы k
соответствует некая переменная X[i,j], поэтому количество столбцов
будет равно ~ N (кол-во слов)*M(кол-во позиций).
Столбец матрицы R формируется следующим образом. Начиная со строки индексом j
в столбце B будет поставлено столько единиц (1), какова длина слова. Во всех остальных
позициях нужно проставить 0. Если мы возьмём и умножим матрицу R на вектор X
то получим вектор B, размером M строк (длина палиндрома). Что он будет означать?
Он будет давать количество слов, чьи буквы находятся на каждой позиции палиндрома.
НО... в палиндроме (да и в любом другом ПРЕДЛОЖЕНИИ) на каждой позиции находится
буква от ОДНОГО слова. Поэтому, если мы имеем вектор B состоящим только из единиц (1),
то задав условие (линейное, это важно) R*X=B, мы гарантируем, что переменные будут
выбираться так, чтобы слова не пересекались, а образовывали одну линейную
последовательность.

Фу, уже легче. Но это не всё. Ведь нам нужен палиндром.
Чем характеризуется палиндром, тем, что на позиции L, L=1:M, находится
та же буква, что и на позиции M-L+1. Например, если L=1 (начало слова), то
такая же буква должна быть на позиции M-1+1 = M, то есть в конце слова.
И так далее со смещением к центру палиндрома.

Для того, что бы это формализовать, вводим матрицу W[j,k], j=1:M, k=1:M*N,
которая полностью аналогична матрице R, но... в ячейках матрицы находятся
не нули или единицы, а числа представляющие собой числовые КОДЫ соответствующих
букв каждого слова. Тогда если мы возьмём произведение матрицы W на вектор
переменную X, то получим вектор P, который ... в чистом виде даёт нам
последовательность слов (точнее букв), включённых в 'палиндром'. Для того,
что я смог убрать кавычки у слова палиндром в предыдущем предложении, мне
нужно лишь правильно задать 'палиндромные' ограничения. Как их задать ?
Очень просто:

P[L]=P[M-L+1], где L=1,M.

Как мы видим все ограничения, которые мы вводили
линейны, то есть для решения задачи вполне можно пользоваться пакетами
решения задач целочисленного линейного программирования.
В качестве критерия (а также дополнительных ограничений) можно задавать
различные выражения, (как в задаче о разнобуквицах). Например можно задать
ограничения, чтобы любое слово не входило более двух раз в палиндром.
Или чтобы в палиндроме было от 4 до 6 существительных. Или, чтобы в палиндроме
обязательно были заданные слова (неважно на каких позициях, или наоборот
в определённых).

Вопросы практического применения, то есть того, насколько полезна такая
формализация, будем обсуждать в следующей статье.

Аналогичный подход может быть применён для генерации пантограмм.

Latest Month

October 2019
S M T W T F S
  12345
6789101112
13141516171819
20212223242526
2728293031  

Syndicate

RSS Atom
Powered by LiveJournal.com
Designed by Lilia Ahner