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

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 2

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 3

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