1

I have a question regarding a scheduling problem, similar to this problem .

I would like to write a program or algorithm to calculate a game schedule for a sports league, but not with two teams per game, rather than with 3 or more teams. The constraints I have here is only that it works, there's no "home" and "away" difference, I only need to find one correct combination of the game tuples. I want to show you what I mean with that with a 9 teams league with 3 teams per game:

(0,1,2),(3,4,5),(6,7,8) - First matchday
(0,1,3),(2,4,6),(5,7,8) - Second matchday
...
(0,7,8),(1,2,3),(4,5,6) - Might be the last, in this case 28th (8 over 2), matchday

the total number of games are (n over k), the total number of matchdays are ((n-1) over (k-1)), where n is the team number and k is the number of teams per game.

Do you have any ideas how to write this program, I already searched the internet but didn't find anything. I also know that for large n, the calculation might need very long, but it would be ok if it takes some days to calculate. Preferred programming language would be python, but I would also accept C, C++ or java.

Any help would be appreciated. Thank you already in advance!

Unnamed1242
  • 13
  • 2

1 Answers1

0

This isn’t too difficult with itertools. To enumerate, we choose a particular competitor to examine (always the minimum in the code below, but that’s an arbitrary selection), iterate over all possible groupings with that competitor, iterate over all possible partitions of the other competitors, and combine them.

import itertools


def partitions(s, k):
    s = set(s)
    assert len(s) % k == 0
    if s:
        x = min(s)
        s.remove(x)
        for c in itertools.combinations(sorted(s), k - 1):
            for p in partitions(s - set(c), k):
                yield [(x,) + c] + p
    else:
        yield []


if __name__ == "__main__":
    for q in partitions(range(9), 3):
        print(q)

Sample output:

