Ruby：将数组分成2个数组，取最接近的平均值

Question

背景： 我正在为一个小型多人视频游戏副项目开发 "matchmaking system"。每个球员的排名从 0 到 10，每支球队有 4 名球员。我正在努力寻找一个好的方法来平衡球队，让他们的平均排名尽可能接近，比赛尽可能公平。

我目前的有缺陷的方法是这样的：

def create_teams(players)
    teams = Hash.new{|hash, team| hash[team] = []}

    players.sort_by(&:rank).each_slice(2) do |slice|
        teams[:team1] << slice[0]
        teams[:team2] << slice[1]
    end

    teams
end

如果排名已经非常相似，这会很好地工作，但这不是解决此问题的正确方法。例如，它在这样的情况下失败：

require "ostruct"

class Array
    def avg
        sum.fdiv(size)
    end
end

dummy_players = [9, 5, 5, 3, 3, 3, 2, 0].map{|rank| OpenStruct.new(rank: rank)}

teams = create_teams(dummy_players)
teams.each do |team, players|
    ranks = players.map(&:rank)
    puts "#{team} - ranks: #{ranks.inspect}, avg: #{ranks.avg}"
end

这会导致非常不公平的团队：

team1 - ranks: [0, 3, 3, 5], avg: 2.75
team2 - ranks: [2, 3, 5, 9], avg: 4.75

相反，我希望处于这种情况的团队是这样的：

team1 - ranks: [0, 3, 3, 9], avg: 3.75
team2 - ranks: [2, 3, 5, 5], avg: 3.75

Answer 1

如果有n个玩家，其中n为偶数，则有

C(n) = n!/((n/2)!(n/2)!)

将 n 名玩家分成两队 n/2 名玩家的方法，其中 n！等于 n-facorial。这通常表示为从 n 项集合中选择 n/2 项的方法数。

要获得总排名（因此平均排名）的绝对差异最小的分区，必须枚举所有 C(n) 个分区。如果 n = 8，如本例所示，则 C(8) = 70（例如，参见 this online calculator）。然而，如果 n = 16，则 C(16) = 12,870 和 C(32) = 601,080,390。这让您了解 n 必须多小才能执行完整枚举。

如果 n 太大而无法枚举所有组合，您必须求助于使用 启发式，或用于划分等级数组的主观规则。这里有两种可能性：

将排名最高的元素 ("rank 1") 分配给 A 队，将排名 2 和 3 的元素分配给 B 队，将排名 4 和 5 的元素分配给 A 队，依此类推。
将秩为 1 和 n 的元素分配给团队 A，将秩为 2 和 n-1 的元素分配给团队 B，依此类推。

启发式的问题在于评估它们的有效性。对于这个问题，对于你设计的每一个启发式算法，都有一个等级数组，对于这些等级，启发式算法的性能很糟糕。如果您知道可能的排名数组的范围并且有一种绘制无偏样本的方法，您可以统计地评估启发式。然而，这通常是不可能的。

这是检查所有分区的方法。假设：

ranks = [3, 3, 0, 2, 5, 9, 3, 5]

那么我们可以进行如下计算。

indices = ranks.size.times.to_a
  #=> [0, 1, 2, 3, 4, 5, 6, 7] 
team_a = indices.combination(ranks.size/2).min_by do |combo|
   team_b = indices - combo
   (combo.sum { |i| ranks[i] } - team_b.sum { |i| ranks[i] }).abs
end
  #=> [0, 1, 2, 5]
team_b = indices - team_a
  #=> [3, 4, 6, 7]

参见 Array#combination and Enumerable#min_by。

我们看到A队选手的排名是：

arr = ranks.values_at(*team_a)
  #=> [3, 3, 0, 9]

这些排名的总和是：

arr.sum
  #=> 15

同理，B队：

arr = ranks.values_at(*team_b)
  #=> [2, 5, 3, 5] 
arr.sum
  #=> 15

见Array#values_at。

Ruby：将数组分成2个数组，取最接近的平均值

Ruby: Divide array into 2 arrays with the closest possible average

ruby

average

matchmaking