Soccer tournament, partitioning games

[troplosti]

I've this very difficult problem which I can't solve so I really need your help. I don't know if this will be a clear explanation because I'm Dutch but I'll try..

I have this tournament which is devided into several poules. Each poule has a user given number of teams (ex: Poule 1: 4 teams, Poule 2: 7 teams, Poule 3: 6 teams). Each poule plays a half competition, which means that they play against eachother 1 time. In a poule of 4 teams this would mean the following:

Round 1 Round 2 Round 3
Team 1 - Team 2 Team 1 - Team 3 Team 1 - Team 4
Team 3 - Team 4 Team 2 - Team 4 Team 2 - Team 3

I can set this up for a poule with 4 teams, but with 5 and higher I can't. I don't see the logics and I don't feel like putting all schematics in and not find any formula.

[DavidHooper]

Hi troplosti.

Your problem is because 5 teams is an odd number. In any round, there will be 1 team left over.

6 teams would be possible. Post back if you need more help.

[Guv]

There might not be a good solution to this problem. If it can be solved trial and error should not take too much time.

With an odd number of teams, some team is idle each round. I have no idea of how to approach this problem analytically. It does not seem to be a lot of work to figure it out by trying various combinations. For example, it did not take long for me to work out the following for 5 teams.

AB CD, E idle.
AC, BE, D idle
AE, BD, C idle
AD, CE, B idle
BC, DE, A idle

Note that there are 10 combinations (5*4 / 2) of five teams. The above uses two each round for 5 rounds, with one team idle each round. I intended to assign pair A with each team in order, and assign the idle teams in reverse order (E, D, C, B, A). I hit a snag in the third round and had to improvise a bit.

There are 15 combinations of 6 teams (6*5 / 2). Using three combinations per round for 5 rounds seems possible. I am too lazy to try to work it out. I suppose that you start by listing the 15 combinations. Next assign A to each of the other teams in order: AB in the first round, AC in the second, AD in the third, et cetera. Then try to assign the second pairing in each round, which leaves no choice for the third pair in the round. If you hit a snag, improvise a bit. Perhaps there is no elegant solution. You might discover that you need 6 or 7 rounds with two teams idle for some rounds.

There are 21 combinations of 7 teams (7*6 / 2). Using three combinations per round for 7 rounds (with one team always idle) seems doable. I would start as indicated above for 5 teams.

If it can be done, I expect it to be a job which a human can do easily, but which is hell to program. Even the human might have trouble as the number of teams increases.

If I had to write a program to handle the above, I think I would try to work it out and supply the program with the pairings. Trying to figure out an analytical algorithm seems like more work that just doing it myself by trial and error.

Now that I think of it, a trial and error algorithm might not be too difficult to program, and probably easier than developing an analytical algorithm.

[transcendental]

This is the c code for doing it the analytical way.
Sorry, source code have no comments.


//This program is trying to solve soccer team combination problem for troplosti.
#include <iostream.h>
#include <stdlib.h>
#include <stdio.h>
//Number of combinations for 4 teams= 4*3/2 = 6
int main()
{
char array[4]={'A','B','C','D'};

for(int cnt=0;cnt<4;++cnt)
{
printf("%c %c\n",array[0],array[1]);
char swap=array[0];
array[0]=array[1];
array[1]=array[2];
array[2]=array[3];
array[3]=swap;
}
for(int cnt=0;cnt<2;++cnt)
{
printf("%c %c\n",array[cnt],array[cnt+2]);
}
system("PAUSE");

return 0;
}


below is the output,
===============
A D
B A
C B
D C
A C
B D

[transcendental]

//This program is trying to solve soccer team combination problem for troplosti
//for 5 teams per group
#include <iostream.h>
#include <stdlib.h>
#include <stdio.h>
//Number of combinations for 5 teams= 5*4/2 = 10

void checkrepeat();


char array[5]={'A','B','C','D','E'};
int endnum=0;
char comb[10][5];

