#ruby-on-rails #ruby
Вопрос:
# 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).
Я чувствую, что это звучит так просто, но я борюсь.
Ответ №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.
Комментарии:
1. всегда на помощь спасибо! если я могу спросить … когда вы говорите, что не знаете, можно ли это сделать с помощью рекурсии, это просто не подразумевает, например, я не знаю, я не думал об этом; или есть намек на то, что это сложно, например, я не знаю, потому что это кажется сложным? ЕСЛИ последнее, какое-нибудь представление о том, почему это может быть сложно? потому что концептуально это кажется мне простым, но я всегда смотрел на свою статью…
2. Для любого использования в будущем,
nil
определенно бросает некоторые ключи в это… с помощью рекурсивного методаnil
недоучеты (я не исследовал, почему). с помощью нерекурсивного методаnil
overcounts посколькуnil
обрабатывается как уникальная запись, код считывается{"Terry"=>"apple","Merry"=>nil,"Perry"=>nil}
и{"Terry"=>"apple","Perry"=>nil,"Merry"=>nil}
как 2 разных решения3. О, да, извините, я тестировал с новым вариантом использования:
hmmm(["Terry", "Merry","Perry"], ["Apple"])
, это возвращает 2 возможных решения[{"Terry"=>nil, "Merry"=>"Apple", "Perry"=>nil}, {"Terry"=>nil, "Merry"=>"Apple", "Perry"=>nil}]
. Опять же, хотя и не имеет большого значения для этого конкретного упражнения4. джеймс, это не проблема. Я удалил свой комментарий; возможно, вы захотите удалить свой.
Ответ №2:
Если 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)
, то либо первый человек получает, либо не получает фрукт, а рекурсивно остальные люди получают все, что осталось.
Вам остается в качестве упражнения, как это закодировать.
Комментарии:
1. как вы думаете, это можно сделать с помощью рекурсии
2. О, извините. Не видел часть рекурсии в конце . . . .
Ответ №3:
Для любого дальнейшего использования это был мой ответ с использованием рекурсии.
ОБРАТИТЕ внимание, что «ноль» перерасчитывается; поскольку «ноль» обрабатывается как уникальная запись, код считывается {"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