Ruby循环赛调度器开发：球员参赛次数不均问题求助

需求说明 #

开发一款调度器，输入N名球员（最少4人，支持奇偶数量）：

1. 先生成所有两人搭档组合；
2. 将这些组合转化为比赛，每场比赛由两个无重叠球员的两人组合对战；
3. 要求每对搭档仅对战一次，且每位球员的参赛次数完全相同。

两人组合生成示例 #

players = ['A','B','C','D','E']
players.combination(2).to_a
# 输出结果：
# [["A", "B"], ["A", "C"], ["A", "D"], ["A", "E"], ["B", "C"], ["B", "D"], ["B", "E"], ["C", "D"], ["C", "E"], ["D", "E"]]

当前实现的问题 #

伪代码 #

# 选择随机队伍
# 找到与当前队伍无重叠球员的队伍
# 生成这两支队伍的比赛
# 从原数组中删除这两支队伍
# 重复直到数组为空

实现代码 #

def generate_matches(player_combinations)
   matches = []

   while !player_combinations.empty?
        team_1 = player_combinations.shift

        # 筛选与team1无重叠球员的队伍
        filtered_teams = player_combinations.select do |team| 
            (team & team_1).empty? 
        end
        team_2 = filtered_teams.pop

        player_combinations.delete(team_2)
        matches << [team_1, team_2]
    end

    matches
end

问题表现 #

• 比赛数量不足：例如5名球员预期生成5场比赛，但实际可能只生成4场；
• 参赛次数不均衡：部分球员参赛次数少于目标值（目标值为球员数-1），示例：

  实际参赛次数：{"A"=>4, "C"=>3, "B"=>2, "E"=>4, "D"=>3}
  预期参赛次数：{"A"=>4, "C"=>4, "B"=>4, "E"=>4, "D"=>4}
  

• 随机选择逻辑未考虑后续配对可行性，导致部分组合无法被合理匹配。

解决方案：回溯法均衡调度 #

通过回溯算法，优先处理参赛次数较少的球员组合，确保每一步选择都为后续配对保留可行性，最终生成符合要求的均衡调度。

实现代码 #

def generate_balanced_matches(players)
  combinations = players.combination(2).to_a
  target_count = players.size - 1 # 每位球员需参赛的次数
  matches = []

  # 回溯函数：尝试匹配剩余组合，维护球员参赛计数
  backtrack = lambda do |remaining, current_matches, counts|
    return current_matches if remaining.empty?

    # 优先选择当前参赛次数总和最少的组合，避免后续无法配对
    sorted_combinations = remaining.sort_by { |c| counts[c[0]] + counts[c[1]] }
    team1 = sorted_combinations.first

    # 筛选可配对的队伍：无重叠球员，且配对后参赛次数不超目标
    valid_team2s = remaining.select do |team2|
      next if (team1 & team2).any?
      counts[team2[0]] + 1 <= target_count && counts[team2[1]] + 1 <= target_count
    end

    valid_team2s.each do |team2|
      new_remaining = remaining - [team1, team2]
      new_counts = counts.dup
      team1.each { |p| new_counts[p] += 1 }
      team2.each { |p| new_counts[p] += 1 }
      
      result = backtrack.call(new_remaining, current_matches + [[team1, team2]], new_counts)
      return result if result
    end

    nil
  end

  # 初始化计数：所有球员参赛次数为0
  initial_counts = Hash.new(0)
  result = backtrack.call(combinations, matches, initial_counts)
  
  result || raise("无法生成符合要求的均衡比赛调度")
end

# 测试示例
players = ['A','B','C','D','E']
matches = generate_balanced_matches(players)
puts "生成的比赛："
puts matches.inspect

# 验证参赛次数
counts = Hash.new(0)
matches.flatten(1).each { |team| team.each { |p| counts[p] +=1 } }
puts "\n球员参赛次数："
puts counts.inspect

代码说明 #

1. 回溯逻辑：递归尝试所有可能的配对组合，直到所有两人组合都被合理匹配；
2. 优先级排序：每次优先选择参赛次数总和最少的组合，避免部分球员过早耗尽参赛名额；
3. 有效性校验：确保配对的两支队伍无重叠球员，且配对后球员参赛次数不超过目标值；
4. 结果保障：只要存在可行解，就能生成符合要求的均衡调度。

内容的提问来源于stack exchange，提问作者AshkanYadegari