Генератор анаграмм
maximsidorovАлгоритм генерации анаграмм
Это руководство поможет понять, как работает алгоритм поиска и составления фраз-анаграмм из заданного слова или словосочетания с использованием языка программирования Julia.
Введение
Алгоритм генерации анаграмм — это способ перестановки букв исходного слова (или словосочетания) таким образом, чтобы получить новые осмысленные слова или фразы. Он широко используется в лингвистике, криптографии, играх «на внимательность» и задачах развлечательного характера.
Например, слово Listen может быть преобразовано в Silent, поскольку обе эти комбинации используют одни и те же буквы, но в другом порядке. Наше приложение будет искать такие анаграммы среди набора английских слов из файла unixdict.txt.
Основная часть программы
Чтение словаря
Считываем файл со списком слов (unixdict.txt) и переводим всё в нижний регистр. Затем разделяем строку на слова, используя регулярное выражение \s+ для пробелов, чтобы убрать лишние символы и превратить их во внутреннюю коллекцию - массив.
const unixwords = split(read("unixdict.txt", String) |> lowercase, r"\s+")
Функция findphrases
Функция findphrases принимает строку (anastring) — то, что нужно анаграммировать — а также словарный массив choices. Также можно указать минимальную длину слов (sizelong, по умолчанию 4 символа) и сколько коротких слов допустимо добавить к результату (n_shortpermitted, по умолчанию ноль). Возвращаемый результат — список подходящих фраз.
function findphrases(anastring::AbstractString, choices, sizelong = 4, n_shortpermitted = 1)
# Подсчет частот каждой буквы входной строки (только a-z)
anadict = Dict{Char, Int}()
for c in lowercase(anastring)
if 'a' <= c <= 'z'
anadict[c] = get(anadict, c, 0) + 1
end
end
# Здесь будем хранить найденные анаграммы
phrases = String[]
# Рекурсивно подставляем слова
function addword(remaining, phrase, numshort)
# Проходим через каждое слово в нашем словаре
for w in unixwords
len = length(w)
# Если нет возможности использовать ещё короткие слова и это слово слишком маленькое → пропускаем
numshort < 1 && len < sizelong && continue
# Проверяем, достаточно ли букв из оставшихся для использования слова W
any(c -> get(remaining, c, 0) < count(==(c), w), w) && @goto nextword
# Создаем новую версию оставшихся букв без тех, что уже использовали
cdict = copy(remaining)
for c in w
cdict[c] -= 1
end
# Все буквы совпадают? То есть остались только нули?
if all(==(0), values(cdict))
# Мы собрали полную анаграмму! Добавляем её в результат
return strip(phrase * " " * w)
elseif (newphrase = addword(cdict, phrase * " " * w, numshort - (len < sizelong))) != nothing
push!(phrases, newphrase)
end
@label nextword
end
# Не нашли ничего на этом шаге → возвращаем nothing
return nothing
end
# Запуск рекурсивного процесса сбора результатов
addword(anadict, "", n_shortpermitted)
# Возвращаем все собранные фразы
return phrases
end
Вызов функции с тестовыми данными
for s in ["Engee the best", "Simulink", "Exponenta"]
println("\nFrom '$s':")
# Удаление повторяющихся и вывод отсортированных результатов
foreach(println, findphrases(s, unixwords, 4, 0) |> unique |> sort!)
end
Заключение
Мы подробно рассмотрели реализацию алгоритма для поиска анаграмм в языке Julia. Используя файл unixdict.txt, мы смогли находить осмысленные фразы, являющиеся анаграммами определённых словосочетаний.
Подобная техника имеет применение в написании головоломок, анализа текстов и даже при проверке уникальности паролей. Главный плюс этого кода — чистота реализации и использование рекурсии для точного подбора сочетаний букв. Эффективность зависит от размера словаря и стратегии отбора новых слов, поэтому при необходимости его всегда можно улучшить за счёт выборочной фильтрации либо оптимизации обхода.
Пример разработан с использованием материалов Rosetta Code