6

给定一个包含至少一次字母 az 的单词列表，你将如何编写一个程序来找到以字符数（不包括空格）作为单词组合的最短pangram ？

由于我不确定是否存在简短的答案，因此这不是代码高尔夫，而只是讨论您将如何处理这个问题。但是，如果你认为你可以编写一个短程序来做到这一点，那就继续吧，这可能会变成代码高尔夫 :)

4

4 回答 4

7

我会通过证明问题是 NP-hard 来解决这个问题，并通过检查看起来相似的 NP-hard 问题的启发式方法。

我们可以将Set Cover 问题简化为我们的问题。Set Cover 的不同之处在于，不是使用的字母数量被最小化，而是使用的单词数量被最小化。假设我们要解决 Set Cover 问题，给定 N 个单词，每个单词的长度都小于 M。让我们通过克隆给定的集合来构建另一组单词，但是将 N*M 个非英文字母连接到每个单词上，比如 Ж。如果我们可以构建一个需要最少符号的 pangram（在 a,b,c...x,y,z,ж 字母表上），如果我们删除所有 Ж 字母，那将是一个包含最少单词的 pangram。

这证明了原始问题是 NP 难题，但不幸的是，我们需要简化为一些 NP 难题来重用其（希望是已知的）启发式。Set-Cover 具有对数近似的贪婪启发式算法，但我认为它不适用于原始问题（Set-Cover 问题的性质要求采用字母丰富的长词；这不是解决我们问题的方法）。

所以我会搜索相关的 NP 难题列表，并检查是否有感兴趣的东西。我就是这样处理这个的。

于 2010-04-25T19:30:20.300 回答
2

这是集合覆盖问题（又名命中集合问题）的变体：

作为输入，您将获得几组。它们可能有一些共同点。您必须选择最少数量的这些集合，以便您选择的集合包含输入中任何集合中包含的所有元素。[...] 在 1972 年被证明是 NP-complete [,] 并且 set cover 的优化版本是 NP-hard。

这是一个变体，因为我们正在寻找最少的字母数，而不是最少的单词数。但我认为它仍然是 NP 难的，这意味着你将无法比蛮力做得更好。

于 2010-04-25T19:30:44.217 回答
2

当您将字符串而不是单词列表作为输入时，这是针对不同问题的O(n)算法。. 这是我的疏忽，但将解决方案留在这里，因为我不想删除它:)

因为我们只对字符感兴趣，所以问题就容易多了。维护每个字符[a-z]到其在字符串中的位置的映射。仅此地图就足以确定我们是否有一个 pangram 以及它的长度是多少。

1. Initialize a map of all alphabets to null
2. Initialize shortest_pangram to { length: ∞, value: undefined }
3. Loop through each "character" in given string
  3.1 Update the value of map[character] to current string index
  3.2 If we have a pangram, and its the shortest so far, record its length/value
4. shortest_pangram should have our result

我们创建的地图足以确定我们是否有一个 pangram - 如果我们的地图中的所有值都不为空，我们就有一个 pangram。

要找到当前 pangram 的长度，请从我们地图中的最小值中减去最大值。请记住，在找到长度之前，我们必须检查它是否是 pangram。

这是 Ruby 中一个天真的非优化实现：

class Pangram
  def initialize(string)
    @input = string.downcase.split('')
    @map = {}
    ('a'..'z').each { |c| @map[c] = nil }
    infinity = 1.0/0.0
    @best = { :length => infinity, :string => nil }
  end

  def shortest
    @input.each_with_index do |c, index|
      @map[c] = index if @map.key?(c)
      if pangram? and length < @best[:length]
        @best[:length] = length
        @best[:string] = value
      end
    end
    @best
  end

  def pangram?
    @map.values.all? { |value| !value.nil? }
  end

  def length
    @map.values.max - @map.values.min
  end

  def value
    @input[@map.values.min..@map.values.max].join('')
  end
end

要使用，请实例化该类并将整个字符串传递给它。调用 .shortest 以查找最短 pangram 的长度和匹配的子字符串。

pangram = Pangram.new("..")
print pangram.shortest
于 2010-04-25T20:48:13.810 回答
1

这是一个老问题，所以可能你已经找到了一些你已经喜欢的启发式方法。我在探索生成完美 pangrams 的方法时遇到了这个问题，这将是最少的字符（因为它们只允许使用字母表中的每个字母一次）。无论如何，对于像我这样的未来发现者：

我写了一个成功的程序。我将这个问题更像是图形搜索而不是设置覆盖，并使用 A* 作为算法的起点。您可以浏览github 上的代码。

最有帮助的事情是：

压缩状态空间

我拿了一本字典，将所有单词转换成它们的排序字母集。例如，这种方式“BAD”和“DAB”都存储为“ABD”。我使用的压缩字典将大约 250,000 个单词缩减为大约 31,000 个独特的字母组合，这是一个巨大的胜利。

启发式

正如其他地方所提到的，这是 NP 很难，所以我开始使用启发式算法。我目前使用的三个是：

元音比率

当我在选择一个单词后检查剩余的字母时，我计算#vowels / #unusedLetters。这样做的动机非常简单——剩余的元音越多，我就越有可能使用这些字母选择单词。

字母共性

当我阅读初始单词集时，我为字母表中的每个字母创建一个字典，并计算每个字母在所有单词中出现的次数。我使用这本字典来选择剩余字母具有更常见字母的节点。（我相信OP在其中一个评论中提到了这个）

共享的 3 字母组合

这类似于字母共性启发式。同样，在处理初始单词集时，我创建了一个字典，其中包含可以用该单词组成的所有 3 个字母组合。例如，字母集 ABC 只有一个有效的组合，但 ABCD 有 [ABC, ABD, BCD]。请记住，我只关心压缩初始单词集后的排序字母集。

所以最后，一定要喜欢字母共性度量，我有一个字典，映射所有 26 个选择 3 个可能的字母集，映射到这些组合在我的词集中出现的次数。然后我使用它来更喜欢搜索剩余字母具有更多有效 3 字母组合的节点。

于 2016-01-01T20:39:25.600 回答