我正在寻找一种有效的算法,用于将一组字母加扰成包含最大字数的排列.
例如,假设给出了字母列表:{e,e,h,r,s,t}.我需要以包含最大字数的方式对它们进行排序.如果我将这些字母命名为"theres",它包含"the","there","her","here"和"ere"等字样.因此,该示例的得分为5,因为它包含5个单词.我想以这样的方式订购这些字母以获得最高分(包含最多的单词).
一个天真的算法是尝试对每个排列进行评分.我相信这是O(n!),因此仅针对上面的6个字母尝试720种不同的排列(包括一些重复,因为该示例有两次).当然,对于更多的字母,天真的解决方案很快就变得不可能了.
该算法不必实际产生最佳解决方案,但它应该在合理的时间内找到一个好的解决方案.对于我的应用程序,简单地猜测(蒙特卡罗)几百万的排列效果非常差,所以这是目前的标志.
我目前正在使用Aho-Corasick算法对排列进行评分.它只通过文本一次搜索字典中的每个单词,所以我相信它非常有效.这也意味着我将所有单词存储在一个trie中,但如果另一个算法需要不同的存储空间也很好.我并不担心设置字典,只是实际订购和搜索的运行时间.如果需要,甚至可以使用模糊字典,例如布隆过滤器.
对于我的应用程序,给出的字母列表大约为100,字典包含超过100,000个条目.字典永远不会改变,但需要订购几个不同的字母列表.
我正在考虑尝试寻路算法.我相信我可以从列表中的随机字母开始作为起点.然后,每个剩余的字母将用于创建"路径".我认为这适用于Aho-Corasick评分算法,因为分数可以一次建立一个字母.我还没有尝试寻路; 也许这不是一个好主意？我不知道哪种路径寻找算法可能是最好的.
我想到的另一种算法也是以随机字母开头的.然后将搜索字典trie以查找包含剩余字母的"丰富"分支.包含不可用字母的字典分支将被修剪.关于这将如何正常工作的细节我有点模糊,但它可以完全消除评分排列.