(Algorithm) Find and arrange combination of teams as pairs

Question: We have 4 teams and 3 gamedays. Write the algorithm that each team plays another team every gameday, and by the end of 3 game days, each team should have played one game with every other team.

Resource: http://www.careercup.com/page?pid=algorithm-interview-questions

Question Owner: rockeblaze

ANSWER

Consider teams as 1, 2, 3, and 4.

Store them into integer array.(ex. a[4])

Each day our teams will play different teams.

T1-T2 and T3-T4

T2-T4 and T1-T3

T1-T4 and T2-T3

As you see, we made our matching in three days. But focus that how we do it.

We did it by selecting them as pairs!

We just did combination in mathematics of 4 and 2.

But how we write these combinations in real world?

Answer is simple. While we are writing possible pairs, we check if we wrote this pair before. So, we should do this checking in programming world too.

We can calculate combination of 4 and 2 as 6. It means we have 6 possible pairs. So let's create two dimentional array to hold pairs that we created, so then, we can check if following pairs will be written are suitable. (ex. b[6][2])

Actually we chose next "neighbor" for each number. What I mean is:

1 2 3 4

we choose 1 and 2

1 - 2

Then we jumped into next: 3

1 - 3

Then finally jump to last: 4

1 - 4

Pass to second team: 2

2 - 3

2 - 3

And  third(which is last for algorithm):

3 - 4

Can you get the algorithm? We choose pairs like that, then arrange them so no team will play more than one match on same day.

You can use following pseudocode to choose pairs:

DEFINE and INITIALIZE i to 0.
DEFINE integer j.
DEFINE and INITIALIZE m to 0. //Last index of empty row of column b.
WHILE i is less than ((size of array a) - 1)
ASSIGN (i+1) to j
WHILE j is less than size of array a
STORE a[i] into b[m][0]
STORE a[j] into b[m][1]
INCREASE m by 1
INCREASE j by 1
END WHILE
INCREASE i by 1
END WHILE

After you find the pairs, just you have to do is print them on the screen so no team will play more than one match on same day. You can easily do it by checking array b's first rows.