TL;DR:
Съев мяч, щипцы, эльф‑конюх ждёт груз шайб. (33 буквы)
Прошлым летом подарили сыну магнитную азбуку. Ну, знаете, такие буквы на магнитах, можно составлять слова на холодильнике:
Ну само собой получилось, что мне захотелось составить что‑то из всех букв. Оказалось, что классика вроде «Съешь ещё этих мягких французских булок» не подходит — в моём наборе каждая буква была только один раз. А те панграммы, где буквы не повторяются (можно найти, например, у Лебедева в «Ководстве») — «Эй, жлоб! Где туз? Прячь юных съёмщиц в шкаф.» или «— Любя, съешь щипцы, — вздохнёт мэр, — кайф жгуч» — они, скажем так, на любителя. Слишком много восклицаний, междометий и прямой речи. Хотелось чего-то более пристойное и связное.
И я тут вспомнил видео Мэтта Паркера про оптимизацию его кода. Действительно, можно попробовать найти панграмму с помощью bitwise логики — тогда перебор комбинаций будет быстрым. Допустим, у нас есть слово «кайф». Буква «к» — это 11-й бит, «а» — 0-й, «й» — 10-й, «ф» — 21-й. В числе биты этих разрядов будут выставлены в единицу. Слово «жгуч» — своё число, и так для каждого слова из словаря.
Дальше — нам нужно найти такой набор слов, где каждая буква встречается ровно один раз. Это значит, что нам нужны две вещи:
Никаких пересечений. Если у двух слов есть общая буква, их битовые маски имеют общий бит. Побитовое И двух масок даст ноль, если общих битов нет. Если результат не ноль — значит, есть повторение, такое слово не подходит.
Все буквы покрыты. В русском алфавите 33 буквы. Значит, нам нужна маска из 33 единиц подряд: 111111111111111111111111111111111. Если мы набрали несколько слов, их маски можно сложить. И если результат равен этой константе из 33 единиц — значит, мы собрали все буквы, и это панграмма.
Остается сделать алгоритм на С, чтобы каждое сравнение масок выполнялось за один такт процессора, тогда брутфорс комбинаций будет выполняться относительно быстро.
Какой же поиск слов без словаря. За основу я взял репозиторий danakt/russian‑words. Там около 1.5 миллиона слов. Но нам не нужны все. Во‑первых, нам нужны только слова без повторяющихся букв, потому что если в слове есть две одинаковые буквы, оно автоматически бесполезно для нашей задачи — в панграмме каждая буква участвует ровно один раз. Во‑вторых, надо убедиться, что слово состоит только из русских букв (никаких цифр, английских букв, знаков и прочего). В итоге после фильтрации осталось 233 539 слов.
Кстати. Если вам интересно, какое слово в русском языке самое длинное и все буквы в нем разные, их три (17 букв):
подчёркивающемуся
четырёхполюсникам
четырёхугольникам
Дальше я попытался отфильтровать мусор, потому что в словаре полно всякой ерунды вроде «аб», «оф», «жну». С этими словами у меня получалось найти кучу панграмм, однако как составить из полученных слов что‑то осмысленное?
Поэтому я попробовал отсортировать слова. Пробовал разное:
Частотность через библиотеку wordfreq. У неё есть шкала Zipf — от 0 до 7, где 7 — это предлоги типа «в», а 0 — редкая ерунда. Я выставил пороги в зависимости от длины: для двухбуквенных — не ниже 3.5, для трёхбуквенных — 3.0, для четырёх и больше — хотя бы 2.0.
Морфология через pymorphy2 — если слово не определяется как известное, но частота высокая — оставляем. Это позволяло не выкинуть редкие, но осмысленные слова.
Отбрасывал слова без гласных, с кучей согласных подряд, начинающиеся на ъ или ь. Даже если такие слова действительно есть, я не хотел их видеть в панграмме.
Однобуквенные — оставил только предлоги и союзы: в, с, к, о, у, я, и, а.
В итоге после всех фильтров словарь сжался до ~96 тысяч слов. Неплохо, но поиск стал находить сильно мало комбинаций, а некоторые слова, которые находились в панграммах и показались мне вполне адекватными, оказались обрезаны. Лучше оставить все 234 тысячи, но отсортировать их так, чтобы в первую очередь перебирались более «полезные» слова. Полезность я определил как комбинацию длины и частоты употребления. Плюс я добавил бонус за редкие буквы (как в игре «Словодел») — чтобы слова с «ъ», «ё», «ф» оказывались выше.
Если вам интересно какая буква самая редкая, какая самая частая, в моем словаре буква «ъ» встречается всего 1279 раз, а самая частая буква «а» — 134 154 раза в словаре из 233 539 слов:
Обнаружив уже известных нам «съёмщиц» на 3 месте словаря, я посчитал что ранжирование вышло хорошо:
Однако на практике, мне показалось что лучше больше добавить веса длине слов. Когда выполняется поиск, хочется чтобы слова были не только осмысленные, но и длинные. Потому что найти комбинацию из коротких 3–2 буквенных слов легко, а вот составить из них осмысленное предложение — нет. Лучше найти длинные слова и добить фразу короткими. В результате словарь вышел таким:
Затем при поиске я могу обрезать список слов до нужной длинны. Хочешь быстрее, но меньше результатов или дольше, но больше результатов сомнительного качества?
Кроме возможности выбора размера словаря, я сделал еще опции:
Динамическая фильтрация — на первых 2–3 уровнях рекурсии строим временный список слов, которые не пересекаются с уже выбранными, и перебираем только его. Это отсекает заведомо неподходящие варианты и ускоряет немного поиск (процентов на 30%). На больших глубинах, когда у нас уже набрано, скажем, 2 слова, мы перестаём строить временные списки, потому что к этому моменту число подходящих слов и так резко сократилось, и оверхед на построение фильтра становится неоправданным.
Произвольное стартовое слово — можно задать любое слово или несколько (даже если его нет в словаре), и поиск начнётся с него. Очевидно, что некоторые слова с редкими буквами типа «ъ» или «ё» гораздо более удобны для поиска. Также гораздо более ценны глаголы, так как поиск обычно выдает комбинации с кучей существительных.
В итоге процесс поиска вышел таким: на маленьком словаре ищем подходящую комбинацию слов — особенно выискиваем сочетания слов с глаголами в правильных формах — готовые фразы. С этими фразами ищем по большому словарю. Так удалось найти комбинацию:
Съев мяч, щипцы, эльф‑конюх ждёт груз шайб. (33 буквы)
Найдя эту комбинацию, мне захотелось ее опубликовать. Но где? Это оказалось гораздо сложнее, чем написать программу для поиска панграмм и найти искомую. Я попробовал писать разным блогерам от мира слов, написал Лебедеву на мыло, но ответа так ни от кого и не получил. А недавно перенося проекты с гитфлика на гитлаб, наткнулся на этот проект и подумал, что можно хотя бы опубликовать на Хабре. Может быть тут посоветуют куда написать?
Проект я выложил в открытый доступ, вдруг кто тоже захочет поискать: https://gitflic.ru/project/crantisz/pangram - там код на С и словарь, который я использовал.