有效的词置乱算法

我正在寻找一种有效的算法,将一组字母排列成包含最大字数的排列。

例如,假设我得到了字母列表:e,e,h,r,s,t。我需要以包含最大字数的方式对它们进行排序。如果我把这些字母排列成“theres”,它将包含“the”、“there”、“her”、“here”和“ere”等词。所以这个例子可以有5分,因为它包含5个单词。我想按顺序排列字母,使其得分最高(包含最多的单词)。

一个幼稚的算法是尝试对每一个排列进行评分。我相信这是O(N!)因此,仅对上面的6个字母尝试720种不同排列(包括一些重复的字母,因为示例中有e两次)。当然,对于更多的信件,这种天真的解决办法很快就不可能了。

该算法不需要实际产生最佳解,但它应该在合理的时间内找到一个好的解。对于我的应用程序,只需猜测( Monte Carlo )在几百万排列工作相当糟糕,所以这是目前的标志。

我目前正在使用 Aho-Corasick 排列得分算法。它只在一次通过文本的过程中搜索字典中的每个单词,所以我相信它是相当有效的。这也意味着我将所有单词存储在 trie 但是如果另一个算法需要不同的存储,那也没问题。我不担心建立字典,只是实际排序和搜索的运行时间。如果需要,甚至可以使用模糊字典,比如 Bloom Filter .

对于我的申请,给出的字母表大约是100个,字典包含超过100000个条目。字典永远不会改变,但需要订购几个不同的字母表。

我正在考虑尝试 path finding algorithm . 我相信我可以从列表中的一封随机信开始。然后,剩下的每个字母将被用来创建一个“路径”。我认为这将与AHO Corasick评分算法很好地合作,因为分数可以一次建立一个字母。不过,我还没试过寻路,也许这不是一个好主意?我不知道哪种寻径算法最好。

我想到的另一个算法也是从一个随机字母开始的。然后字典trie将被搜索到包含剩余字母的“丰富”分支。将删除包含不可用字母的词典分支。我对这个方法的具体工作有点迷茫,但它可以完全消除评分排列。