algorithm - 是否可以从给定的单词列表生成 Pangram？

Question

Pangram是使用字母表中的每个字母至少一次的句子。

是否可以生成最短的Pangram来自给定的单词列表？

比方说，我有这样的单词列表

cat monkey temp banana christmas 
fast quick quickest jumping 
white brown black blue
fox xor jump jumps oven over 
now the is was 
lazy laziest crazy
dig dog joker mighty

并喜欢生成可能的 pangrams 列表，如下所示

the quick over lazy jumps fox dog brown
brown dog fox jumps lazy over quick the
quick brown fox jumps over the lazy dog

语法和词序暂时不需要考虑(我打算用非英语语言)

任何想法、算法、代码、引用，将不胜感激!

PS:这不是作业

Answer 1

从单词列表中生成所有可能的 pangram 的最简单方法可能是从列表中生成所有可能的单词组合，然后针对每个单词检查它是否是 pangram。要进行检查，遍历字符串并将字符串中的每个字母的 bool 值设置为 true。最后，如果 bool 值都设置为 true，则它是一个 pangram。

更有效的方法可能是遍历每个单词，并设置一个 bool 数组(或一组位，例如在 32 位 int 中)以及单词的长度。然后你可以找到 or'd 一起产生一个值的位，所有 26 位都设置了，你就有了一个 pangram。

当您将 pangram 放在一起时，您可以添加边界检查，因此如果添加一个单词会使潜在的 pangram 比您当前最短的 pangram(如果有的话)更长，您可以立即停止该检查。如果您首先按长度对单词进行排序，那么在您找到更长的组合的那一刻，您就可以放弃整组尝试，并继续下一个可能性。

如果您想对其进行更复杂的了解，您可以从构建与上述相同类型的位集开始。然后把这些，加在一起以确定哪些字母出现在最少的单词中。当您开始生成一个潜在的 pangram 时，您知道它必须包含其中一个词。例如。在您上面给出的列表中，“lazy”、“laziest”和“crazy”似乎是唯一包含“z”的，因此您立即知道每个 pangram 必须包含这三个之一字。这些都不包含“q”，唯一包含“q”的词似乎是“quick”和“quickest”，所以(再次)每个 pangram 都必须包含这两个词之一(当然我要去来自此处的手动检查，所以我可能漏掉了一个词)。因此，该列表中的每个可能的 pangram 都包括(也可能以以下开头):(quick|quickest) (lazy|laziest|crazy)。

您还可以考虑预处理您的单词列表:任何比另一个长但不包含至少一个字母缺失的单词都可以立即被删除。举个假设的例子，如果你有“ab”和“abab”，你知道“abab”永远不会产生比“ab”更短的全字母组合，所以你最好立即从列表中删除它。