Частный случай этой проблемы у меня есть - найти все комбинации игроков длиной с , которые могут поместиться на n кортах (которые содержат m игроки каждый).
Однако есть дополнительное ограничение: некоторые игроки должны быть включены как минимум на один корт. Пусть они будут "Set_A". Остальные места, доступные на кортах, заполняются игроками в «Set_B».
Пример игрушки с желаемым выводом:
Set_A = {0, 1, 2}
Set_B = {3, 4}
def func(set_a, set_b, courts, court_size):
#insert code here
return answer
>>>func(Set_A, Set_B, 2, 2)
(((0,1),(2,3)),((0,1),(2,4)),((0,2),(1,3)),((0,2),(1,4)),((0,3),(1,2)),((0,4),(1,2)))
В реальном примере может быть 3 корта, каждый из которых рассчитан на 4 игрока. В «Set_A» 10 игроков, а в «Set_B» 12 игроков. Я хочу найти все комбинации, в которые входят все 10 игроков из «Set_A» и ровно 2 из «Set_B».
Следующий код (который я нашел здесь ) достаточен для нахождения всех комбинаций, когда пробелы на корте равны количеству игроков в "Set_A", например, позвонив по номеру list(partitions(range(12), 4)):
def partitions(s, r):
"""
Generate partitions of the iterable `s` into subsets of size `r`.
>>> list(partitions(set(range(4)), 2))
[((0, 1), (2, 3)), ((0, 2), (1, 3)), ((0, 3), (1, 2))]
"""
s = set(s)
assert(len(s) % r == 0)
if len(s) == 0:
yield ()
return
first = next(iter(s))
rest = s.difference((first,))
for c in combinations(rest, r - 1):
first_subset = (first,) + c
for p in partitions(rest.difference(c), r):
yield (first_subset,) + p
Однако для моих целей этого недостаточно.
Другая проблема - это скорость и память. 'partitions (16,4)' занимает ~ 14 секунд при каждом запуске, а 'partitions (20,4)' возвращает MemoryError. Вполне возможно, что комбинаторный взрыв означает, что он просто неразрешим для некоторых ценностей, с которыми я хочу работать. (Тем не менее, я думаю, что в большинстве случаев это будет правдоподобно, особенно если эти вычисления кэшируются для последующего просмотра).