从哪里开始：哪一组由N个字母组成的单词能组成最多的单词？

Question

我在解决这个问题时遇到了一些困难，我一直想知道：给定一个字典，哪个由N个字母组成的字母集可以用来组成最多的单词？字母可以重复使用。

例如，对于N=3，我们可以选择EST，从而得到像TEST和SEE之类的单词...

我在网上搜索时发现了一些答案（如上面列出的EST），但没有解释方法。

我的问题是：有哪些类似于这个问题的著名问题，或者我应该使用哪些原则来解决这个问题？

注意：我知道EST是N=3时的最佳选择，并不意味着ESTx是N=4时的最佳选择。也就是说，你不能只是在前一个解决方案后附加一个字母。

如果你想知道，这个问题是因为我想知道哪个由4个成分组成的组合可以制作最多的鸡尾酒而引起的，然后我开始寻找答案。然后我意识到我的问题是具体的，所以我想这个字母问题是同样类型的问题，于是也开始搜索它。

- swagrov

---

解决你的鸡尾酒问题要简单得多，例如，重复（在“sEE”中的“EE”...）不存在，宇宙非常小（我猜不到几千个），而输入是具体的（一组成分），而不是根据其大小找到该集合的目标。这并不是说这个问题无效。 - Amit

我不确定从哪里开始，但我怀疑应该从字典开始，而不是从一组字母开始。找到正确的字典表示，这个问题可能对于每个N来说都变得微不足道。 - Ted Hopp

对于一般情况，有N个单词，每个单词可以使用M个可用字母的任何子集，这是不幸的NP难问题。请参见我的证明：http://cs.stackexchange.com/questions/64334/n-songs-m-instruments-how-to-pick-k-instruments-to-cover-maximal-amount-of-son/64348#64348（“乐器”=字母，“歌曲”=单词）。 （请注意，忘记单词中字母的顺序和重复不会损失任何东西。） - j_random_hacker

@mrmcgreg：为了使一个单词被某些可用字母“启用”，我们关心的唯一信息是它使用的无序字母集。 （因此，例如，任何算法的第一步都应该将单词规范化为这个无序使用字母的集合。） - j_random_hacker

@j_random_hacker 感谢您的解释。 - mrmcgreg

Answer 1

对于字典中的每个单词，按字母顺序排序并去重。将其作为单词的“骨架”。对于每个骨架，计算包含它的单词数量。这就是它的“频率”。忽略所有大小大于N的骨架。

让一个“子骨架”成为从骨架中删除1个或多个字母的任何可能性，即EST具有E、S、T、ES、ET、ST的子骨架。对于大小为N的每个骨架，添加此骨架及其所有子骨架的计数。选择总和最大的骨架。

您需要O(2 ** N * D)次操作，其中D是字典的大小。

更正：我们需要考虑到大小高达N（不仅仅是单词的）所有骨架，并且操作的数量将为O(2 ** N * C(L, N))，其中L是字母的数量（在英语中可能为26）。

- user31264

---

选择具有最大总和的骨架--如果您仅考虑单词的骨架，则可能会错过最佳解决方案。例如：单词为AB，BC，CD，n = 3。最佳解决方案是ABC，但您的算法将无法找到它。 - j_random_hacker

看起来更好了。但是如果我理解正确，O(2**N*C(L,N))实际上是您将考虑的“骨架”数量--在这种情况下，以相同的时间复杂度解决问题意味着每个骨架的时间复杂度为O(1)。我认为可以通过按格雷码顺序枚举任何给定起始骨架的2^N个子骨架来实现这一点，但您应该明确说明这一点。 - j_random_hacker

您IP地址为143.198.54.68，由于运营成本限制，当前对于免费用户的使用频率限制为每个IP每72小时10次对话，如需解除限制，请点击左下角设置图标按钮（手机用户先点击左上角菜单按钮）。 - user31264

你的整体解决方案很明显；使用格雷码来加速是其中最不明显的部分。 - j_random_hacker

Answer 2

所以我编写了一个使用哈希表解决此问题的解决方案。在此过程中，我还必须处理一些问题！

1. 令 N 为你要寻找的能组成最多单词的字母组大小。令 L 为字典的长度。
2. 将字典中的每个单词转换为一个字母集合：'test' -> {'e','s','t'}
3. 对于每个从1到N的数字，创建一个包含你可以用恰好那么多字母制作的单词的切割列表。
4. 为每个从1到N的数字创建一个哈希表，然后遍历相应的切割列表，并使用该集合作为键，对切割列表的每个成员进行加1操作。
5. 这是让我困扰的部分！为N创建一个切割列表的集合（unique_cut_list）。这本质上是N的哈希表中所有填充的键值对。
6. 对于unique_cut_list中的每个集合，生成所有子集，并检查相应的哈希表（子集的大小）是否有值。如果有，将该值添加到原始集合的键为N的哈希表中。
7. 最后，遍历哈希表并找到最大值。相应的键就是你要寻找的字母组。

在步骤1-5中，您将穿过字典1+2N次，步骤6将穿过字典的版本并每次检查(2^N)-1个子集（忽略空集）。这将得到O(2NL + L*2^N)，其应接近于O(L*2^N)。这不错，因为在大多数应用程序中，N不会太大！

- swagrov

---

看起来你只考虑那些是某个单词的子集的字母组合。所以例如，如果单词是AB、BC，而n=3，那你会错过最优的组合ABC。（尽管如果例如ABCD或ABC本身也是单词，你就能得到它。） - j_random_hacker

如果您通过生成所有（A选N）大小为N的集合（对于A字母表），并且如果N约为A/2，则结果时间复杂度将近两倍指数。有一种单指数解决方案，涉及从最小的集合开始，生成每个包含恰好一个更多字母的超集，然后将当前集合的权重添加到对应该超集的值中的哈希表中（必要时为超集创建新键）。 - j_random_hacker