How do I generate a tournament schedule in Ruby?

Question

I have been searching everywhere, including the Stack Overflow archives, for an answer of how to do this, I tried rolling my own, but have come up short, so I decided I would post my request here.

I need to take an arbitrary (even) number of items in an array and return with item paired with another item in the array. I need the output of the code to be the same as the output example I have included below.

Input:

('A'..'H').to_a

Output:

[[['A','H'], ['B','G'], ['C','F'], ['D','E']],
 [['A','G'], ['B','F'], ['C','E'], ['D','H']],
 [['A','F'], ['B','E'], ['C','D'], ['G','H']],
 [['A','E'], ['B','D'], ['C','H'], ['F','G']],
 [['A','D'], ['B','C'], ['E','G'], ['F','H']],
 [['A','C'], ['B','H'], ['D','G'], ['E','F']],
 [['A','B'], ['C','G'], ['D','F'], ['E','H']]]

Any ideas?

Here's what I have done so far. It's a bit dirty, and it's not returning in the order I need.

items = ('A'..'H').to_a
combinations = []

1.upto(7) do |index|
  curitems = items.dup
  combination = []
  1.upto(items.size / 2) do |i|
    team1 = curitems.delete_at(0)
    team2 = curitems.delete_at(curitems.size - index) || curitems.delete_at(curitems.size - 1)
    combination << [team1, team2]
  end
  combinations << combination
end

pp combinations

The output is close, but not in the right order:

[[["A", "H"], ["B", "G"], ["C", "F"], ["D", "E"]],
 [["A", "G"], ["B", "F"], ["C", "E"], ["D", "H"]],
 [["A", "F"], ["B", "E"], ["C", "D"], ["G", "H"]],
 [["A", "E"], ["B", "D"], ["C", "H"], ["F", "G"]],
 [["A", "D"], ["B", "C"], ["E", "G"], ["F", "H"]],
 [["A", "C"], ["B", "H"], ["D", "E"], ["F", "G"]],
 [["A", "B"], ["C", "G"], ["D", "H"], ["E", "F"]]]

You'll notice that my code gets me two D<->H combinations (last line and second line) and that won't work.

My understanding of the OP's requirements [FM]:

• Given N teams (for example, 8 teams: A..H).
• Create a tournament schedule, consisting of R rounds of play (7 in our example) and G games (28 in our example).
• Where every team plays every other team exactly once.
• Where every team plays once in each round.
• And (the hard part) where the ordering of games within a round works like this:
• The top-ranked team (A) plays the low-ranked team (H) first.
• If a candidate matchup is rejected for violating the no-repeat rule, put the low-ranked team on the "back-burner" and form the other matchups first. Then matchup the back-burner teams using the same rules. (For example: in Round 2, the first candidate matchup, A-H, is rejected as a repeat, so Game 1 will be A-G, and H will sit on the back burner, to be paired with D as the last game in the round).
• When adding teams to the back-burner, add them to the front of that list (i.e., preserve rank ordering on the back-burner as well).
• Note: Round 5 is the tricky one. The first 2 games are straightforward. The 3rd game would then be E-H; however, that creates a scenario where the 4th game would be a repeat (F-G). So the algorithm needs to backtrack, reject the E-H pairing and instead go for E-G in the 3rd game.

Answer 1

You seem want a round-robin schedule. The principle is easy:

If you start with this setup (teams in the upper row playing against the corresponding lower team):

A B C D
H G F E

you set one team as fixed (e.g., A) and rotate the rest (e.g., clockwise):

A H B C     A G H B     A F G H     A E F G    A D E F    A C D E  
G F E D     F E D C     E D C B     D C B H    C B H G    B H G F

Voilà, 7 rounds, and every team plays each other team.

Edit: I changed the enumeration order in this example to reflect your example output, but this only gets the opponents of A right.

Answer 2

Well, I can get your 8-team example right, but I don't know how to generalize the tweak. But maybe this'll get you thinking...

games = (1...teams.size).map do |r|
  t = teams.dup
  (0...(teams.size/2)).map do |_|
    [t.shift,t.delete_at(-(r % t.size + (r >= t.size * 2 ? 1 : 0)))]
  end
end

Answer 3

How about

