哈希将每个值相互求和

Question

我有如下所示的哈希：

hash = {
  "Hulk" => 25,
  "IronMan" => 75,
  "Groot" => 51,
  "Captain America" =>50,
  "Spider Man" => 40,
  "Thor" => 50,
  "Black Panther" => 49
}

我需要找到一组超级英雄，当我将彼此的值相加时，它们的值将是 100，例如，美国队长 + 雷神 = 100。

我可以使用以下索引迭代散列：

hash.each_with_index { |(key,value),index| ... }

使用内部循环比较每个值。

有没有更好更简单的方法来解决这个问题？

Answer 1

尝试

input["Thor"] + input["Captain America"]

您创建的输入对象是一个散列，从散列中获取值的最简单方法是输入与其关联的键：

hash["key"]

Answer 2

可能的解决方案是：

all_options = input.map { |a| input.without(a).map { |b| [a, b] } }.flatten(1).sort.uniq

valid_options = all_options.select { |r| r.sum(&:second) == 100 }

修改，第一行可以用input.combination(2)实现（oops）。整个问题可以使用以下方法解决：

input.combination(2).select { |r| r.sum(&:second) == 100 }.map(&:to_h)

Answer 3

如果输入量不大，可以使用Array#combination:

1.upto(input.size).
  flat_map do |i|
    input.to_a.combination(i).select do |arrs|
      arrs.map(&:last).reduce(:+) == 100
    end
  end.
  map(&:to_h)
#⇒ [{"Hulk"=>25, "IronMan"=>75},
#   {"Groot"=>51, "Black Panther"=>49},
#   {"Captain America"=>50, "Thor"=>50}]

如果您确定只有 2 个英雄的力量总和达到 100，请在 combination 的参数中用硬编码的 2 替换 1.upto(input.size) 循环。在这种情况下，即使输入量很大，它也足够快。

Answer 4

我想这就是您要找的东西

resultArr = []
input.keys.each do |keyName|
  input.each do |inKey, inValue|
    ((resultArr << [keyName, inKey]) if ((input[keyName] + inValue) == 100)) unless (keyName == inKey)
  end
end

result = []
resultArr.each do |resArr| result << resArr.sort end
result.uniq!
puts result

Answer 5

你可以实现线性复杂度O(N)性能方面

编辑我假设您正在寻找 2 的组合，据我所知，这是不正确的。

input = { 
  "Hulk" => 25,
  "IronMan" => 75,
  "Groot" => 51,
  "Captain America" => 50,
  "Spider Man" => 40,
  "Thor" => 50,
  "Black Panther" => 49
}

# Create inverse lookup map
inverse_input = input.each.with_object(Hash.new([])){ |(k, v), h| h[v] += [k] }
#=> {25=>["Hulk"], 75=>["IronMan"], 51=>["Groot"], 50=>["Captain America", "Thor"], 40=>["Spider Man"], 49=>["Black Panther"]}

input.flat_map do |hero, power| 
  # Get heroes with needed power only
  other_heroes = inverse_input[100 - power]
  # Remove current hero from the list
  other_but_this = other_heroes.reject{ |name| name == hero }
  # Map over remaining heroes 
  # and sort them for later `uniq` filtering
  other_but_this.map { |h| [hero, h].sort }
end.compact.uniq
# compact will remove nils
# uniq will remove duplicates
#=> [["Hulk", "IronMan"], ["Black Panther", "Groot"], ["Captain America", "Thor"]]

如果输入的长度较小，您可以采用更短的 O(N^2) 解决方案：

input.to_a.
      permutation(2).
      select{|(n1,v1), (n2, v2)| n1 != n2 && v1 + v2 == 100 }.
      map{ |l,r| [l.first, r.first].sort }.
      uniq
#=> [["Hulk", "IronMan"], ["Black Panther", "Groot"], ["Captain America", "Thor"]]

哈希将每个值相互求和

Hash to sum every value with each other

ruby

algorithm

ruby-on-rails

knapsack-problem