Хеш для суммирования каждого значения друг с другом

Question

У меня есть хеш, как показано ниже:

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

Мне нужно найти набор супергероев, значение которых будет равно 100, когда я подведу итоги друг другу, например, Captain America + Thor = 100.

Я могу перебрать хеш с индексом:

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

с внутренним циклом, сравнивающим каждое значение.

Есть ли лучший и простой способ подойти к этому?

Answer 1

вы можете достичь линейной сложности 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"]]

Answer 2

Я думаю, это то, что вы ищете

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 3

Потенциальное решение будет:

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) (упс). Вся эта проблема может быть решена с помощью:

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

Answer 4

Если ввод не велик, можно использовать 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, замените цикл 1.upto(input.size) на жестко закодированный 2 в аргументе combination.В этом случае это будет достаточно быстро даже для огромных входных данных.

Answer 5

Попробуйте

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

Созданный вами объект ввода - это хеш, и самый простой способ получить значение из хеша - ввести ключ, с которым он связан:

hash["key"]