int main()
{

for(int cnt=0;cnt<5;++cnt)
{
sprintf(comb[endnum],"%c %c",array[0],array[1]);
printf("%s\n", comb[endnum]);
++endnum;

char swap=array[0];
array[0]=array[1];
array[1]=array[2];
array[2]=array[3];
array[3]=array[4];
array[4]=swap;
}
for(int cnt=0;cnt<3;++cnt)
{
sprintf(comb[endnum],"%c %c",array[cnt],array[cnt+2]);
printf("%s\n", comb[endnum]);
++endnum;
}
for(int cnt=0;cnt<2;++cnt)
{
sprintf(comb[endnum],"%c %c",array[cnt],array[cnt+3]);
printf("%s\n", comb[endnum]);
++endnum;

}
checkrepeat();
system("PAUSE");

return 0;
}
//=====================================================
//function for checking combination doesn't repeat itself.
void checkrepeat()
{
for(int cnt=0;cnt<10;++cnt)
{
for(int cnt1=0;cnt1<10;++cnt1)
{
if(cnt==cnt1) continue;
if(strcmp(comb[cnt],comb[cnt1])== 0)
printf("Error at %d & %d",cnt, cnt1);
}
}


}


Here's the output,
=============
A B
B C
C D
D E
E A
A C
B D
C E
A D
B E

[transcendental]

//This program is trying to solve soccer team combination problem for troplosti
//for 6 teams per group
#include <iostream.h>
#include <stdlib.h>
#include <stdio.h>

//Number of combinations for 6 teams= 6*5/2 = 15

void checkrepeat();


char array[6]={'A','B','C','D','E','F'};
int endnum=0;
char comb[15][5];

int main()
{

for(int cnt=0;cnt<6;++cnt)
{
sprintf(comb[endnum],"%c %c",array[0],array[1]);
printf("%s\n", comb[endnum]);
++endnum;

char swap=array[0];
array[0]=array[1];
array[1]=array[2];
array[2]=array[3];
array[3]=array[4];
array[4]=array[5];
array[5]=swap;
}
for(int cnt=0;cnt<4;++cnt)
{
sprintf(comb[endnum],"%c %c",array[cnt],array[cnt+2]);
printf("%s\n", comb[endnum]);
++endnum;
}
for(int cnt=0;cnt<3;++cnt)
{
sprintf(comb[endnum],"%c %c",array[cnt],array[cnt+3]);
printf("%s\n", comb[endnum]);
++endnum;

}
for(int cnt=0;cnt<2;++cnt)
{
sprintf(comb[endnum],"%c %c",array[cnt],array[cnt+4]);
printf("%s\n", comb[endnum]);
++endnum;

}
checkrepeat();
system("PAUSE");

return 0;
}
//=====================================================
//function for checking combination doesn't repeat itself.
void checkrepeat()
{
for(int cnt=0;cnt<15;++cnt)
{
for(int cnt1=0;cnt1<15;++cnt1)
{
if(cnt==cnt1) continue;
if(strcmp(comb[cnt],comb[cnt1])== 0)
printf("Error at %d & %d",cnt, cnt1);
}
}


}


Here's the output,
A B
B C
C D
D E
E F
F A
A C
B D
C E
D F
A D
B E
C F
A E
B F

[transcendental]

troplosti, source code have no comments. But u should see the analytical pattern involved. Try to do 7 teams per poule yourself.

U can ignore checkrepeat function when trying to understand the code.

U try to convert the c code to VB code yrself. My VB skills is very rusty.

I will try my best to explain here. I will use 6 teams per poule scenario to explain.

First u must calculate the number of combinations involved, as shown in Guv's post. 6*5/2=15

Then u proceed to do a 6 iterations of loop. 6 is determined by the number of teams involved. Display the teams adjacent to each other in each loop by shifting the teams.

eg, team 0 & team 1, team 1 & team 2, team2 & team3 and so on.

In the second loop, do 4 iterations to display alternate teams. Note 4 is determined by how much u can do before u exceed the boundary of the array.

eg, team 0 & team 2, team 1 & team 3, team 2 & team 4, team 3 & team 5 cannot go on any further, bcos team 5 is the last team, thus can only loop 4 times, remember 1st team start from team 0.

In the third loop, do 3 iterations to display teams which is 2 teams apart.

eg, team 0 & team 3, team1 & team 4 and so on.

In the fourth loop, do 2 iterations to display teams which is 3 teams apart.

eg, team 0 & team 4, team 1 & team 5, Remember 5th is the the last team so cannot loop more than twice.

By now u have done 4 for loops.

