时间戳

首页 > 解决方案 > Ruby：将数组划分为 2 个具有最接近平均值的数组

ruby - Ruby：将数组划分为 2 个具有最接近平均值的数组

问题描述

背景：我正在为一个小型多人视频游戏项目开发“匹配系统”。每个球员都有一个从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

标签： rubyaveragematchmaking

解决方案

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

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

将 n 名球员分成两队 n/2 名球员的方法，其中 n! 等于n面。这通常表示为从 n 个项目的集合中选择 n/2 个项目的方法数。

为了获得总秩（因此，平均秩）具有最小绝对差的分区，必须枚举所有 C(n) 个分区。如果 n = 8，如本例所示，C(8) = 70（例如，请参阅此在线计算器）。但是，如果 n = 16，则 C(16) = 12,870 且 C(32) = 601,080,390。这使您了解 n 必须有多小才能执行完整的枚举。

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

  • 将排名最高的元素（“排名 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和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。

推荐阅读