找到各种分配水果给人们的方法

Question

# 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"},
]

在尝试递归解决这个问题时卡住了(对于这个练习是必要的，如果你认为递归是不可能的，请告诉我)。

我觉得我基本上是从随机分配给一个人一个水果开始，然后把它加到所有可能的解决方案中，这些解决方案来自分配给剩下的人剩余水果的较小子集。

。例如，我给Terry分配了一个苹果，然后将它与Merry可能得到的剩余选项(葡萄或桃子)聚合在一起。

然后重复改变分配给第一个随机的人的水果(例如，在例1中，特里得到葡萄然后得到桃子)。

我觉得这听起来很简单，但我很纠结。

Answer 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在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

这将产生与上面所示的递归解相同的返回值。

参见Array#permutation and Enumerable#zip。

Answer 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，那么就完成了，使用空溶液。(不要与no solution混淆)

• 如果len(fruit) == 0，那么没有人得到任何水果。这是一个实际的解决方案。

• 如果len(people) <= len(fruit)，那么第一个人得到一些水果，附加到其余人得到剩余水果的所有可能结果上。

• 如果len(people) > len(fruit)，那么第一个人得到或没有得到一块水果，然后递归地剩下的人得到剩下的东西。

如何编写这段代码留给你作为练习。

Answer 3

供将来参考，这是我使用递归的答案。

注意"nil"在数量上超过;自"nil"作为唯一条目，代码将{"Terry"=>"apple","Merry"=>"nil","Perry"=>"nil"}和{"Terry"=>"apple","Perry"=>"nil","Merry"=>"nil"}读取为两个不同的解。我没有进一步研究，因为对于这是一部分的练习来说，这不是超级现实的。

出于同样的原因，我也没有进一步调查，但是使用字符串"nil"和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