Эффективное распределение вариантов по людям

Question

(извините за вопросы, этот вопрос НЕ является дубликатом, вопрос, который был дубликатом, был ошибочным и был удален)

Допустим, у меня есть данные о выборе людей:

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

Любые мысли или советы приветствуются.

Answer 1

Вот грубый подход к решению проблемы, которая, на мой взгляд, является 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"] 

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

Answer 2

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

Надеюсь, код не требует пояснений, или я добавлю объяснение позже.

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

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"]

Answer 3

Давайте сделаем это шаг за шагом.

choices = {"choices"=> {
  "jaime"=>["apple", "banana"],
  "taylor"=>["apple"],
  "pat"=>["apple", "pear"]
}}['choices']

Давайте теперь создадим обратный хэш фруктов => people:

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"}

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