algorithmmathscheduletournamentsports-league-scheduling-problem

Sports tournament schedule with changing pairs


Lets imagine there are 8 players attending to beach volley event. Matches are played 2 vs 2.

As organiser i want to generate schedule for players with the following rules:

So the schedule would start for example:

round 1 
player1 + player2 vs player3 + player4
player5 + player6 vs player7 + player8

round2
player1 + player3 vs player2 + player5
player4 + player7 vs player6 + player8

round3
player1 + player4 vs player2 + player3
player5 + player8 vs player6 + player7

etc

With the example above lets think about the player1. He has been playing together with players (2,3,4) so he has matches left together with players (5,6,7,8)

He has been playing against:

Player3 (twice)
Player4
Player2 (twice)
Player5

So the remaining 4 matches (for player 1) should be played together with players 5,6,7,8 and the opponents cant be player3 or player2 (as you have played twice against those)

I have seen the great examples here How to automatically generate a sports league schedule and wikipedia article about round robin https://en.wikipedia.org/wiki/Round-robin_tournament (Original construction of pairing tables by Richard Schurig (1886)) works fine for generating the matches, but with that there will be more than two matches against some players.

I really appreciate any help!


Solution

  • Yes, this can be accomplished with the help of the finite field F8. We identify each player with one of the elements of F8. Let t and p be any distinct nonzero elements of F8. In round r for r in F8 ∖ {0} (seven elements), player x has x + r t as a teammate and x + r p and x + r p + r t as opponents.

    Since x + r t + r t = x and x + r p + r t + r t = x + r p in a field of characteristic 2, each player in each round has exactly one teammate, and their two opponents are teammates. For a pair of players x and y, the round in which they are teammates is uniquely determined because the equation x + r t = y (equivalent to x = y + r t) has exactly one solution. Similar reasoning demonstrates why each player opposes each other player in exactly two rounds.

    F8 = {
        (0, 0, 0): "a",
        (1, 0, 0): "b",
        (0, 1, 0): "c",
        (1, 1, 0): "d",
        (0, 0, 1): "e",
        (1, 0, 1): "f",
        (0, 1, 1): "g",
        (1, 1, 1): "h",
    }
    
    
    def f8_times(p, q):
        pq = (
            p[0] & q[0],
            (p[0] & q[1]) ^ (p[1] & q[0]),
            (p[0] & q[2]) ^ (p[1] & q[1]) ^ (p[2] & q[0]),
            (p[1] & q[2]) ^ (p[2] & q[1]),
            p[2] & q[2],
        )
        return (pq[0] ^ pq[3], pq[1] ^ pq[3] ^ pq[4], pq[2] ^ pq[4])
    
    
    for a in F8:
        if any(a):
            print("{}{} vs {}{}; {}{} vs {}{}".format(*(F8[f8_times(a, b)] for b in F8)))
    

    Output:

    ab vs cd; ef vs gh
    ac vs eg; db vs hf
    ad vs gf; he vs bc
    ae vs dh; gc vs fb
    af vs be; ch vs dg
    ag vs hb; fd vs ce
    ah vs fc; bg vs ed