选择覆盖单词最多的字母表？

Question

给定一个单词列表和一个最多包含P个字母的字母表，我们如何选择覆盖最多单词的最优字母表？

例如:给定带有P=1的单词"aaaaaa“"bb”"bb“，最佳字母表是"b”，因为"b“覆盖了两个单词。

另一个例子:给定带有P=4的单词"abmm“"abaa”"mnab“"bbcc”"mnnn“，最佳字母表是"abmn"，因为这涵盖了5个单词中的4个。

有没有已知的算法，或者有人能建议一个算法来解决这个问题？

Answer 1

这个问题是NP-难的，通过从团的简化(它是一种最密集的k-sub(超)图问题)。给定一个图，用不同的字母标记它的顶点，并为每条边组成一个两个字母的单词。存在k-团当且仅当我们可以覆盖k选择2个有k个字母的单词。

即使对于CLIQUE，算法的情况也是grim (在一个合理的假设下，运行时间必须是n^θ(K))，所以我不确定除了使用原始bit arrays的蛮力之外还能推荐什么。

Answer 2

我还不确定这是否正确，但希望它至少是接近的。我们考虑一个动态规划解决方案。列举单词1到N，字母表1到P中的字母。我们希望能够根据所有子解决方案来求解(n，p)。我们考虑了几种情况。

最简单的情况是第n个单词已经存在于(n-1，p)的解决方案中的字典中。然后我们认为自己很幸运，增加了一个包含的单词，并保持字典不变( dictionary在这里指的是字母的某个子集)。

相反，假设第n个单词不在(n-1，p)给定的字典中。则字典解(n-1，p)是(n，p)的字典，或者第n个单词在解中。因此，我们寻找明确涉及第n个单词的解决方案。因此，我们将第n个单词中的所有字母添加到我们正在考虑的字典中。现在我们搜索形式(n-1，i)的所有以前的子解，其中i是p-1或更小。我们正在寻找i的最大值，使得|d(n-1，i) U(N)| <= p。其中d(n-1，i)表示与该解相关联的字典，d(n)仅表示与第n个单词的所有字母相关联的字典。在简单的英语中，我们使用我们的子解来找到具有较小p值的最佳解决方案，从而使我们能够适应新单词。一旦我们找到了i的值，我们就合并我们正在测量其量值的字典。如果这个集合的大小仍然不是p，我们重复前面描述的过程。当我们用这种技术(或迭代所有以前的解决方案)创建了一个量级为p的字典，涵盖了第n个单词时，我们计算它的覆盖率，并将其与我们简单地使用(n-1，p)中的字典获得的覆盖率进行比较，然后我们选择更好的。如果打成平手，我们两个都选。

我不完全相信这个解决方案的正确性，但我认为它可能是正确的。有什么想法？

Answer 3

我会这样做：

1. 使用输入单词创建一个数据结构，该数据结构将字母(字符串)列表映射到它们所覆盖的单词数。你可以通过提取组成单词的唯一字母，对它们进行排序，并将结果用作散列映射关键字。
2. 会忽略关键字长度超过P的任何条目(不能通过有限的字母表覆盖这些单词)。
3. 对于所有剩余的整体，计算它们包含的条目列表(字母表'ab‘包含字母'b’和'a')。将这些条目覆盖的字数相加。
4. 会查找键数最多的条目。