1st loop: 6 iterations
2nd loop: 4 iterations
3rd loop: 3 iterations
4th loop: 2 iterations
Total :15 iterations which correspond to 15 combinations for 6 teams per poule.

So no need to do any further looping now.

What u get is the 15 diff combinations u want.;)

[Guv]

Transcendental: Your code merely generates combinations.

The problem is to make pairings for each round of a tournatment.

With 6 teams (15 total combinations), I hope you are not suggesting a 15-day competition with one game each day. Even 15 consecutive games in less than 15 days is not what is required here.

Hopefully, you could have three concurrent games each day for 5 days. Id est: Use up 3 combinations at once.

[transcendental]

Originally posted by Guv
Trying to figure out an analytical algorithm seems like more work that just doing it myself by trial and error.


Yes, it is true.

Pairing for 6 teams(diff colors depict diff days)
=================================
A B
B C
C D
D E
E F
F A
A C
B D
C E
D F
A D
B E
C F
A E
B F

[transcendental]

Actually, I just discovered a simple analytical way to do it. First u have to find all the combinations in a really simple method. I will use 4 teams in a poule as an simple example to illustrate. Then proceed to 7 teams a poule to show that it is really easy to pair the teams in a tournament.

Now, how to find diff combinations(before we can pair)
=======================================

In this example, each team have to face the other 3 teams eventually. Let us have the combination for A.

A B
A C
A D

Let us add in the combinations for team B now. Pls note 1 combo is in the above already.

A B
A C
A D
B C
B D

Let us add in the combinations for team C now. Pls note 2 combo are in the above already.

A B
A C
A D
B C
B D
C D

Part 1:Using the same method to find combo for 7 teams in poule
==============================================
Being a kind person I am, I will do a walkthough with u.

7 teams in a poule: A B C D E F G


A B
A
A
A
A
A
B C
B
B
B
B
C D
C
C
C
D E
D
D
E F
E
F G


Now fill in the 2nd column with alphabets that began after the ones I put in.

A B
A C
A D
A E
A F
A G
B C
B D
B E
B F
B G
C D
C E
C F
C G
D E
D F
D G
E F
E G
F G

U got the 21 diff combo

Part 2: We can do the pairing now!
=========================


Note: I have to use the code tags to keep my alignment intact.
Note: For my own convenience, I will call the 1st column began with the same alphabet, seg or segment. Eg, seg A and seg B.

Do the 6 days, ignore day 7 for now.


day1=A B
day2=A C
day3=A D
day4=A E
day5=A F
day6=A G
B C
B D
B E
B F
B G
C D
C E
C F
C G
D E
D F
D G
E F
E G
F G


For day 1, we had "A B", look for another matching. Since B is in "A B", we need not look in seg B.
Suppose we choose "C D", we still got to look for another match. Since D is in "C D", we need not look in seg D. Let us choose "A B", "C D" and "E F" for day 1.


day1=A B
day2=A C
day3=A D
day4=A E
day5=A F
day6=A G
B C
B D
B E
B F
B G
day1=C D
C E
C F
C G
D E
D F
D G
day1=E F
E G
F G


Do the same for the other days.

Rule of thumb:While doing pairing for each day, do not look in seg for which the found matches already contains the alphabets. Eg,looking the third match for "A E" & "B F", u need not look again in seg A seg B, seg E and seg F, proceed straight to seg C or seg D.

After u have paired for the 6 days, the remaining 3 un-paired matches would be for day 7.


day1=A B
day2=A C
day3=A D
day4=A E
day5=A F
day6=A G
day3=B C
day2=B D
day5=B E
day4=B F
day7=B G
day1=C D
day6=C E
day7=C F
day4=C G
day7=D E
day6=D F
day5=D G
day1=E F
day2=E G
day3=F G



Voila! u have all the pairings.


Day1 Day2 Day3 Day4 Day5 Day6 Day7
==== ==== ==== ==== ==== ==== ====
A B A C A D A E A F A G B G
C D B D B C B F B E C E C F
E F E G F G C G D G D F D E
G F E D C B A

[sql_lall]

I haven't tried this properly yet, but here goes.

Use differences, and modula arithmetic (remainders):
you have n teams.

Loop AVal 1 to n-1
loop BVal from 1 to n-1
match up team BVal with team AVal + BVal, if BVal and BVal + Aval haven't been matched already
next BVal
Next AVAl