marinol (marinol) wrote,
marinol
marinol

Category:

АНАГРИФЫ

Анагриф – это текст, составленный из набора букв, входящих в заданное слово. Вместо слова можно задать и просто произвольный набор букв (каждой по одной). Можно рассмотреть полный анагриф – множество ВСЕХ слов, составленных из данного набора букв. Количество элементов (слов) этого множества – это его мощность. Интересной задачей, по моему мнению, будет определение набора из N разных букв, который даёт полный анагриф максимальной мощности, то есть, дающий максимальное количество слов. Полный анагриф слова ‘мост’ содержит 25 слов. Полный анагриф слова 'свет' – 26 слов, слова 'дом' – 6 слов. А вот, интересно, какой набор из 4-х букв даст максимальное количество слов, которые состоят только из этих букв?

Для решения это задачи предлагается следующая модель целочисленного линейного программирования.
Имеется словарь, состоящий из слов S[i], i=1…N, где N – количество слов в словаре.
Для каждого слова введём бинарную переменную X[i], которая равна 1, если слово входит во множество F (полный анагриф) и 0, если не входит. Для каждого слова S[i] имеется вектор букв, которые входят в это слово: A[j,i] = 1, если буква с номером j входит в слово S[i], и 0 – в противном случае. Эти вектора составляют матрицу A. Если мы умножим матрицу A на вектор X, то получим вектор В, размером в 33 числа (по числу букв алфавита), который показывает - сколько в словах множества F содержится вхождений каждой буквы. Зададим на него условие, что
B <= R*M, где M – число (слов в словаре), а R – бинарный вектор. R[i] = 0 или 1. И добавим условие на него – сумма его компонент равна L (3,4,5,6...). Что это означает? Если R[i] = 0, то соответствующая ему буква (i – её порядковый номер) не будет входить в слова множества F – согласно неравенству. А если равна 1, то буква как может входить, так может и не входить в слова множества F. Тогда сумма компонент вектора R – это точное число (разных) букв, которые содержатся в словах множества F.
Теперь добавим критерий – будет максимизировать число слов во множестве F. Для этого просто возьмём сумму компонент вектора X и устремим её к максимуму.

Что получается. Мы имеем задачу линейного целочисленного программирования, которая хорошо исследована и имеет отличные пакеты оптимизации для решения (CPLEX, GUROBU, на худой конец - LPSOLVE). Аналогичный подход я применял для нахождения разнобуквиц и он отлично работает (с бесплатным LPSOLVE). В ближайшее время я постараюсь провести численные расчёты и ответить на вопросы –
Какие наборы и 3,4,5,6,7… букв дают возможность составить максимальное количество слов, то есть получить анагриф максимальной мощности. Их (эти анагрифы) наверное можно использовать для составления неплохих рассказов. Так же как буква 'П', на которую начинается максимальное количество слов, часто используется в тавтограммах.
Tags: анагрифы
Subscribe

  • ***

    Освоил новую профессию - 'смазыватель вентиляторов ноутбуков Xiaomi' )) Как здорово, что на youtube полно роликов по ремонту чего-угодно! Пока…

  • ***

    Специальный выпуск журнала «Гвидеон», посвященный 30-летию Международной Академии Зауми. С моими анаграммами. http://gulliverus.ru/mariin-20.html

  • ***

    Особенности индексации Яндекса. Проверил, как Яндекс индексирует страницы сайта stihi.ru через форму на самом сайте. Например по слову…

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 0 comments