我正在寻找一种有效的算法，用于将一组字母扰乱为包含最大单词数的排列。

例如，假设给我字母列表：{e，e，h，r，s，t}。我需要以包含最大单词数的方式对它们进行排序。如果我将这些字母排序为“ theres”，则其中包含“
the”，“ there”，“ her”，“ here”和“
ere”。因此该示例的得分为5，因为它包含5个单词。我想对字母进行排序，使其得分最高（包含最多单词）。

天真的算法是尝试对每个排列进行评分。我相信这是O（n！），因此仅对上述6个字母尝试720种不同的排列（包括一些重复项，因为该示例具有两次e）。当然，对于更多字母，天真的解决方案很快变得不可能。

该算法不必实际产生最佳解决方案，但应在合理的时间内找到一个好的解决方案。对于我的应用程序，简单地猜测（蒙特卡洛）数百万个排列的效果就很差，因此，这是目前的最高表现。

我目前正在使用Aho-Corasick算法对排列进行评分。它只需要搜索文本中的一个单词就可以搜索字典中的每个单词，因此我认为它非常有效。这也意味着我把所有单词都存储在一个trie中，但是如果另一种算法需要不同的存储，那也很好。我并不担心要设置字典，而只是担心实际排序和搜索的运行时间。如果需要，甚至可以使用模糊字典，例如Bloom
Filter。

对于我的应用程序，给定的字母列表大约为100，并且词典包含超过100,000个条目。字典永远不会改变，但是需要订购几个不同的字母列表。

我正在考虑尝试一种路径查找算法。我相信我可以从列表中的随机字母开始作为起点。然后，每个剩余的字母将用于创建“路径”。我认为这可以与Aho-
Corasick评分算法配合使用，因为可以一次累积一个字母的分数。我还没有尝试过寻路；也许这不是一个好主意？我不知道哪种路径查找算法可能是最好的。

我想到的另一个算法也以随机字母开头。然后将在字典trie中搜索包含剩余字母的“丰富”分支。包含不可用字母的字典分支将被删除。我对如何正确工作的细节有些迷惑，但可以完全消除得分排列。