Как разделить всех участников на отдельные честные команды на основе их рейтинга?
Я хочу разделить игроков на отдельные честные команды на основе их рейтинга. Например, у меня есть такой список игроков:
players = [{
name: "Qasim",
rating: 1
}, {
name: "Mahsam",
rating: 7
}, {
name: "Aj",
rating: 3
}, {
name: "Osman",
rating: 6
}, {
name: "Usama",
rating: 2
}, {
name: "Bilal",
rating: 8
}, {
name: "Kaka",
rating: 20
}, {
name: "Owen",
rating: 15
}
]
Я хочу разделить их на 4 команды с лучшими равными общими баллами, а также поровну по участникам следующим образом:
Team A Team B Team C Team D
======= ======= ======= =======
Kaka: 20 Owen: 15 Bilal: 8 Mahsam: 7
Qasim: 1 Usama: 2 Aj: 3 Osman: 6
Я нашел способ решить эту проблему, но его трудно превратить в рубиновый код. Предположим, что у нас может быть более 8 игроков, а количество команд может варьироваться от 2 до 4 команд.
1. Sort all players by their ratings descendingly.
2. Assign team A the best player.
3. Assign team B the next best player.
4. Assign team C the next best player.
5. Assign team D the next best player.
6. Assign team D the next best player.
7. Assign team C the next best player.
8. Assign team B the next best player.
9. Assign team A the next best player.
10. Go to 2
11. End when we're out of players.
На самом деле в команде может быть от 2 до 4 команд, все игроки в каждой команде должны быть равными, и суммарные рейтинги каждой команды тоже должны быть равными или как можно ближе к равным.
Количество игроков может быть любым, и они должны делиться на команды.
Например, если 2 команды, общее количество игроков должно быть четным. Если 3 команды, общее количество игроков должно делиться на 3, а если 4 команды, общее количество игроков должно делиться на 4.
Мне кажется, что это NP-полная проблема. Я не уверен, что это просто вариант проблема с рюкзаком. Или если он достаточно особенный, чтобы иметь собственное имя. Возможно, вы захотите просмотреть одну из известных задач комбинаторной оптимизации.
@CarySwoveland Я уже написал это в вопросе «... Я нашел способ решить эту проблему ...».
Ответы 2
Мы можем решить эту проблему, отсортировав хэш по рейтингу ключа.
players.sort_by { |k| k[:rating] }
Теперь, когда вы отсортировали массив.
Вы можете выполнить итерацию до половины длины массива и нажать элемент i и элемент length-i в одной команде, в этом случае у вас есть 4 команды.
def divide_teams players
players = players.sort_by { |k| k[:rating] } # sorted
len = players.length
teams = Hash.new(0)
(len/2).times do |i|
teams["team#{i+1}"] = [players[i], players[len-i-1]]
end
teams
end
divide_teams players
=> {"team1"=>[{:name=>"Qasim", :rating=>1}, {:name=>"Kaka", :rating=>20}],
"team2"=>[{:name=>"Usama", :rating=>2}, {:name=>"Owen", :rating=>15}],
"team3"=>[{:name=>"Aj", :rating=>3}, {:name=>"Bilal", :rating=>8}],
"team4"=>[{:name=>"Osman", :rating=>6}, {:name=>"Mahsam", :rating=>7}]}
Сейчас, как я предположил, 4 команды и в каждой по 2 человека.
вы можете изменить функцию в соответствии с вашими потребностями, если функция team является динамической переменной.
Спасибо.
Вы можете реализовать описанный вами алгоритм назначения следующим образом.
def assign(nbr_teams, players)
flip = [true, false].cycle
players.
sort_by { |p| p[:rating] }.
each_slice(nbr_teams).
map { |a| flip.next ? a.reverse : a }.
transpose
end
assign(4, players)
#=> [[{:name=>"Osman", :rating=>6}, {:name=>"Mahsam", :rating=>7}],
# [{:name=>"Aj", :rating=>3}, {:name=>"Bilal", :rating=>8}],
# [{:name=>"Usama", :rating=>2}, {:name=>"Owen", :rating=>15}],
# [{:name=>"Qasim", :rating=>1}, {:name=>"Kaka", :rating=>20}]]
Задания были бы такими, если бы было 2 команды.
assign(2, players)
#=> [[{:name=>"Usama", :rating=>2}, {:name=>"Aj", :rating=>3},
# {:name=>"Bilal", :rating=>8}, {:name=>"Owen", :rating=>15}],
# [{:name=>"Qasim", :rating=>1}, {:name=>"Osman", :rating=>6},
# {:name=>"Mahsam", :rating=>7}, {:name=>"Kaka", :rating=>20}]]
Шаги следующие.
nbr_teams = 4
flip = [true, false].cycle
#=> #<Enumerator: [true, false]:cycle>
Массив#цикл работает так: flip.next #=> true, flip.next #=> false, flip.next #=> true и так далее. Продолжая,
a = players.sort_by { |p| p[:rating] }
#=> [{:name=>"Qasim", :rating=>1}, {:name=>"Usama", :rating=>2},
# {:name=>"Aj", :rating=>3}, {:name=>"Osman", :rating=>6},
# {:name=>"Mahsam", :rating=>7}, {:name=>"Bilal", :rating=>8},
# {:name=>"Owen", :rating=>15}, {:name=>"Kaka", :rating=>20}]
b = a.each_slice(nbr_teams)
#=> #<Enumerator:
# [{:name=>"Qasim", :rating=>1}, {:name=>"Usama", :rating=>2},
# {:name=>"Aj", :rating=>3}, {:name=>"Osman", :rating=>6},
# {:name=>"Mahsam", :rating=>7}, {:name=>"Bilal", :rating=>8},
# {:name=>"Owen", :rating=>15}, {:name=>"Kaka", :rating=>20}]
# :each_slice(4)>
Мы можем преобразовать этот перечислитель в массив, чтобы увидеть, какие объекты он сгенерирует и передаст в map.
b.to_a
#=> [[{:name=>"Qasim", :rating=>1}, {:name=>"Usama", :rating=>2},
# {:name=>"Aj", :rating=>3}, {:name=>"Osman", :rating=>6}],
# [{:name=>"Mahsam", :rating=>7}, {:name=>"Bilal", :rating=>8},
# {:name=>"Owen", :rating=>15}, {:name=>"Kaka", :rating=>20}]]
Продолжая,
c = b.map { |a| flip.next ? a.reverse : a }
#=> [[{:name=>"Osman", :rating=>6}, {:name=>"Aj", :rating=>3},
# {:name=>"Usama", :rating=>2}, {:name=>"Qasim", :rating=>1}],
# [{:name=>"Mahsam", :rating=>7}, {:name=>"Bilal", :rating=>8},
# {:name=>"Owen", :rating=>15}, {:name=>"Kaka", :rating=>20}]]
c.transpose
#=> [[{:name=>"Osman", :rating=>6}, {:name=>"Mahsam", :rating=>7}],
# [{:name=>"Aj", :rating=>3}, {:name=>"Bilal", :rating=>8}],
# [{:name=>"Usama", :rating=>2}, {:name=>"Owen", :rating=>15}],
# [{:name=>"Qasim", :rating=>1}, {:name=>"Kaka", :rating=>20}]]
Может оказаться желательным преобразовать результаты в массив хэшей.
assign(4, players).map { |a| a.map { |h| [h[:name], h[:rating]] }.to_h }
#=> [{"Osman"=>6, "Mahsam"=>7},
# {"Aj" =>3, "Bilal" =>8},
# {"Usama"=>2, "Owen" =>15},
# {"Qasim"=>1, "Kaka" =>20}]
Так как алгоритм (который я нашел) не идеален, но результат все же приемлемый. В любом случае, ваш ответ является наиболее точным из того, что мне нужно. Спасибо и за подробное объяснение ;-)
Я обновил вопрос. "... Вы имеете в виду, что хотите свести к минимуму разницу между наибольшим и наименьшим? Если да, то вы должны сказать, что..." ==> Да! Это именно то, что я хочу.