Evenly duplicate games to reach a maximum amount p

问题:

I have a round robin tournament where I create all the games necessary (7 games per participant) for 8 teams. I however need 10 games per participant which means I need to duplicate matchups, and on top of that 1 and 5 can't play each other. You can see from the data below the games I generated for each participant (# of games) in the order it was created which would be the round.

I am trying to figure out the best possible way to duplicate the matchups and evently distribute the matchups in such a way that there aren't matchups that duplicate three times and still retain 10 games per participant and having 1 and 5 not play each other. Any suggestions would be helpful how to figure this out. This also needs to be a generic solution where other possibilities still work.

1 (6)
    1 vs 2
    1 vs 3
    1 vs 4
    1 vs 6
    1 vs 7
    1 vs 8
2 (7)
    1 vs 2
    2 vs 4
    2 vs 3
    2 vs 6
    2 vs 5
    2 vs 8
    2 vs 7
3 (7)
    3 vs 4
    1 vs 3
    2 vs 3
    3 vs 7
    3 vs 8
    3 vs 5
    3 vs 6
4 (7)
    3 vs 4
    2 vs 4
    1 vs 4
    4 vs 8
    4 vs 7
    4 vs 6
    4 vs 5
5 (6)
    5 vs 6
    5 vs 7
    5 vs 8
    2 vs 5
    3 vs 5
    4 vs 5
6 (7)
    5 vs 6
    6 vs 8
    6 vs 7
    2 vs 6
    1 vs 6
    4 vs 6
    3 vs 6
7 (7)
    7 vs 8
    5 vs 7
    6 vs 7
    3 vs 7
    4 vs 7
    1 vs 7
    2 vs 7
8 (7)
    7 vs 8
    6 vs 8
    5 vs 8
    4 vs 8
    3 vs 8
    2 vs 8
    1 vs 8

回答1:

First of all, you didn't strictly define what is an "evenly distributed" match up. So I will suggest this means that every pair of teams play either 1 or 2 games. With this restriction I have a solution for your original case and some thoughts on the general case.

Original Case

8 teams, each must play 10 games, team 1 should not play with team 5. Here is the match up matrix:

    1  2  3  4  5  6  7  8
    ----------------------
1 | 0  2  2  1  0  1  2  2
2 | 2  0  1  2  1  2  1  1
3 | 2  1  0  2  2  1  1  1
4 | 1  2  2  0  2  1  1  1
5 | 0  1  2  2  0  2  2  1
6 | 1  2  1  1  2  0  1  2
7 | 2  1  1  1  2  1  0  2
8 | 2  1  1  1  1  2  2  0

And the same matrix with cells colored according to value:

This matrix is symmetric, each row (and each column) sums up to 10, which means total number of games for each team is 10 as required. All values are 1 or 2, except for zeroes on main diagonal (teams do not play with themselves) and on (1, 5) and (5, 1) cells (team 1 and 5 do not play with each other).

General case

I will explain how I constructed the matrix for the original case in a number of steps. These steps may be generalized for several different conditions. But not for all. I do not suggest a solution for the most general case.

1. Start with the matrix where all teams that can play, do play exactly one game. Sum of rows of this matrix is [6 7 7 7 6 7 7 7], where 6 stands in positions 1 and 5.
2. Try to make sum of each row the same. For this, add games between teams 1 and 8, 1 and 7, 5 and 4, 5 and 3, 2 and 6. Sum is now [8 8 8 8 8 8 8 8]. Nice.
3. Try to add two games per team where pairs from the previous item are forbidden. At this step, do it only for the first four teams. Add games between teams 1 and 2, 2 and 4, 4 and 3, 3 and 1. Sum is now [10 10 10 10 8 8 8 8].
4. Repeat previous pattern for the last four teams. Sum is now [10 10 10 10 10 10 10 10]. Each pair of teams (which are allowed to play) plays 1 or 2 games. We're done.

Another idea, that may be helpful. In an evenly distributed match up, number of games between allowed pairs may differ not more than by 1. We may think of it as this: all pairs play N games, and several pairs play N+1 games. I started with all pairs playing 1 game in my solution. And it gives initial sums, which must be corrected by selecting these several pairs playing one additional game. So the general problem might be reformulated as follows: how to place several ones into allowed places of a zero symmetrical matrix so that sum of rows will become equal to a given vector?