Sets: Given a list (of students), how can I generate all sets (of teams) with maximums and minimums?

Question

I working on some functionality, on behalf of a teacher, that groups students into teams. To this end, I am looking for help to determine an efficient way of generating all possible team combinations that meet the following criteria:

All students are represented in a team, and each student appears only once
Teams have a maximum and minimum size
There are a maximum number of teams

Example inputs:

students=['a','b','c','d','e','f','g','h','i','j']
max_team_size=5
min_team_size=2
max_team_count=4

Example of some desired output:

[['a','b','c','d'],['e','f','g'],['h','i','j']],
[['a','b','c'],['d','e','f','g'],['h','i','j']],
[['a','b','c'],['d','e','f'],['g','h','i','j']],
[['a','b'],['c','d','e'],['f''g','h'],['i','j']],
[['a','b','c','d','e'],['f''g','h','i','j']],
...

There are a bunch of other student/teacher preferences and such that will be used to filter the results later, but for now, need some help generating all possible combinations of teams. I've tried using [itertools.combinations]1, but I haven't yet found the magic that fits my particular situation (given my novice python and set theory skills). I've also come across similar, over-my-head examples, which get me close, but are not quite what I'm after:

Are the teams always in order from the original list, or could you also have `[a, h, i, j]`? — Barmar, Jan 18 '20 at 01:25
Variable and function names should follow the `lower_case_with_underscores` style. Have you managed to break down the problem? Do you have anything to go off of? — AMC, Jan 18 '20 at 01:26
If they can be in any order, there will be too many combinations to list them all. — Barmar, Jan 18 '20 at 01:27
order doesn't matter, but obviously I don't want duplicate results — Jason Newblanc, Jan 18 '20 at 01:46

score 0 · Answer 1 · answered Jan 18 '20 at 02:17

It would seem to me like this is a permutations problem, which itertools can handle.

from itertools import permutations

players = ['a','b','c','d','e','f','g','h','i','j']
allPossibleCombos = permutations(players)

This will generate all the possible arrangements of the players. The team boundaries could be indicated by the index in the list e.g. Team 1 from index 0 to 3, Team 2 is 4 - 6...etc.

TEAM 1                TEAM 2           TEAM 3       
('b', 'h', 'a', 'g', | 'i', 'c', 'e', | 'j', 'f', 'd')

('b', 'h', 'a', 'g', | 'i', 'c', 'f', | 'd', 'e', 'j')

('b', 'h', 'a', 'g', | 'i', 'c', 'f', | 'd', 'j', 'e')

As you work through the list and grab a team, you sort it so all the players are in the same order, then you make sure it's unique combination. If it is a unique combo you store it in a dictionary. Just an idea. I hope this helps.

score 0 · Answer 2 · answered Jan 18 '20 at 02:39

Not the most efficient method, but you could use the example you linked to above Set partitions in Python or another preferred method to generate all possible combinations of student teams, then have another list where you append only the teams that meet your criteria. Example:

def partition(collection):
    # This function was taken from https://stackoverflow.com/questions/19368375/set-partitions-in-python/30134039#30134039
    if len(collection) == 1:
        yield [ collection ]
        return

    first = collection[0]
    for smaller in partition(collection[1:]):
        # insert `first` in each of the subpartition's subsets
        for n, subset in enumerate(smaller):
            yield smaller[:n] + [[ first ] + subset]  + smaller[n+1:]
        # put `first` in its own subset 
        yield [ [ first ] ] + smaller

student_partitions = []
for n, p in enumerate(partition(Students), 1):
    if len(sorted(p)) <= max_team_count:
        sublist_lengths = [len(x) for x in sorted(p)]
        if all((i <= max_team_size and i >= min_team_size) for i in sublist_lengths):
            student_partitions.append(sorted(p))

for sp in student_partitions:
    print(sp)

Thanks! I started moving in this direction, but it seems to be prohibitively inefficient. I'm hoping that someone has a better way. — Jason Newblanc, Jan 18 '20 at 06:17

score 0 · Answer 3 · answered Jan 18 '20 at 10:40

Student grouping is proved to be an NP-hard problem. Generating all possible team combinations is not quite feasible. From what i can understand, you need all possible team combination for choosing the best, right? For that, you need an optimization algorithm to optimize your criterion.

In a recent research, a PSO was implemented to classify students under unknown number of groups of 4 to 6. PSO showed improved capabilities compared to GA. I think that all you need is the specific research.

The paper is: Forming automatic groups of learners using particle swarm optimization for applications of differentiated instruction

Perhaps the researchers could guide you through researchgate: https://www.researchgate.net/publication/338078753

You can find the paper here: https://doi.org/10.1002/cae.22191

I hope I have helped!!

Sets: Given a list (of students), how can I generate all sets (of teams) with maximums and minimums?

3 Answers3