(很抱歉问题，这个问题不是重复的，重复的问题是一个错误的帖子，已被删除)
假设我有关于人们选择的数据：
data = {"choices"=> {
"jaime"=>["apple", "banana"],
"taylor"=>["apple", "pear"],
"pat"=>["apple", "pear","banana"]
}}
数据意味着詹姆并不关心得到苹果或香蕉。现在我想进行一个公平的分配，以便每个人都得到一种符合他们偏好的水果，但哪种水果并不重要。
还有其他条件：
如果选择- 太多(如果水果比人多)，那么有人仍然会有额外的选择(见下面的第一个示例)，而其他人都得到 1 件事。 如果
- 选择太少(如果水果比人少)，那么有人根本不会得到任何东西。 为
- 简单起见，假设谁是幸运的人或最终空手而归的人并不重要，所以让我们假设它总是归结为数据列表中的最后一个人 鉴于这些条件，请考虑以下示例。
data = {"choices"=> {
"jaime"=>["apple", "banana"],
"taylor"=>["apple", "pear"],
"pat"=>["apple", "pear","banana","orange"]
}}
outcome = {
"jaime"=>["apple"],
"taylor"=>["pear"],
"pat"=>["banana","orange"]
}
data = {"choices"=> {
"jaime"=>["apple", "banana"],
"taylor"=>["apple", "pear"],
"pat"=>["apple", "banana"]
}}
outcome = {
"jaime"=>["apple"],
"taylor"=>["pear"],
"pat"=>["banana"]
}
data = {"choices"=> {
"jaime"=>["apple", "banana"],
"taylor"=>["apple", "banana"],
"pat"=>["apple", "banana"]
}}
outcome = {
"jaime"=>["apple"],
"taylor"=>["banana"],
"pat"=>[]
}
我开始集思广益一些代码
data = {"choices"=> {
"jaime"=>["apple", "banana"],
"taylor"=>["apple", "pear"],
"pat"=>["apple", "pear","banana"]
}}
fruit_avail = ["apple","banana","pear"]
result = {"allocation"=>{},"will_not_get_anything"=>[]}
# helper array, contains people that are "done" being allocated
finished = []
fruit_avail.each do |fruit|
unfinished = data["choices"].reject { |person,options| finished.include? person }
# helper hash, contains people who have yet to be allocated (opposite of finished)
first_person_who_has_fruit_choice = unfinished.first { |person,options| v.include? fruit }[0]
# this is the "someone". since i use .first, this will bias toward the first person with the fruit preference in the choices data getting it. In other words, in the absense of enough fruit, the last person will be empty handed, in the presence of too much fruit, the last person will also have the extra choice
unfinished.each do |person, options|
if first_person_who_has_fruit_choice == person
result["allocation"][person] = [fruit]
finished << person
else
updated_options = result["allocation"][person].present? result["allocation"][person] : options
# helper variable, gets the latest options for this person (which may have been trimmed due to earlier allocations
remaining_options = updated_options - [fruit]
result["allocation"][person] = remaining_options
result["will_not_get_anything"] << person if remaining_options.blank?
end
end
end
但是上面没有捕捉到数据如下所示的情况：
data = {"choices"=> {
"jaime"=>["apple", "banana"],
"taylor"=>["apple"],
"pat"=>["apple", "pear"]
}}
由于代码只是在列表中工作，因此它将产生以下结果：
outcome = {
"jaime"=>["apple"],
"taylor"=>[],
"pat"=>["pear"]
}
而实际正确的结果应该是：
outcome = {
"jaime"=>["banana"],
"taylor"=>["apple"],
"pat"=>["pear"]
}
任何想法或建议表示赞赏。
这是一种解决我认为是NP完全问题的蛮力方法。保证最大限度地增加被分配首选水果的人数。
法典
def assign_fruit(preferences, basket)
prefs = preferences.values
best = [nil, nil, nil]
best_count = 0
basket.permutation(prefs.size) do |perm|
arr = prefs.zip(perm).map { |pref, p|
pref.include?(p) ? p : nil }
sz = arr.compact.size
if sz > best_count
best = arr
break if sz == prefs.size
best_count = sz
end
end
preferences.transform_values { best.shift }
end
例子
preferences = {
"jaime"=>["apple", "banana"],
"taylor"=>["apple", "pear"],
"pat"=>["apple", "pear", "banana", "orange"]
}
assign_fruit(preferences, ["pear", "banana", "plum"])
#=> {"jaime"=>"banana", "taylor"=>"pear", "pat"=>nil}
assign_fruit(preferences, ["pear", "banana", "apple", "plum"])
#=> {"jaime"=>"banana", "taylor"=>"pear", "pat"=>"apple"}
assign_fruit(preferences, ["pear", "banana", "orange"])
#=> {"jaime"=>"banana", "taylor"=>"pear", "pat"=>"orange"}
assign_fruit(preferences, ["orange", "orange", "orange"])
#=> {"jaime"=>nil, "taylor"=>nil, "pat"=>"orange"}
此方法允许水果篮包含超过每个水果一个的计数。
解释
如果prefences如示例中给出的，并且
basket = ["pear", "banana", "plum", "fig"]
然后
prefs = preferences.values
#=> [["apple", "banana"], ["apple", "pear"],
# ["apple", "pear", "banana", "orange"]]
enum = basket.permutation(prefs.size)
#=> #<Enumerator: ["pear", "banana", "plum",
# "fig"]:permutation(3)>
enum.size
#=> 24
我们可以看到enum通过将enum转换为数组来生成并传递给块的元素：
enum.to_a
#=> [["pear", "banana", "plum"], ["pear", "banana", "fig"],
# ["pear", "plum", "banana"], ["pear", "plum", "fig"],
# ["pear", "fig", "banana"], ["pear", "fig", "plum"],
# ...
# ["fig", "plum", "pear"], ["fig", "plum", "banana"]]
生成并传递给块的第一个元素是：
perm = enum.next
#=> ["pear", "banana", "plum"]
然后我们计算：
pairs = prefs.zip(perm)
#=> [[["apple", "banana"], "pear"],
# [["apple", "pear"], "banana"],
# [["apple", "pear", "banana", "orange"], "plum"]]
然后映射到：
pairs.map { |pref, p| pref.include?(p) ? p : nil }
#=> [nil, nil, nil]
表明没有人收到首选水果。
考虑第二个示例。什么时候：
perm = ["pear", "apple", "banana"]
我们获得：
pairs = prefs.zip(perm)
#=> [[["apple", "banana"], "pear"],
# [["apple", "pear"], "apple"],
# [["apple", "pear", "banana", "orange"], "banana"]]
pairs.map { |pref, p| pref.include?(p) ? p : nil }
#=> [nil, "apple", "banana"]
表明两个人应该高兴。对于所考虑的每个排列，将接受首选水果的人数与迄今为止最好的数量进行比较。如果该数字大于到目前为止的最佳分配，则该分配将成为迄今为止的最佳分配。如果每个人都收到首选水果，我们就可以打破循环。
让我们一步一步来。
choices = {"choices"=> {
"jaime"=>["apple", "banana"],
"taylor"=>["apple"],
"pat"=>["apple", "pear"]
}}['choices']
现在让我们构建水果 => 人的反向哈希：
fruits_to_ppl =
choices.each_with_object(Hash.new { |h, k| h[k] = [] }) do |(k, vs), acc|
vs.each { |v| acc[v] << k }
end.sort_by { |_, v| v.size }.to_h
#⇒ {"banana"=>["jaime"], "pear"=>["pat"], "apple"=>["jaime", "taylor", "pat"]}
另外，让我们按首选项列表的大小对 ppl 进行排序：
sorted = choices.sort_by { |_, v| v.size }.map(&:first)
好的，我们已经准备好了。
distribution =
fruits_to_ppl.each_with_object(Hash.new { |h, k| h[k] = [] }) do |(f, ppl), acc|
who = sorted.detect { |s| ppl.detect(&s.method(:==)) && acc[s].empty? }
acc[who] = f if who
end
#⇒ {"jaime"=>"banana", "pat"=>"pear", "taylor"=>"apple"}
此解决方案不完整，可能需要显式处理存储桶中剩余的内容，但这将是完成任务的良好起点。
这是一个冗长的解决方案，不是为了展示基本思想而优化的。
我希望代码是不言自明的，或者我稍后会添加解释。
基本思想是跟踪一个人收到多少水果，每次都进行排序，以便优先考虑拥有较少水果的人。
data = {"choices"=> {
"jaime"=>["apple", "banana", "kiwi"],
"taylor"=>["apple", "pear","peach"],
"pat"=>["apple", "pear","banana","peach"]
}}
fruit_avail = ["apple","banana","pear","peach","melon"]
# setup
people_fruits_request = data['choices'].transform_values { |v| v & fruit_avail }.sort_by{ |_, v| v.size }.to_h
people_fruits_allocation = people_fruits_request.transform_values { |v| v = [] }
people_fruits_count = people_fruits_request.transform_values { |v| v = 0 }
fruit_avail_requested = fruit_avail & people_fruits_request.values.flatten.uniq
# calculation
fruit_avail_requested.each do |fruit|
people_requesting = people_fruits_request.select { |_, fruits| fruits.include? fruit }.keys
person = (people_fruits_count.sort_by { |k,v| v}.map(&:first) & people_requesting).first
people_fruits_allocation[person] << fruit
people_fruits_count[person] += 1
end
people_fruits_allocation
#=> {"jaime"=>["apple"], "taylor"=>["pear", "peach"], "pat"=>["banana"]}
fruits_left_in_the_basket = fruit_avail - fruit_avail_requested
#=> ["melon"]