Round Robin Tournament Scheduling

Schedules - You must register to Post and Download => Requests => Topic started by: skyywalker on November 16, 2013, 01:57:10 PM

Title: round robin for 24 competitors in groups of 6
Post by: skyywalker on November 16, 2013, 01:57:10 PM

Good evening everybody,

I am trying to work out a competition format for 24 competitors.

They shall compete in a round robin system against each other, in groups of 6

Every competitor shall face all possible combinations of groupings for this.

Initially this would be
(1 2 3 4 5 6)
(7 8 9 10 11 12)
(13 14 15 16 17 18)
(19 20 21 22 23 24)
etc

Then changing the first and keeping the rest, but this could take forever. I have seen systems like that for slot car racing, but have not found a algorithm for it (or a website or software) that helps me to create the schedule.

Ideally competitors from the last heat in a flight would not compete in the first heat of the second flight, i.e. in the above example preferably numbers 19-24 would not be seeded into the next heat.

Any hints where I could dig ?

Thanks
Markus

Title: Re: round robin for 24 competitors in groups of 6
Post by: Ian Wakeling on November 17, 2013, 01:26:58 AM

If I have understood correctly, there is no solution to this problem. To see this think about the first heat in flight 2.  Start by taking one competitor per heat from the first flight to get something like (1 7 13 19 ? ?), but then there is no way to fill the last two slots that does not duplicate pairs of competitors from the first flight.   The last-heat-in-a-flight constraint will make things even worse.

It is possible to have 23 flights, with all pairs of competitors together in a heat exactly five times, but I guess this in not what you are looking for.

To have any chance of playing a single round robin in this format, the number of heats in a flight must be greater than or equal to the number of competitors in a heat.  See Ed Pegg's page (http://www.mathpuzzle.com/MAA/54-Golf%20Tournaments/mathgames_08_14_07.html) which discusses group sizes between 2 and 4. Take heed of Ed's final sentence, as mathematics wins over algorithms for many of these problems.

On this site, there is a VBA implementation of an algorithm that you could adapt, but currently it only considers three competitors per group.

Title: Re: round robin for 24 competitors in groups of 6
Post by: skyywalker on November 17, 2013, 11:06:29 AM

I am not 100% sure if I understand that correctly, in the second flight I could mix heats 1 and 2, and 3 and 4 so that should be fine. Not sure how it looks further down the road.

I have found one proposal for 18 boats in heats of 6, with a total of 36 heats (12 flights times 3), one of the main problems I have is that I need to adopt that to the actual number of competitors turning up to a competition on the morning of the first day, therefore looking for software options. Will have a look at the recommended pages and also see if I can tweek the VBA approach.

Thanks so far !
Markus

Title: Re: round robin for 24 competitors in groups of 6
Post by: Ian Wakeling on November 19, 2013, 03:46:22 AM

I was thinking that any given pair of competitors were to be in a heat together no more than once, but I see now that you wish them to oppose more than once.   I could probably come close to making a schedule for 12 flights and 24 competitors (48 heats) where pairs meet either 2 or 3 times, if that would help.

Title: Re: round robin for 24 competitors in groups of 6
Post by: skyywalker on November 25, 2013, 11:03:49 PM

Hi Ian,

that would indeed help a lot. They obviously can meet several times as long as we get a good mix of "everybody against everybody in various combinations".

Is there any algorithm that could be used i.e. if there are only 20 or 16 competitors (or any other even number) depending on number of entry ? Assigning byes woud be difficult as then in some heat there might be only 3 people.

Or would the best way be to do something for any even number starting with i.e. 10 and then up to 24 ?

Thanks for your help !

Cheers,
Markus

Title: Re: round robin for 24 competitors in groups of 6
Post by: Ian Wakeling on November 26, 2013, 04:43:31 AM

Here is the 24 competitor schedule.

  ( 4 22  2 12  6 18) (20  3  8  1 17  9) ( 5 13 15 23 16 19) (24 10 11 21  7 14)
  ( 5 23  3 10  4 16) (21  1  9  2 18  7) ( 6 14 13 24 17 20) (22 11 12 19  8 15)
  ( 6 24  1 11  5 17) (19  2  7  3 16  8) ( 4 15 14 22 18 21) (23 12 10 20  9 13)
  (17 11 19 12 20 18) (10  5 15  2  7  6) (22  9 13  3 14 16) ( 8 23 24  4 21  1)
  (18 12 20 10 21 16) (11  6 13  3  8  4) (23  7 14  1 15 17) ( 9 24 22  5 19  2)
  (16 10 21 11 19 17) (12  4 14  1  9  5) (24  8 15  2 13 18) ( 7 22 23  6 20  3)
  ( 1 13 21 15  6 16) (23 17 22  5 18  8) ( 9 10  3 14 11  2) ( 4 19 24 20 12  7)
  ( 2 14 19 13  4 17) (24 18 23  6 16  9) ( 7 11  1 15 12  3) ( 5 20 22 21 10  8)
  ( 3 15 20 14  5 18) (22 16 24  4 17  7) ( 8 12  2 13 10  1) ( 6 21 23 19 11  9)
  ( 5 14 12  8 16  6) (15 23 11 20  2  4) ( 1  3 24 18 10 19) (21 13  7  9 17 22)
  ( 6 15 10  9 17  4) (13 24 12 21  3  5) ( 2  1 22 16 11 20) (19 14  8  7 18 23)
  ( 4 13 11  7 18  5) (14 22 10 19  1  6) ( 3  2 23 17 12 21) (20 15  9  8 16 24)