[(0, 1, 2), (3, 4, 5), (6, 7, 8)]
[(0, 1, 2), (3, 4, 6), (5, 7, 8)]
[(0, 1, 2), (3, 4, 7), (5, 6, 8)]
[(0, 1, 2), (3, 4, 8), (5, 6, 7)]
[(0, 1, 2), (3, 5, 6), (4, 7, 8)]
[(0, 1, 2), (3, 5, 7), (4, 6, 8)]
[(0, 1, 2), (3, 5, 8), (4, 6, 7)]
[(0, 1, 2), (3, 6, 7), (4, 5, 8)]
[(0, 1, 2), (3, 6, 8), (4, 5, 7)]
[(0, 1, 2), (3, 7, 8), (4, 5, 6)]
[(0, 1, 3), (2, 4, 5), (6, 7, 8)]
[(0, 1, 3), (2, 4, 6), (5, 7, 8)]
[(0, 1, 3), (2, 4, 7), (5, 6, 8)]
[(0, 1, 3), (2, 4, 8), (5, 6, 7)]
[(0, 1, 3), (2, 5, 6), (4, 7, 8)]
[(0, 1, 3), (2, 5, 7), (4, 6, 8)]
[(0, 1, 3), (2, 5, 8), (4, 6, 7)]
[(0, 1, 3), (2, 6, 7), (4, 5, 8)]
[(0, 1, 3), (2, 6, 8), (4, 5, 7)]
[(0, 1, 3), (2, 7, 8), (4, 5, 6)]
[(0, 1, 4), (2, 3, 5), (6, 7, 8)]
[(0, 1, 4), (2, 3, 6), (5, 7, 8)]
[(0, 1, 4), (2, 3, 7), (5, 6, 8)]
[(0, 1, 4), (2, 3, 8), (5, 6, 7)]
[(0, 1, 4), (2, 5, 6), (3, 7, 8)]
[(0, 1, 4), (2, 5, 7), (3, 6, 8)]
[(0, 1, 4), (2, 5, 8), (3, 6, 7)]
[(0, 1, 4), (2, 6, 7), (3, 5, 8)]
[(0, 1, 4), (2, 6, 8), (3, 5, 7)]
[(0, 1, 4), (2, 7, 8), (3, 5, 6)]
[(0, 1, 5), (2, 3, 4), (6, 7, 8)]
[(0, 1, 5), (2, 3, 6), (4, 7, 8)]
[(0, 1, 5), (2, 3, 7), (4, 6, 8)]
[(0, 1, 5), (2, 3, 8), (4, 6, 7)]
[(0, 1, 5), (2, 4, 6), (3, 7, 8)]
[(0, 1, 5), (2, 4, 7), (3, 6, 8)]
[(0, 1, 5), (2, 4, 8), (3, 6, 7)]
[(0, 1, 5), (2, 6, 7), (3, 4, 8)]
[(0, 1, 5), (2, 6, 8), (3, 4, 7)]
[(0, 1, 5), (2, 7, 8), (3, 4, 6)]
[(0, 1, 6), (2, 3, 4), (5, 7, 8)]
[(0, 1, 6), (2, 3, 5), (4, 7, 8)]
[(0, 1, 6), (2, 3, 7), (4, 5, 8)]
[(0, 1, 6), (2, 3, 8), (4, 5, 7)]
[(0, 1, 6), (2, 4, 5), (3, 7, 8)]
[(0, 1, 6), (2, 4, 7), (3, 5, 8)]
[(0, 1, 6), (2, 4, 8), (3, 5, 7)]
[(0, 1, 6), (2, 5, 7), (3, 4, 8)]
[(0, 1, 6), (2, 5, 8), (3, 4, 7)]
[(0, 1, 6), (2, 7, 8), (3, 4, 5)]
[(0, 1, 7), (2, 3, 4), (5, 6, 8)]
[(0, 1, 7), (2, 3, 5), (4, 6, 8)]
[(0, 1, 7), (2, 3, 6), (4, 5, 8)]
[(0, 1, 7), (2, 3, 8), (4, 5, 6)]
[(0, 1, 7), (2, 4, 5), (3, 6, 8)]
[(0, 1, 7), (2, 4, 6), (3, 5, 8)]
[(0, 1, 7), (2, 4, 8), (3, 5, 6)]
[(0, 1, 7), (2, 5, 6), (3, 4, 8)]
[(0, 1, 7), (2, 5, 8), (3, 4, 6)]
[(0, 1, 7), (2, 6, 8), (3, 4, 5)]
[(0, 1, 8), (2, 3, 4), (5, 6, 7)]
[(0, 1, 8), (2, 3, 5), (4, 6, 7)]
[(0, 1, 8), (2, 3, 6), (4, 5, 7)]
[(0, 1, 8), (2, 3, 7), (4, 5, 6)]
[(0, 1, 8), (2, 4, 5), (3, 6, 7)]
[(0, 1, 8), (2, 4, 6), (3, 5, 7)]
[(0, 1, 8), (2, 4, 7), (3, 5, 6)]
[(0, 1, 8), (2, 5, 6), (3, 4, 7)]
[(0, 1, 8), (2, 5, 7), (3, 4, 6)]
[(0, 1, 8), (2, 6, 7), (3, 4, 5)]
[(0, 2, 3), (1, 4, 5), (6, 7, 8)]
[(0, 2, 3), (1, 4, 6), (5, 7, 8)]
[(0, 2, 3), (1, 4, 7), (5, 6, 8)]
[(0, 2, 3), (1, 4, 8), (5, 6, 7)]
[(0, 2, 3), (1, 5, 6), (4, 7, 8)]
[(0, 2, 3), (1, 5, 7), (4, 6, 8)]
[(0, 2, 3), (1, 5, 8), (4, 6, 7)]
[(0, 2, 3), (1, 6, 7), (4, 5, 8)]
[(0, 2, 3), (1, 6, 8), (4, 5, 7)]
[(0, 2, 3), (1, 7, 8), (4, 5, 6)]
[(0, 2, 4), (1, 3, 5), (6, 7, 8)]
[(0, 2, 4), (1, 3, 6), (5, 7, 8)]
[(0, 2, 4), (1, 3, 7), (5, 6, 8)]
[(0, 2, 4), (1, 3, 8), (5, 6, 7)]
[(0, 2, 4), (1, 5, 6), (3, 7, 8)]
[(0, 2, 4), (1, 5, 7), (3, 6, 8)]
[(0, 2, 4), (1, 5, 8), (3, 6, 7)]
[(0, 2, 4), (1, 6, 7), (3, 5, 8)]
[(0, 2, 4), (1, 6, 8), (3, 5, 7)]
[(0, 2, 4), (1, 7, 8), (3, 5, 6)]
[(0, 2, 5), (1, 3, 4), (6, 7, 8)]
[(0, 2, 5), (1, 3, 6), (4, 7, 8)]
[(0, 2, 5), (1, 3, 7), (4, 6, 8)]
[(0, 2, 5), (1, 3, 8), (4, 6, 7)]
[(0, 2, 5), (1, 4, 6), (3, 7, 8)]
[(0, 2, 5), (1, 4, 7), (3, 6, 8)]
[(0, 2, 5), (1, 4, 8), (3, 6, 7)]
[(0, 2, 5), (1, 6, 7), (3, 4, 8)]
[(0, 2, 5), (1, 6, 8), (3, 4, 7)]
[(0, 2, 5), (1, 7, 8), (3, 4, 6)]
[(0, 2, 6), (1, 3, 4), (5, 7, 8)]
[(0, 2, 6), (1, 3, 5), (4, 7, 8)]
[(0, 2, 6), (1, 3, 7), (4, 5, 8)]
[(0, 2, 6), (1, 3, 8), (4, 5, 7)]
[(0, 2, 6), (1, 4, 5), (3, 7, 8)]
[(0, 2, 6), (1, 4, 7), (3, 5, 8)]
[(0, 2, 6), (1, 4, 8), (3, 5, 7)]
[(0, 2, 6), (1, 5, 7), (3, 4, 8)]
[(0, 2, 6), (1, 5, 8), (3, 4, 7)]
[(0, 2, 6), (1, 7, 8), (3, 4, 5)]
[(0, 2, 7), (1, 3, 4), (5, 6, 8)]
[(0, 2, 7), (1, 3, 5), (4, 6, 8)]
[(0, 2, 7), (1, 3, 6), (4, 5, 8)]
[(0, 2, 7), (1, 3, 8), (4, 5, 6)]
[(0, 2, 7), (1, 4, 5), (3, 6, 8)]
[(0, 2, 7), (1, 4, 6), (3, 5, 8)]
[(0, 2, 7), (1, 4, 8), (3, 5, 6)]
[(0, 2, 7), (1, 5, 6), (3, 4, 8)]
[(0, 2, 7), (1, 5, 8), (3, 4, 6)]
[(0, 2, 7), (1, 6, 8), (3, 4, 5)]
[(0, 2, 8), (1, 3, 4), (5, 6, 7)]
[(0, 2, 8), (1, 3, 5), (4, 6, 7)]
[(0, 2, 8), (1, 3, 6), (4, 5, 7)]
[(0, 2, 8), (1, 3, 7), (4, 5, 6)]
[(0, 2, 8), (1, 4, 5), (3, 6, 7)]
[(0, 2, 8), (1, 4, 6), (3, 5, 7)]
[(0, 2, 8), (1, 4, 7), (3, 5, 6)]
[(0, 2, 8), (1, 5, 6), (3, 4, 7)]
[(0, 2, 8), (1, 5, 7), (3, 4, 6)]
[(0, 2, 8), (1, 6, 7), (3, 4, 5)]
[(0, 3, 4), (1, 2, 5), (6, 7, 8)]
[(0, 3, 4), (1, 2, 6), (5, 7, 8)]
[(0, 3, 4), (1, 2, 7), (5, 6, 8)]
[(0, 3, 4), (1, 2, 8), (5, 6, 7)]
[(0, 3, 4), (1, 5, 6), (2, 7, 8)]
[(0, 3, 4), (1, 5, 7), (2, 6, 8)]
[(0, 3, 4), (1, 5, 8), (2, 6, 7)]
[(0, 3, 4), (1, 6, 7), (2, 5, 8)]
[(0, 3, 4), (1, 6, 8), (2, 5, 7)]
[(0, 3, 4), (1, 7, 8), (2, 5, 6)]
[(0, 3, 5), (1, 2, 4), (6, 7, 8)]
[(0, 3, 5), (1, 2, 6), (4, 7, 8)]
[(0, 3, 5), (1, 2, 7), (4, 6, 8)]
[(0, 3, 5), (1, 2, 8), (4, 6, 7)]
[(0, 3, 5), (1, 4, 6), (2, 7, 8)]
[(0, 3, 5), (1, 4, 7), (2, 6, 8)]
[(0, 3, 5), (1, 4, 8), (2, 6, 7)]
[(0, 3, 5), (1, 6, 7), (2, 4, 8)]
[(0, 3, 5), (1, 6, 8), (2, 4, 7)]
[(0, 3, 5), (1, 7, 8), (2, 4, 6)]
[(0, 3, 6), (1, 2, 4), (5, 7, 8)]
[(0, 3, 6), (1, 2, 5), (4, 7, 8)]
[(0, 3, 6), (1, 2, 7), (4, 5, 8)]
[(0, 3, 6), (1, 2, 8), (4, 5, 7)]
[(0, 3, 6), (1, 4, 5), (2, 7, 8)]
[(0, 3, 6), (1, 4, 7), (2, 5, 8)]
[(0, 3, 6), (1, 4, 8), (2, 5, 7)]
[(0, 3, 6), (1, 5, 7), (2, 4, 8)]
[(0, 3, 6), (1, 5, 8), (2, 4, 7)]
[(0, 3, 6), (1, 7, 8), (2, 4, 5)]
[(0, 3, 7), (1, 2, 4), (5, 6, 8)]
[(0, 3, 7), (1, 2, 5), (4, 6, 8)]
[(0, 3, 7), (1, 2, 6), (4, 5, 8)]
[(0, 3, 7), (1, 2, 8), (4, 5, 6)]
[(0, 3, 7), (1, 4, 5), (2, 6, 8)]
[(0, 3, 7), (1, 4, 6), (2, 5, 8)]
[(0, 3, 7), (1, 4, 8), (2, 5, 6)]
[(0, 3, 7), (1, 5, 6), (2, 4, 8)]
[(0, 3, 7), (1, 5, 8), (2, 4, 6)]
[(0, 3, 7), (1, 6, 8), (2, 4, 5)]
[(0, 3, 8), (1, 2, 4), (5, 6, 7)]
[(0, 3, 8), (1, 2, 5), (4, 6, 7)]
[(0, 3, 8), (1, 2, 6), (4, 5, 7)]
[(0, 3, 8), (1, 2, 7), (4, 5, 6)]
[(0, 3, 8), (1, 4, 5), (2, 6, 7)]
[(0, 3, 8), (1, 4, 6), (2, 5, 7)]
[(0, 3, 8), (1, 4, 7), (2, 5, 6)]
[(0, 3, 8), (1, 5, 6), (2, 4, 7)]
[(0, 3, 8), (1, 5, 7), (2, 4, 6)]
[(0, 3, 8), (1, 6, 7), (2, 4, 5)]
[(0, 4, 5), (1, 2, 3), (6, 7, 8)]
[(0, 4, 5), (1, 2, 6), (3, 7, 8)]
[(0, 4, 5), (1, 2, 7), (3, 6, 8)]
[(0, 4, 5), (1, 2, 8), (3, 6, 7)]
[(0, 4, 5), (1, 3, 6), (2, 7, 8)]
[(0, 4, 5), (1, 3, 7), (2, 6, 8)]
[(0, 4, 5), (1, 3, 8), (2, 6, 7)]
[(0, 4, 5), (1, 6, 7), (2, 3, 8)]
[(0, 4, 5), (1, 6, 8), (2, 3, 7)]
[(0, 4, 5), (1, 7, 8), (2, 3, 6)]
[(0, 4, 6), (1, 2, 3), (5, 7, 8)]
[(0, 4, 6), (1, 2, 5), (3, 7, 8)]
[(0, 4, 6), (1, 2, 7), (3, 5, 8)]
[(0, 4, 6), (1, 2, 8), (3, 5, 7)]
[(0, 4, 6), (1, 3, 5), (2, 7, 8)]
[(0, 4, 6), (1, 3, 7), (2, 5, 8)]
[(0, 4, 6), (1, 3, 8), (2, 5, 7)]
[(0, 4, 6), (1, 5, 7), (2, 3, 8)]
[(0, 4, 6), (1, 5, 8), (2, 3, 7)]
[(0, 4, 6), (1, 7, 8), (2, 3, 5)]
[(0, 4, 7), (1, 2, 3), (5, 6, 8)]
[(0, 4, 7), (1, 2, 5), (3, 6, 8)]
[(0, 4, 7), (1, 2, 6), (3, 5, 8)]
[(0, 4, 7), (1, 2, 8), (3, 5, 6)]
[(0, 4, 7), (1, 3, 5), (2, 6, 8)]
[(0, 4, 7), (1, 3, 6), (2, 5, 8)]
[(0, 4, 7), (1, 3, 8), (2, 5, 6)]
[(0, 4, 7), (1, 5, 6), (2, 3, 8)]
[(0, 4, 7), (1, 5, 8), (2, 3, 6)]
[(0, 4, 7), (1, 6, 8), (2, 3, 5)]
[(0, 4, 8), (1, 2, 3), (5, 6, 7)]
[(0, 4, 8), (1, 2, 5), (3, 6, 7)]
[(0, 4, 8), (1, 2, 6), (3, 5, 7)]
[(0, 4, 8), (1, 2, 7), (3, 5, 6)]
[(0, 4, 8), (1, 3, 5), (2, 6, 7)]
[(0, 4, 8), (1, 3, 6), (2, 5, 7)]
[(0, 4, 8), (1, 3, 7), (2, 5, 6)]
[(0, 4, 8), (1, 5, 6), (2, 3, 7)]
[(0, 4, 8), (1, 5, 7), (2, 3, 6)]
[(0, 4, 8), (1, 6, 7), (2, 3, 5)]
[(0, 5, 6), (1, 2, 3), (4, 7, 8)]
[(0, 5, 6), (1, 2, 4), (3, 7, 8)]
[(0, 5, 6), (1, 2, 7), (3, 4, 8)]
[(0, 5, 6), (1, 2, 8), (3, 4, 7)]
[(0, 5, 6), (1, 3, 4), (2, 7, 8)]
[(0, 5, 6), (1, 3, 7), (2, 4, 8)]
[(0, 5, 6), (1, 3, 8), (2, 4, 7)]
[(0, 5, 6), (1, 4, 7), (2, 3, 8)]
[(0, 5, 6), (1, 4, 8), (2, 3, 7)]
[(0, 5, 6), (1, 7, 8), (2, 3, 4)]
[(0, 5, 7), (1, 2, 3), (4, 6, 8)]
[(0, 5, 7), (1, 2, 4), (3, 6, 8)]
[(0, 5, 7), (1, 2, 6), (3, 4, 8)]
[(0, 5, 7), (1, 2, 8), (3, 4, 6)]
[(0, 5, 7), (1, 3, 4), (2, 6, 8)]
[(0, 5, 7), (1, 3, 6), (2, 4, 8)]
[(0, 5, 7), (1, 3, 8), (2, 4, 6)]
[(0, 5, 7), (1, 4, 6), (2, 3, 8)]
[(0, 5, 7), (1, 4, 8), (2, 3, 6)]
[(0, 5, 7), (1, 6, 8), (2, 3, 4)]
[(0, 5, 8), (1, 2, 3), (4, 6, 7)]
[(0, 5, 8), (1, 2, 4), (3, 6, 7)]
[(0, 5, 8), (1, 2, 6), (3, 4, 7)]
[(0, 5, 8), (1, 2, 7), (3, 4, 6)]
[(0, 5, 8), (1, 3, 4), (2, 6, 7)]
[(0, 5, 8), (1, 3, 6), (2, 4, 7)]
[(0, 5, 8), (1, 3, 7), (2, 4, 6)]
[(0, 5, 8), (1, 4, 6), (2, 3, 7)]
[(0, 5, 8), (1, 4, 7), (2, 3, 6)]
[(0, 5, 8), (1, 6, 7), (2, 3, 4)]
[(0, 6, 7), (1, 2, 3), (4, 5, 8)]
[(0, 6, 7), (1, 2, 4), (3, 5, 8)]
[(0, 6, 7), (1, 2, 5), (3, 4, 8)]
[(0, 6, 7), (1, 2, 8), (3, 4, 5)]
[(0, 6, 7), (1, 3, 4), (2, 5, 8)]
[(0, 6, 7), (1, 3, 5), (2, 4, 8)]
[(0, 6, 7), (1, 3, 8), (2, 4, 5)]
[(0, 6, 7), (1, 4, 5), (2, 3, 8)]
[(0, 6, 7), (1, 4, 8), (2, 3, 5)]
[(0, 6, 7), (1, 5, 8), (2, 3, 4)]
[(0, 6, 8), (1, 2, 3), (4, 5, 7)]
[(0, 6, 8), (1, 2, 4), (3, 5, 7)]
[(0, 6, 8), (1, 2, 5), (3, 4, 7)]
[(0, 6, 8), (1, 2, 7), (3, 4, 5)]
[(0, 6, 8), (1, 3, 4), (2, 5, 7)]
[(0, 6, 8), (1, 3, 5), (2, 4, 7)]
[(0, 6, 8), (1, 3, 7), (2, 4, 5)]
[(0, 6, 8), (1, 4, 5), (2, 3, 7)]
[(0, 6, 8), (1, 4, 7), (2, 3, 5)]
[(0, 6, 8), (1, 5, 7), (2, 3, 4)]
[(0, 7, 8), (1, 2, 3), (4, 5, 6)]
[(0, 7, 8), (1, 2, 4), (3, 5, 6)]
[(0, 7, 8), (1, 2, 5), (3, 4, 6)]
[(0, 7, 8), (1, 2, 6), (3, 4, 5)]
[(0, 7, 8), (1, 3, 4), (2, 5, 6)]
[(0, 7, 8), (1, 3, 5), (2, 4, 6)]
[(0, 7, 8), (1, 3, 6), (2, 4, 5)]
[(0, 7, 8), (1, 4, 5), (2, 3, 6)]
[(0, 7, 8), (1, 4, 6), (2, 3, 5)]
[(0, 7, 8), (1, 5, 6), (2, 3, 4)]
David Eisenstat
  • 64,237
  • 7
  • 60
  • 120
  • Ok, so that is the list of all possible groupings for a given competitor, but how do I now find a solution for a game schedule? Because I think this is only a pre-step, right? – Unnamed1242 May 19 '23 at 06:32
  • @Unnamed1242 Oh, I see, is [this](https://stackoverflow.com/questions/25902598/find-unique-compositions-of-k-distinct-element-subsets-for-a-set-of-n-elements/25902878#25902878) what you want? – David Eisenstat May 19 '23 at 13:13
  • 1
    Yes! This is exactly what I was looking for. I didn't know that this has a name. This is gorgeous! Thank you so much for this, I really appreciate it. – Unnamed1242 May 22 '23 at 08:42