Блог

 # Example 1
People = ["Terry", "Merry"]
Fruit = ["Apple","Grape","Peach"]

# Possible solutions:
[
  {"Terry"=>"Apple","Merry"=>"Grape"},
  {"Terry"=>"Apple","Merry"=>"Peach"},

  {"Terry"=>"Grape","Merry"=>"Apple"},
  {"Terry"=>"Grape","Merry"=>"Peach"},

  {"Terry"=>"Peach","Merry"=>"Apple"},
  {"Terry"=>"Peach","Merry"=>"Grape"},
]

# Example 2
People = ["Terry", "Merry", "Perry"]
Fruit = ["Apple","Grape"]

# Possible solutions:
[
  {"Terry"=>"Apple","Merry"=>"Grape","Perry"=>nil},
  {"Terry"=>"Apple","Merry"=>nil,"Perry"=>"Grape"},

  {"Terry"=>"Grape","Merry"=>"Apple","Perry"=>nil},
  {"Terry"=>"Grape","Merry"=>nil,"Perry"=>"Apple"},

  {"Terry"=>nil,"Merry"=>"Apple","Perry"=>"Grape"},
  {"Terry"=>nil,"Merry"=>"Grape","Perry"=>"Apple"},
]
 

Застрял, пытаясь решить это рекурсивно (необходимо для этого упражнения, хотя дайте мне знать, если вы не считаете, что рекурсия возможна).

Я чувствую, что в основном я начинаю с присвоения случайному человеку фрукта, а затем добавляю это ко всем возможным решениям, которые возникают из меньшего подмножества присвоения оставшимся людям оставшихся фруктов.

Например, например, 1, я назначаю Терри яблоко, а затем объединяю его с остальными возможными вариантами того, что может получить Мерри (виноград или персик).

Затем просто повторите изменение фрукта, назначенного первому случайному человеку (например, Терри получает виноград, а затем персик, в примере 1).

Я чувствую, что это звучит так просто, но я борюсь.

Это можно сделать рекурсивно следующим образом.

 def hmmm(people, fruit)
  adj_fruit = fruit   [nil]*([people.size-fruit.size, 0].max)
  recurse(adj_fruit).map { |a| people.zip(a).to_h }
end
 

 def recurse(fruit_left, fruit_selected = [])
  return [fruit_selected   fruit_left] if fruit_left.size == 1
  fruit_left.each_with_object([]) do |f,a|
    recurse(fruit_left - [f], fruit_selected   [f]).each { |e| a << e }
  end
end
 

 hmmm(["Terry", "Merry"], ["Apple", "Grape", "Peach"])
  #=> [{"Terry"=>"Apple", "Merry"=>"Grape"}, {"Terry"=>"Apple", "Merry"=>"Peach"},
  #    {"Terry"=>"Grape", "Merry"=>"Apple"}, {"Terry"=>"Grape", "Merry"=>"Peach"},
  #    {"Terry"=>"Peach", "Merry"=>"Apple"}, {"Terry"=>"Peach", "Merry"=>"Grape"}]
 

Здесь adj_fruit #=> ["Apple", "Grape", "Peach"]

 hmmm(["Terry", "Merry", "Perry"], ["Apple", "Grape"])
  #=> [{"Terry"=>"Apple", "Merry"=>"Grape", "Perry"=>nil},
  #    {"Terry"=>"Apple", "Merry"=>nil,     "Perry"=>"Grape"},
  #    {"Terry"=>"Grape", "Merry"=>"Apple", "Perry"=>nil},
  #    {"Terry"=>"Grape", "Merry"=>nil,     "Perry"=>"Apple"},
  #    {"Terry"=>nil,     "Merry"=>"Apple", "Perry"=>"Grape"},
  #    {"Terry"=>nil,     "Merry"=>"Grape", "Perry"=>"Apple"}]
 

Здесь adj_fruit #=> ["Apple", "Grape", nil] .

Мы можем увидеть map ‘s receiver в hmmm , удалив .map { |a| people.zip(a).to_h } из его последней строки.

 def hmmm(people, fruit)
  adj_fruit = fruit   [nil]*([people.size-fruit.size, 0].max)
  recurse(adj_fruit)
end
 

 hmmm(["Terry", "Merry"], ["Apple","Grape","Peach"])
  #=> [["Apple", "Grape", "Peach"], ["Apple", "Peach", "Grape"],
  #    ["Grape", "Apple", "Peach"], ["Grape", "Peach", "Apple"],
  #    ["Peach", "Apple", "Grape"], ["Peach", "Grape", "Apple"]]
 

Более традиционное решение, такое как следующее, не будет использовать рекурсию.

 def hmmm(people, fruit)
  (fruit   [nil]*[people.size - fruit.size, 0].max).
    permutation(people.size).
    map { |a| people.zip(a).to_h }
end
 

Это приводит к тем же возвращаемым значениям, что и показанные выше для рекурсивного решения.

Смотрите Массив #перестановка и Перечисляемый #zip.

Если len(people) <= len(fruit) , то вы можете использовать

 for pieces in itertools.permutations(fruit, len(people)):
    assign the pieces of fruit to the people in order
 

Если len(people) > len(fruit) , то используйте

 for eaters in itertools.permutations(people, len(fruit))
    assign the eaters to the fruit in order, and the others get nothing
 

Я не знаю, как объединить два отдельных случая в один случай

Теперь я вижу, что это должно было решаться рекурсивно. Неправильно прочитал оригинал.

Давайте рассмотрим возможности для

назначение (люди, фрукты):

• Если len(people) == 0 , тогда вы закончили с пустым решением. (Не путать с отсутствием решения.)
• Если len(fruit) == 0 , то никто не получает никаких фруктов. Опять же, это реальное решение.
• Если len(people) <= len(fruit) , то первый человек получает какой-то фрукт, добавленный ко всем возможным результатам остальных людей, получающих оставшуюся часть фруктов.
• Если len(people) > len(fruit) , то либо первый человек получает, либо не получает фрукт, а рекурсивно остальные люди получают все, что осталось.

Вам остается в качестве упражнения, как это закодировать.

Для любого дальнейшего использования это был мой ответ с использованием рекурсии.

ОБРАТИТЕ внимание, что «ноль» перерасчитывается; поскольку «ноль» обрабатывается как уникальная запись, код считывается {"Terry"=>"apple","Merry"=>"nil","Perry"=>"nil"} и {"Terry"=>"apple","Perry"=>"nil","Merry"=>"nil"} как 2 разных решения. Я не стал исследовать дальше, потому что это не очень реалистично для упражнения, частью которого это является.

Я также не проводил дальнейших исследований по той же причине, но использование string "nil" versus nil дало разные результаты

   def pure5(people, fruit, solution = [])
    people_count = people.size 
    fruit_count = fruit.size 
    diff = people_count - fruit_count
    diff.times { fruit << "nil" } if diff > 0 

    people.each do |p|
      fruit.each do |f|
        if people.size == 1
          obj = {}
          obj[p] = f
          solution << obj
        else
          partial_solution = pure5(people - [p], fruit - [f])
          partial_solution.each do |s|
            s[p] = f
          end    
          solution = solution   partial_solution
        end
      end
      return solution
    end
  end