There is no easy algorithm that is going to solve the general case.  But perhaps if you tried assigning each round at random and then exchanging pairs of competitors between groups to improve the pairwise balance, this would give you a reasonable schedule.  

Title: Re: round robin for 24 competitors in groups of 6
Post by: skyywalker on November 26, 2013, 09:47:34 AM

Great - cool stuff ! Wondering how you work the pairing out... have to dig deeper on the basics I guess to see how to do that for any given even number...

Thanks again and if you have some sources to read to work it out for me that would be highly appreciated as well

Cheers,
Markus

Title: Re: round robin for 24 competitors in groups of 6
Post by: skyywalker on December 19, 2013, 10:13:37 AM

Hi Ian,

that round robin for 24 helped a lot - now I need to add round robin options for 10, 15, 20 and 25 competitors, competing in heats of 5, with the same principle - more or less everybody competing in all sort of combinations...

can you help ?

Thanks !
Markus

Title: Re: round robin for 24 competitors in groups of 6
Post by: Ian Wakeling on December 20, 2013, 05:23:53 AM

Hi Markus,

25 is easy, just use the schedule here and everyone competes against all others exactly once.  Use two copies of this with different random assignments of the letters to the 25 competitors if you need 12 rounds.

Can you say something about the number of rounds you are looking for.  Perfect solutions for:

10 competitors & 18 rounds
15 competitors & 21 rounds
20 competitors & 19 rounds

all exist, but I am thinking these might be too large.

Ian.

Title: Re: round robin for 24 competitors in groups of 6
Post by: skyywalker on December 20, 2013, 07:06:00 AM

Hi Ian,

number of rounds actually does not matter, obviously the shorter the better and then there can be a new assignment and do it again.

key is that we achieve as many as possible combinations of players to play against each other in different setups, which of course may include that they meet more than once.

Cheers,
Markus

Title: Re: round robin for 24 competitors in groups of 6
Post by: Ian Wakeling on December 28, 2013, 04:04:20 AM

Markus,

It's not as simple as you are thinking.  If everyone is to compete with each other the same number of times, then the number of rounds I have specified above is the minimum possible number of rounds that you need to achieve this, for example with 10 competitors and 18 rounds, everyone competes with each other exactly 8 times (see schedule below).  Anything less than this must be unbalanced, and if you then want to 'do it again', it makes the scheduling problem harder in the sense that any new rounds added need to be designed to compensate for the unbalance in the first block of rounds - this is the reason why I was asking to know the total number of rounds beforehand.  I can provide the 15 competitor (21 rounds) and 20 competitor (19 rounds) schedules if they will be useful to you.

Ian.

r1 (3 5 7 10 9)  (1 2 4 6 8)
r2 (5 9 1 7 4)  (3 8 10 2 6)
r3 (8 7 3 1 5)  (2 10 6 4 9)
r4 (4 10 2 5 8)  (1 6 9 7 3)
r5 (5 6 10 7 2)  (9 3 8 4 1)
r6 (9 7 6 8 10)  (4 1 3 5 2)
r7 (10 8 1 3 6)  (4 7 5 9 2)
r8 (1 2 7 8 4)  (3 6 9 10 5)
r9 (9 8 5 4 6)  (7 2 10 3 1)
r10 (3 10 4 2 7)  (6 9 5 1 8)
r11 (4 1 10 6 5)  (2 9 8 7 3)
r12 (7 9 6 2 1)  (8 3 4 5 10)
r13 (6 4 8 3 7)  (2 5 1 9 10)
r14 (6 3 2 4 9)  (5 8 1 10 7)
r15 (8 2 9 5 3)  (10 6 7 1 4)
r16 (2 3 5 6 1)  (10 4 7 8 9)
r17 (10 1 8 9 2)  (5 7 6 3 4)
r18 (1 4 3 9 10)  (7 5 2 8 6)

Title: Re: round robin for 24 competitors in groups of 6
Post by: skyywalker on December 28, 2013, 08:29:38 AM

Hi Ian,

sorry might have been a misunderstanding - 18 rounds is actually not much in that sense as one match is only 5 minutes, so we can run through that easily.

It would be extremely helpful if you could provide the schedules for 15 and 20 competitors.

Thanks a lot and happy holidays !

Markus

