你将如何编写一个程序来在单词列表中找到最短的pangram?

我们可以减少 Set Cover problem 给我们的那个。设置封面的不同之处在于,不是使用的字母数量最小化,而是使用的单词数量最小化。假设我们要解决集合覆盖问题,给定N个单词,每个单词的长度小于M。让我们通过克隆给定的单词集来构建另一组单词,但要将N*M个非英语字母连接到每个单词上,比如。如果我们能建立一个需要最少符号的盘古图(在a,b,c…x,y,z,字母表上),如果我们去掉所有的字母,那将是一个单词最少的盘古图。

到 一些NP困难的问题,以重用其(希望已经知道)启发式。集合覆盖有一个贪婪的启发式对数近似,但我不认为它适用于原来的问题(集合覆盖问题的性质要求采取字母丰富,长词;这不是解决我们问题的方法)。

set cover problem (又名。 hitting set problem ):

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

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

因为我们只对角色感兴趣,所以问题就容易多了。维护每个角色的地图 [a-z] 在弦中的位置。单凭这张地图就足以确定我们是否有一个圆图,它的长度是多少。

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。

下面是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

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

pangram = Pangram.new("..")
print pangram.shortest

我写了一个程序 一些 the code on github .

帮助最大的是:

我拿了一本字典,把所有的单词都转换成它们的分类字母集。例如,这样“BAD”和“DAB”都存储为“ABD”。我使用的压缩字典将约250000个单词压缩到了约31000个独特的字母组合,这是一个巨大的胜利。

启发式

正如其他地方提到的,这是NP难的,所以我开始使用启发式。我目前使用的三种方法是:

当我检查挑选一个单词后剩下的字母时,我会计算“元音/”未使用的字母。这样做的动机很简单——有更多的元音可以让我更有可能选择使用这些字母的单词。

当我读入初始单词集时,我为字母表中的每个字母创建一个字典,并计算每个字母在所有单词中出现的次数。我用这本字典来选择那些剩下的字母有更多普通字母的节点(我相信OP在评论中提到了这一点)

共享的三字母组合

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

最后,一定要像字母通用性度量一样,我有一个字典映射所有26个字母,选择3个可能的字母集,映射到这些组合在我的单词集中出现的次数。然后我用它来更倾向于搜索剩余字母有更有效的3个字母组合的节点。