Наборы: учитывая список (учеников), как я могу создать все наборы (команд) с максимумами и минимумами?

Question

Я работаю над некоторыми функциями от имени учителя, которые группируют студентов в команды. С этой целью я ищу помощи в определении эффективного способа создания всех возможных командных комбинаций, которые соответствуют следующим критериям:

1. Все студенты представлены в команде, и каждый студент появляется только один раз
2. Максимальный и минимальный размер команд
3. Максимальное количество команд

Пример ввода:

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

Пример некоторых желаемых выходные данные:

[['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']],
...

Существует множество других предпочтений ученика / учителя, которые будут использоваться для фильтрации результатов позже, но сейчас потребуется некоторая помощь в создании всех возможных комбинаций команд. Я пытался использовать [itertools.combinations] 1 , но я еще не нашел волхвов c, которые бы подходили для моей конкретной ситуации (учитывая моего новичка python и теоретические навыки набора). Я также сталкивался с подобными, «над головой» примерами , которые приближают меня, но не совсем то, что я ищу:

Answer 1

Не самый эффективный метод, но вы можете использовать пример, на который вы ссылались выше Установить разделы в Python или другой предпочтительный метод для генерации всех возможных комбинаций студенческих команд, а затем иметь другой список, в котором вы добавить только команды, которые соответствуют вашим критериям. Пример:

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)

Answer 2

Группировка студентов доказана как NP-сложная проблема. Генерация всех возможных командных комбинаций не вполне осуществима. Из того, что я могу понять, вам нужны все возможные комбинации команд для выбора лучшего, верно? Для этого вам необходим алгоритм оптимизации для оптимизации вашего критерия.

В недавнем исследовании был реализован PSO для классификации учащихся по неизвестному количеству групп от 4 до 6. PSO продемонстрировал улучшенные возможности по сравнению с GA. Я думаю, что все, что вам нужно, - это конкретное c исследование.

Документ: Формирование автоматов c групп учащихся с использованием оптимизации роя частиц для приложений дифференцированного обучения

Возможно, исследователи может провести вас через исследовательский портал: https://www.researchgate.net/publication/338078753

Вы можете найти статью здесь: https://doi.org/10.1002/cae.22191

Надеюсь, я помог !!

Answer 3

Мне кажется, что это проблема перестановок, которую может решить itertools.

from itertools import permutations

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

Это создаст все возможные варианты расположения игроков. Границы команды могут быть обозначены индексом в списке, например, команда 1 - от индекса 0 до 3, команда 2 - 4-6 ... et c.

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')

. и собирая команду, вы сортируете ее так, чтобы все игроки были в одинаковом порядке, а затем вы убедитесь, что это уникальная комбинация. Если это уникальная комбинация, вы сохраняете ее в словаре. Просто идея. Надеюсь, это поможет.