Title: Re: round robin for 24 competitors in groups of 6
Post by: Ian Wakeling on December 29, 2013, 05:16:29 AM

Here are the other two schedules.  The three schedules also have some positional balance, so if a heat is (a b c d e), then each competitor will be spread as evenly as possible over the 5 positions a to e, this may be of some use if there is a specific starting order for each heat, or competitors are assigned lanes.

15 competitors, 21 rounds, players compete with each other 6 times each.

r1 (15 11 10 4 14)  (2 13 12 7 8)  (9 3 1 6 5)
r2 (12 5 14 10 6)  (4 1 9 13 7)  (8 3 11 15 2)
r3 (4 8 11 14 1)  (5 9 12 3 13)  (6 7 10 2 15)
r4 (13 6 15 12 11)  (14 5 2 4 10)  (7 1 3 9 8)
r5 (13 10 8 6 3)  (1 11 4 7 2)  (14 9 5 12 15)
r6 (10 14 13 8 2)  (6 4 3 12 9)  (7 15 1 5 11)
r7 (14 13 3 1 7)  (11 6 4 9 10)  (2 12 8 15 5)
r8 (9 6 2 3 15)  (12 14 10 1 13)  (11 5 7 4 8)
r9 (5 12 3 8 4)  (10 11 9 2 14)  (15 6 1 7 13)
r10 (3 2 9 14 7)  (6 13 4 11 8)  (5 1 15 10 12)
r11 (1 14 2 6 12)  (4 15 7 3 10)  (5 8 13 9 11)
r12 (11 7 14 12 6)  (3 4 5 15 13)  (1 8 2 10 9)
r13 (6 9 7 8 14)  (11 10 13 5 3)  (15 4 12 1 2)
r14 (12 8 9 10 7)  (14 15 3 4 6)  (1 2 5 13 11)
r15 (13 7 6 14 5)  (9 4 15 8 10)  (3 12 11 2 1)
r16 (8 3 14 1 15)  (2 11 5 6 9)  (7 12 10 13 4)
r17 (2 7 6 5 4)  (13 1 10 15 9)  (8 12 14 11 3)
r18 (12 4 6 8 1)  (9 15 11 13 14)  (10 5 7 3 2)
r19 (7 15 12 9 11)  (13 2 4 14 3)  (6 10 8 5 1)
r20 (10 3 6 11 1)  (15 14 8 7 5)  (4 2 13 9 12)
r21 (5 9 1 14 4)  (8 13 15 2 6)  (3 10 7 11 12)

20 competitors, 19 rounds, players compete with each other 4 times each.

r1 (1 18 2 20 5)  (7 11 15 17 8)  (4 14 13 16 3)  (19 9 12 6 10)
r2 (11 6 20 18 16)  (19 2 17 14 9)  (10 8 4 3 1)  (12 7 5 15 13)
r3 (14 20 8 5 11)  (18 3 17 2 15)  (10 4 6 13 9)  (7 12 1 16 19)
r4 (14 19 18 13 20)  (9 6 7 17 11)  (12 15 8 1 4)  (16 10 5 2 3)
r5 (4 2 14 8 9)  (20 15 13 11 10)  (16 12 17 19 3)  (5 7 18 1 6)
r6 (14 1 17 15 20)  (8 16 2 11 18)  (6 4 19 12 13)  (9 7 10 3 5)
r7 (2 18 7 4 1)  (3 8 15 10 12)  (19 6 11 14 5)  (17 20 16 9 13)
r8 (9 4 15 5 20)  (17 1 19 7 3)  (6 16 2 11 12)  (14 10 13 8 18)
r9 (13 15 1 19 11)  (18 17 12 4 20)  (5 3 6 8 14)  (2 9 10 7 16)
r10 (2 5 6 1 4)  (17 16 10 14 15)  (7 8 13 18 19)  (11 20 9 3 12)
r11 (20 14 3 4 7)  (15 11 19 10 2)  (6 12 16 18 8)  (17 5 9 1 13)
r12 (10 1 14 17 6)  (11 8 3 19 5)  (16 4 9 15 18)  (20 13 7 2 12)
r13 (5 17 4 12 11)  (15 3 20 6 2)  (13 1 9 16 8)  (18 10 19 14 7)
r14 (15 19 16 5 4)  (3 14 18 12 9)  (8 17 7 20 6)  (1 10 11 13 2)
r15 (3 11 4 13 7)  (8 9 20 2 19)  (18 5 12 10 17)  (1 15 16 6 14)
r16 (6 19 20 4 10)  (16 13 5 8 17)  (12 2 14 7 15)  (3 9 18 11 1)
r17 (4 16 11 7 14)  (1 12 8 20 10)  (13 3 2 6 17)  (5 18 15 9 19)
r18 (20 19 1 3 16)  (15 7 6 9 8)  (11 17 10 18 4)  (2 13 12 5 14)
r19 (12 14 11 9 1)  (13 6 3 15 18)  (8 2 4 19 17)  (10 20 5 16 7)