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:
- each player plays together with everyone (7 matches for each player)
- each player plays twice against each player
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!
CodePudding user response:
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