1

I am running a tournament with 16 participants, who will be split into 4 teams of 4 players each.

I intend to map each player name to their average points and then balance teams using average points. If there is a better / easier way to do this than by generating all combinations, please let me know. I am aware that this is a binpacking problem, but I do want to be able to choose between multiple sets of teams, so my goal is not to return only one set.

It is pretty easy to get all possible team combinations:

import itertools
playerList = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]
groups = list(itertools.combinations(playerList, 4))
print(f'Generating {len(groups)} teams...')

Returns "Generating 1820 teams...", which is 16 choose 4, and is expected. The teams generated look like this:

[[1, 2, 3, 4], [1, 2, 3, 5], [1, 2, 3, 6], [1, 2, 3, 7], [1, 2, 3, 8], ...]

My problem is that I need to generate all possible combinations of these teams. This would be 1820 choose 4 = 455,660,782,395 possible combinations, which, from my experience testing, takes a very, very long time to compute. That would return something like this:

[[[1, 2, 3, 4], [1, 2, 3, 5], [1, 2, 3, 6], [1, 2, 3, 7]], [[1, 2, 3, 4], [1, 2, 3, 5], [1, 2, 3, 6], [1, 2, 3, 8], ...]

I am thinking in order to reduce the computation time, I could get rid of duplicates. Practically, no player is going to be on multiple teams, so it makes no sense to repeat 1, 2, and 3 for every team in the first set. I would normally code that using something like this:

allTeams = list(itertools.combinations(groups, 4))
validTeams = []
for i in allTeams:
    if any(val in i[0] for val in i[1]):
        pass
    else:
        validTeams.append(i)

NOTE: I have not run the code block above yet because my computer cannot get past the first line.

This post boils down to two questions:

  1. How can I generate all (1820 choose 4) combinations of these teams without repeating players?
  2. Is this the best way to approach my problem? Would I be better off with a different approach?

I am relatively new to coding so if there are any big misconceptions on my end, please let me know.

martineau
  • 119,623
  • 25
  • 170
  • 301
johnbeatty02
  • 83
  • 7
  • 2
    A function `get_partitions_same_size` from my answer [here](https://stackoverflow.com/questions/71218611/find-all-unordered-partitions-of-a-list-with-a-minimum-number-of-elements/71233372#71233372) can be helpful. I believe that `get_partitions_same_size(list(range(16)), 4, 4)` generals all 2627625 combinations that meet your requirements in around 20 seconds. – hilberts_drinking_problem Apr 26 '22 at 00:34
  • @hilberts_drinking_problem exactly what I needed. Thank you so much. – johnbeatty02 Apr 26 '22 at 01:50

0 Answers0