字谜生成算法
本指南将帮助您了解使用Julia编程语言从给定的单词或短语中搜索和组成字谜短语的算法是如何工作的。
导言
字谜生成算法是一种重新排列原始单词（或短语）的字母以获得新的有意义的单词或短语的方法。 它广泛应用于语言学，密码学，正念游戏和娱乐任务。
例如，单词Listen可以转换为Silent，因为这两种组合使用相同的字母，但顺序不同。 我们的应用程序将从一个文件中搜索一组英文单词中的这样的字谜。 unixdict.txt.
程序的主要部分
阅读字典
读取单词列表文件（unixdict。txt）并将所有内容转换为小写。 然后我们使用正则表达式将字符串分成单词。 \s+ 对于空格，要删除不必要的字符并将其转换为内部集合-数组。
In [ ]:
const unixwords = split(read("unixdict.txt", String) |> lowercase, r"\s+")
Out[0]:
功能 findphrases
功能 findphrases 接受字符串(anastring）-什么需要anagrammed—以及字典数组 choices. 您还可以指定最小字长（sizelong，默认为4个字符）以及结果中可以添加多少个短词（n_shortpermitted，默认为零）。 返回的结果是匹配的短语列表。
In [ ]:
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
Out[0]:
使用测试数据调用函数
In [ ]:
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代码]的材料开发的（https://rosettacode.org/wiki/Anagram_generator ）