字谜生成算法
本指南将帮助您了解使用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
# 这一步没找到什么→返回什么
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 ）