[*'A'..'H'].permutation(2).to_a
 => [["A", "B"], ["A", "C"], ["A", "D"], ["A", "E"], ["A", "F"], ["A", "G"], ["A", "H"], ["B", "A"], ["B", "C"], ["B", "D"], ["B", "E"], ["B", "F"], ["B", "G"],....

Edit: Just noticed the output is not in your desired format, but maybe it's still useful for somebody else.

Answer 4

I apologize for the Python-ness of this code. With any luck, someone will translate.

def tourney(teams):
    N = len(teams)
    R = N-1 # rounds
    M = N/2 # matches per round
    sched = [[None] * M for i in range(R)]
    played = set()

    def fill(i, t):
        # Replenish t at the start of each round.
        if i % M == 0:
            t = teams[:]

        # Pick out the highest-seeded team left in t.
        topseed = t.pop(min(range(len(t)), key=lambda i: teams.index(t[i])))

        # Try opponents in reverse order until we find a schedule that works.
        for j, opp in reversed(list(enumerate(t))):
            match = topseed, opp
            if match not in played:
                # OK, this is match we haven't played yet. Schedule it.
                sched[i // M][i % M] = match
                played.add(match)

                # Recurse, if there are any more matches to schedule.
                if i + 1 == R * M or fill(i + 1, t[j+1:]+t[:j]):
                    return True  # Success!

                # If we get here, we're backtracking. Unschedule this match.
                played.remove(match)
        return False

    if not fill(0, []):
        raise ValueError("no schedule exists")
    return sched

Answer 5

Here is an implementation in ruby 1.8.6 according to FM's specification giving the correct output for 8 teams (Many thanks to FM for the great work!):

#!/usr/bin/env ruby

require 'pp'
require 'enumerator'

class Array
  # special round robin scheduling
  def schedule
    res, scheduled = [], []
    (length-1).times { dup.distribute(scheduled, []) }
    # convert list of games to list of rounds
    scheduled.each_slice(length/2) {|x| res.push x}
    aux = res.inject {|a, b| a+b}
    raise if aux.uniq.length != aux.length
    res
  end
  # pair the teams in self and backburner and add games to scheduled
  def distribute(scheduled, backburner)
    # we are done if list is empty and back burners can be scheduled
    return true if empty? && backburner.empty?
    return backburner.distribute(scheduled, []) if empty?
    # take best team and remember if back burner list offered alternatives
    best, alternatives = shift, !backburner.empty?
    # try each team starting from the last
    while other = pop do
      # add team to the back burner list if best played it already
      if scheduled.include? [best, other]
        backburner.unshift(other)
        next
      end
      # schedule the game
      scheduled.push [best, other]
      # try if rest can be scheduled
      return true if dup.distribute(scheduled, backburner.dup)
      # if not unschedule game and add other to back burner list
      scheduled.pop
      backburner.unshift(other)
    end
    # no possible opponent was found, so try alternatives from back burners list
    return alternatives && backburner.unshift(best).distribute(scheduled, [])
  end
end

pp %w{ A B C D E F G H }.schedule

__END__

Output:
[[["A", "H"], ["B", "G"], ["C", "F"], ["D", "E"]],
 [["A", "G"], ["B", "F"], ["C", "E"], ["D", "H"]],
 [["A", "F"], ["B", "E"], ["C", "D"], ["G", "H"]],
 [["A", "E"], ["B", "D"], ["C", "H"], ["F", "G"]],
 [["A", "D"], ["B", "C"], ["E", "G"], ["F", "H"]],
 [["A", "C"], ["B", "H"], ["D", "G"], ["E", "F"]],
 [["A", "B"], ["C", "G"], ["D", "F"], ["E", "H"]]]

Answer 6

I finally had time to look at this again. This is a Ruby version of Jason's answer, with a few simplifications and a couple of good ideas from jug's answer.

require 'pp'

def tournament (teams)
    teams.reverse!

    # Hash of hashes to keep track of matchups already used.
    played = Hash[ * teams.map { |t| [t, {}] }.flatten ]

    # Initially generate the tournament as a list of games.
    games = []
    return [] unless set_game(0, games, played, teams, nil)

    # Convert the list into tournament rounds.
    rounds = []
    rounds.push games.slice!(0, teams.size / 2) while games.size > 0
    rounds
end

def set_game (i, games, played, teams, rem)
    # Convenience vars: N of teams and total N of games.
    nt  = teams.size
    ng  = (nt - 1) * nt / 2

    # If we are working on the first game of a round,
    # reset rem (the teams remaining to be scheduled in
    # the round) to the full list of teams.
    rem = Array.new(teams) if i % (nt / 2) == 0

    # Remove the top-seeded team from rem.
    top = rem.sort_by { |tt| teams.index(tt) }.pop
    rem.delete(top)

    # Find the opponent for the top-seeded team.
    rem.each_with_index do |opp, j|
        # If top and opp haven't already been paired, schedule the matchup.
        next if played[top][opp]
        games[i] = [ top, opp ]
        played[top][opp] = true

        # Create a new list of remaining teams, removing opp
        # and putting rejected opponents at the end of the list.
        rem_new = [ rem[j + 1 .. rem.size - 1], rem[0, j] ].compact.flatten

        # Method has succeeded if we have scheduled the last game
        # or if all subsequent calls succeed.
        return true if i + 1 == ng
        return true if set_game(i + 1, games, played, teams, rem_new)

        # The matchup leads down a bad path. Unschedule the game
        # and proceed to the next opponent.
        played[top][opp] = false
    end

    return false
end

pp tournament(ARGV)