Round-Robin Matching Teams (Darts)

[DaveC426913]

TL;DR Summary

Looking for an algorithm to have every team play every other team.

It's been two years - long enough that the last thread I started about this appears to have gone off to that Great Recycle Bin in the Sky.

I have eight teams of darts players and 18 weeks of dart nights. I'm looking for an algorithm that ensures - not only that every teams plays each other - but that they play as many other teams as possible before coming back around to the original. Pretty sure that'll loop though every combination in 8 weeks, and then I'll just repeat the pattern one-point-two-five more times.

I'm trying various calculators online but so far no joy.

 

[DaveC426913]

Ah! Found what I was looking for.

This calculator: produced results* that ensured that - not only does every team play every other - but they circulate through the four available boards. It even fairly decides which team gets the first throw, (tough we don't do that - we diddle** for that privilege).

The gamut is reached after a mere seven nights, but this year, we will be playing for 18 weeks, meaning I start the loop again twice.

* ^{You can just skip past the sign-up plea by clicking the 'Not Now' button}

** ^{Not nearly as fun as it sounds.}

 

[Mark44]

I'm not sure what the calculator does, but calculating the number of matchups of N teams is fairly straightforward. With N teams there will be $(N - 1) + (N - 2) + \dots + 3 + 2 + 1$ pairings, where no team plays itself (duh!). If this is hard to follow,
team 1 should play teams 2 thru N (N - 1 matches)
team 2 should play teams 3 thru N (N - 2 matches)
team 3 should play teams 4 thru N (N - 3 matches)
...
team N - 2 should play teams N - 1 and N (2 matches)
team N - 1 should play team N (1 match)
All together, the number of matches is as I showed above.

Symbolically, this is $$\sum_{k= 1}^{N - 1} k= \frac{(N -1)N}2$$
For example, if there are N = 5 teams, there are $\frac{4 \cdot 5}2 = 10$ matches. For your example, with N = 8 teams, there should be $\frac{7 \cdot 8}2 = 28$ matches.

Depending on how many matches can be played each night, you can figure out how long it will take for each team to play each other team -- one complete cycle.

 

[mfb]

With four boards every team plays every night, so you don't even need to sum anything - a team has seven different opponents so it will take 7 days to play against everyone else.

With 8 teams it's possible to find match-ups by hand using symmetries:
Make round-robins within 1-4 and 5-8 separately:
1-2, 3-4, 5-6, 7-8
1-3, 2-4, 5-7, 6-8
1-4, 2-3, 5-8, 6-7
Now mix:
1-5, 2-6, 3-7, 4-8
1-6, 2-7, 3-8, 4-5
1-7, 2-8, 3-5, 4-6
1-8, 2-5, 3-6, 4-7
To mix up play more it's advisable to shuffle these 7 days.

 

[DaveC426913]

To mix up play more it's advisable to shuffle these 7 days.

This is a case where one doesn't want more mixing. Because, essentially, more mixing means ... less mixing.

As it stands, every pair is a maximal distance (in time) from the next instance of that pair. Any shuffling will inevitably reduce the distance (in time) between certain teams playing each other again. (Resulting in players saying "Didn't we just play these guys, like, week before last?")

 

[DaveC426913]

Depending on how many matches can be played each night, you can figure out how long it will take for each team to play each other team -- one complete cycle.

As stated:

The gamut is reached after a mere seven nights.

For my parameters, the calculator only spits out seven nights of play, indicating it's covered all the combinations.

 

[PeroK]

This is a case where one doesn't want more mixing. Because, essentially, more mixing means ... less mixing.

As it stands, every pair is a maximal distance (in time) from the next instance of that pair. Any shuffling will inevitably reduce the distance (in time) between certain teams playing each other again. (Resulting in players saying "Didn't we just play these guys, like, week before last?")

That certainly doesn't happen with @mfb's system. Every team plays every other once before restarting the entire cycle.

 

[pbuk]

Yes it is trivial to construct a round robin where the only requirement is every team plays every other team exactly once.

It becomes harder when you take the advantage of throwing first into account - or are you doing middle for diddle?

 

[willem2]

The schedula can be computed with a 3 character expression

# t is team number from 0 up to 7
# w is week number from 1 up to 7 
# function returns the other team number

def other_team(t, w):
    return t^w

 

[Office_Shredder]

I assume you're supposed to do this mod 8? I think team 0 is always scheduled to play themselves. I'm also pretty sure you can only do something like this if the number of players is one less than a prime, and you assign them numbers 1 through p-1.

Edit: no, $1^k$ is always equal to 1 anyway, so I think this just doesn't work.

 

[pbuk]

I assume you're supposed to do this mod 8? I think team 0 is always scheduled to play themselves. I'm also pretty sure you can only do something like this if the number of players is one less than a prime, and you assign them numbers 1 through p-1.

Edit: no, $1^k$ is always equal to 1 anyway, so I think this just doesn't work.

In Python the ^ operator is xor, not exponentiation. I haven't checked willem2's code.

 

[Office_Shredder]

In Python the ^ operator is xor, not exponentiation. I haven't checked willem2's code.

Oh, that's clever. I think this works. Each week you pick a different set of bits to flip, so you don't match the same team twice. And if you xor with the same thing twice you get back to the original set of bits, so you have created valid pairings.

 

[DaveC426913]

Yes it is trivial to construct a round robin where the only requirement is every team plays every other team exactly once.

It becomes harder when you take the advantage of throwing first into account - or are you doing middle for diddle?

:

It even fairly decides which team gets the first throw, (though we don't do that - we diddle for that privilege).

 

[mfb]

This is a case where one doesn't want more mixing. Because, essentially, more mixing means ... less mixing.

As it stands, every pair is a maximal distance (in time) from the next instance of that pair. Any shuffling will inevitably reduce the distance (in time) between certain teams playing each other again. (Resulting in players saying "Didn't we just play these guys, like, week before last?")

You shuffle the set of 7 pairings I posted once and then you use that resulting list every 7 weeks. The distance between having the same opponent is always 7 weeks no matter which order of the 7 pairings you use.
Shuffling the list I posted goes beyond that basic requirement (which is always fulfilled). It helps that not just every team individually, but also pairs of teams (playing against each other) have a larger set of opponents in the week before/afterwards.

 

[pbuk]

It helps that not just every team individually, but also pairs of teams (playing against each other) have a larger set of opponents in the week before/afterwards.

Yes, to give an example the original pairings for the first three weeks were:

1-2, 3-4, 5-6, 7-8
1-3, 2-4, 5-7, 6-8
1-4, 2-3, 5-8, 6-7

After three weeks, none of teams {1, 2, 3, 4} has played against any of teams {5, 6, 7, 8} - there has in fact been been two separate 4-way round robins. If instead you swap weeks 2 and 3 for weeks 4 and 5 in the original list you get instead:

1-2, 3-4, 5-6, 7-8
1-5, 2-6, 3-7, 4-8
1-6, 2-7, 3-8, 4-5

... which is better mixed. To optimise this as fully as possible you need to define a metric for 'mixing distance': some published lists of round robin pairings for e.g. match racing in yachts where there are additional constraints.

 

[DaveC426913]

This is the pattern I settled on:

     1     8     15    22    29    5    12
A   1,8   2,5   5,7   4,6   7,8   1,3   4,7
B   2,7   6,8   2,3   1,5   1,4   6,7   3,8
C   3,6   1,7   4,8   2,8   3,5   2,4   5,6
D   4,5   3,4   1,6   3,7   2,6   5,8   1,2