arrays - 一组有一定长度的单词

这是一种我认为在所需计算数量方面接近最佳的方法。我将首先回答具体问题，然后介绍一种递归方法，该方法将为一般问题生成所需的组合。

解决具体问题

我们看到有两个 3 字母单词数组。我会写2-3。同样，有 2-4、1-5、1-6、1-7 和 1-10。我们可以忘记空数组。

元素之和如何可能是 10？以下是可能性：3-3-4、3-7、4-6、1-10。

我们只需要计算其中每一个的组合并取它们的并集。

对于 3-3-4，我们必须从以下每个数组中取一个元素：

["act", "bat", "cat"]
["boo", "con", "coo"]
["acta"] | ["tots", "tour"]
  #=> ["acta", "tots", "tour"]

我们可以使用Array#product来计算这些组合：

["act", "bat", "cat"].product(["boo", "con", "coo"],
  ["acta", "tots", "tour"])
  #=> [["act", "boo", "acta"], ["act", "boo", "tots"],
  #    ["act", "boo", "tour"], ["act", "con", "acta"],
  #    ["act", "con", "tots"], ["act", "con", "tour"],
  #    ["act", "coo", "acta"], ["act", "coo", "tots"],
  #    ["act", "coo", "tour"], ["bat", "boo", "acta"],
  #    ["bat", "boo", "tots"], ["bat", "boo", "tour"],
  #    ["bat", "con", "acta"], ["bat", "con", "tots"],
  #    ["bat", "con", "tour"], ["bat", "coo", "acta"],
  #    ["bat", "coo", "tots"], ["bat", "coo", "tour"],
  #    ["cat", "boo", "acta"], ["cat", "boo", "tots"],
  #    ["cat", "boo", "tour"], ["cat", "con", "acta"],
  #    ["cat", "con", "tots"], ["cat", "con", "tour"],
  #    ["cat", "coo", "acta"], ["cat", "coo", "tots"],
  #    ["cat", "coo", "tour"]]

3-7、4-6 和 1-10 的组合计算类似。

广义问题的递归方法

def doit(words, target)
  recurse(words.reject do |a|
    a.empty? || a.first.size > target 
  end.sort_by { |a| a.first.size }, target)
end

def recurse(sorted, target)
  arr, *rest = sorted
  sz = arr.first.size
  if rest.empty?
    return sz == target ? arr.map { |s| [s] } : []
  end
  return [] if sz > target
  b = recurse(rest, target) # include no element of arr
  return b if sz != target && sz > target/2
  case target <=> sz
  when -1
    b
  when 0
    d = arr.map { |s| [s] }
    b.empty? ? d : b + d
  else # 1
    c = recurse(rest, target-sz)
    if c.empty?
      b
    else
      d = arr.product(c).map { |s,c| [s] + c }
      b.empty? ? d : b + d
    end
  end
end

如果我们执行

doit words, 10

返回上一节中显示的解决方案，尽管元素的顺序不同。

解释

解释递归是如何工作的具有挑战性。在我看来，最好的方法是插入puts语句。然而，仅此是不够的，因为它很快就会让人对正在调用的方法的哪个实例感到困惑。出于这个原因，我建议缩进结果，如下所示。

INDENT = 4

def indent
  @offset += INDENT
  puts
end

def undent
  @offset -= INDENT
  puts
end

def pu(str)
  puts ' '*@offset + str
end

def doit(words, target)
  @offset = -INDENT #***
  recurse(words.reject do |a|
    a.empty? || a.first.size > target 
  end.sort_by { |a| a.first.size }, target)
end

def recurse(sorted, target)
  indent           #***
  puts             #***
  pu "sorted=#{sorted}"  #***
  pu "target=#{target}"  #***
  arr, *rest = sorted
  sz = arr.first.size
  pu "arr=#{arr}, rest=#{rest}, sz=#{sz}" #***
  if rest.empty?
    pu "returning (sz==target ? arr.map { |s| [s] } : [])="
    pu "#{(sz==target ? arr.map { |s| [s] } : [])}" #***
    undent #***
    return sz == target ? arr.map { |s| [s] } : []
  end

  if sz > target  
    pu "returning [] as sz > target=#{sz > target}" #***
    undent #***
    return []
  end
  pu "calling recurse(#{rest}, #{target}) w/o using an element of #{arr}" #***
  b = recurse(rest, target) # include no element of arr
  pu "b=#{b}" #***
  pu "target=#{target}, sz=#{sz}, target-sz=#{target-sz}" #***
  if sz != target && sz > target/2
    pu "returning b as sz != target && sz > target/2" #*** 
    undent  #***
    return b
  end

  case target <=> sz
  when -1
    pu "  target < sz"  #***
    b
  when 0
    pu "  target == sz" #***
    d = arr.map { |s| [s] }
    b.empty? ? d : b + d
  else # 1
    pu "  target > sz" #***
    pu "calling recurse(#{rest}, #{target-sz}) using an element of #{arr}"  #***
    c = recurse(rest, target-sz)
    pu "c=#{c}" #***
    if c.empty?
      b
    else
      d = arr.product(c).map { |s,c| [s] + c }
      b.empty? ? d : b + d
    end
  end.
  tap do |a|
    pu "returning a=#{a}"  #***
    undent  #***
  end
end

这是一个更简单的使用示例。我将只展示一个输出样本。感兴趣的读者可能希望运行代码并研究结果。

test_words = [["ac", "ba"], ["bo"],
              ["acta"], ["tots", "tour"]] 

doit test_words, 8

显示以下内容。

sorted=[["ac", "ba"], ["bo"], ["acta"], ["tots", "tour"]]
target=8
arr=["ac", "ba"], rest=[["bo"], ["acta"], ["tots", "tour"]], sz=2
calling recurse([["bo"], ["acta"], ["tots", "tour"]], 8) w/o using an element of ["ac", "ba"]


    sorted=[["bo"], ["acta"], ["tots", "tour"]]
    target=8
    arr=["bo"], rest=[["acta"], ["tots", "tour"]], sz=2
    calling recurse([["acta"], ["tots", "tour"]], 8) w/o using an element of ["bo"]

        ...

       b=[["acta", "tots"], ["acta", "tour"]]
       target=8, sz=2, target-sz=6
       target > sz
       calling recurse([["acta"], ["tots", "tour"]], 6) using an element of ["bo"]


           sorted=[["acta"], ["tots", "tour"]]
           target=6
           arr=["acta"], rest=[["tots", "tour"]], sz=4
           calling recurse([["tots", "tour"]], 6) w/o using an element of ["acta"]

               ...

    c=[["tots"], ["tour"], ["acta"]]
    returning a=[["bo", "tots"], ["bo", "tour"], ["bo", "acta"]]

c=[["bo", "tots"], ["bo", "tour"], ["bo", "acta"]]
returning a=[["acta", "tots"], ["acta", "tour"], ["ac", "bo", "tots"], ["ac", "bo", "tour"], ["ac", "bo", "acta"], ["ba", "bo", "tots"], ["ba", "bo", "tour"], ["ba", "bo", "acta"]]

  #=> [["acta", "tots"], ["acta", "tour"],
  #    ["ac", "bo", "tots"], ["ac", "bo", "tour"],
  #    ["ac", "bo", "acta"], ["ba", "bo", "tots"],
  #    ["ba", "bo", "tour"], ["ba", "bo", "acta"]]

arrays - 一组有一定长度的单词

问题描述

解决方案

推荐阅读