Группа людей хочет сыграть в несколько игр вместе.
Матчи состоят из 2 команд, в каждой команде по 2 игрока, в общей сложности 4 уникальных игрока за матч.
Каждый хочет быть в команде со всеми остальными ровно один раз.
Каковы все комбинации уникальных матчей для N игроков, где каждая команда играет вместе только один раз?
Например, с игроками A, B, C и D. (N = 4)
Уникальными командами будут AB, A C, AD, B C, BD, CD.
Матчи могут быть AB + CD, AC + BD, AD + B C
Количество команд, указанное N игроками, может быть представлено суммой серии
(N-1)+(N-2)+(N-2)...(1) or (N-1)*(N)/2
Общее количество возможных матчей будет
* 1016. *
И общее количество неуникальных решений будет
(num_possible_matches choose num_teams/2)
or
((N choose 4) * ((4 choose 2) / 2)) choose ((N-1)*(N)/2)
Общее количество уникальных решений, в которых каждая команда используется только один раз. намного меньше, чем число неуникальных решений.
Уникальные команды просты для вычисления
N = 5
people = [chr(i) for i in range(65,65+N)] # ['A', 'B', 'C', 'D', 'E']
teams = []
for i, person_one in enumerate(people):
for person_two in people[i+1:]:
teams.append((person_one, person_two))
# teams
# [('A', 'B'), ('A', 'C'), ('A', 'D'), ('A', 'E'), ('B', 'C'), ('B', 'D'), ('B', 'E'), ('C', 'D'), ('C', 'E'), ('D', 'E')]
Уникальные матчи также довольно просты
matches = []
for i, team1 in enumerate(teams):
for team2 in teams[i:]:
if len(set(team1).intersection(team2)) == 0:
matches.append(((team1), (team2)))
# matches
# [(('A', 'B'), ('C', 'D')),
# (('A', 'B'), ('C', 'E')),
# (('A', 'B'), ('D', 'E')),
# (('A', 'C'), ('B', 'D')),
# (('A', 'C'), ('B', 'E')),
# (('A', 'C'), ('D', 'E')),
# (('A', 'D'), ('B', 'C')),
# (('A', 'D'), ('B', 'E')),
# (('A', 'D'), ('C', 'E')),
# (('A', 'E'), ('B', 'C')),
# (('A', 'E'), ('B', 'D')),
# (('A', 'E'), ('C', 'D')),
# (('B', 'C'), ('D', 'E')),
# (('B', 'D'), ('C', 'E')),
# (('B', 'E'), ('C', 'D'))]
Но общее количество неуникальных решений растет очень быстро по мере увеличения числа игроков N, так что это не так можно найти все из них, а затем отфильтровать список на предмет допустимых комбинаций.
Мой первоначальный подход заключался в создании графика, представляющего все возможные совпадения, с использованием команды
matches_graph
for team in teams:
matches_graph[team] = []
for matched_team in teams:
if len(set(team).intersection(matched_team)) == 0:
matches_graph[team].append(matched_team)
# matches_graph
# {('A', 'B'): [('C', 'D'), ('C', 'E'), ('D', 'E')],
# ('A', 'C'): [('B', 'D'), ('B', 'E'), ('D', 'E')],
# ('A', 'D'): [('B', 'C'), ('B', 'E'), ('C', 'E')],
# ('A', 'E'): [('B', 'C'), ('B', 'D'), ('C', 'D')],
# ('B', 'C'): [('A', 'D'), ('A', 'E'), ('D', 'E')],
# ('B', 'D'): [('A', 'C'), ('A', 'E'), ('C', 'E')],
# ('B', 'E'): [('A', 'C'), ('A', 'D'), ('C', 'D')],
# ('C', 'D'): [('A', 'B'), ('A', 'E'), ('B', 'E')],
# ('C', 'E'): [('A', 'B'), ('A', 'D'), ('B', 'D')],
# ('D', 'E'): [('A', 'B'), ('A', 'C'), ('B', 'C')]}
. Я думал, что Я мог пройтись по графику, выбирая совпадения по одному и отмечая посещенные узлы, и использовать это для создания дерева всех наборов совпадений, где каждая команда использовалась только один раз. Затем я мог бы обрезать короткие и повторяющиеся ветви из дерева и в итоге получить мой окончательный набор решений.
К сожалению, этот подход не очень эффективен с точки зрения сложности пространства, поэтому у меня не хватает памяти для вычисления расширенного дерева, пример кода ниже
def next_teams(visited=[]):
to_return = []
for team in matches_graph:
if team not in visited:
to_return.append(next_matches(team, visited+[team]))
return to_return
def next_matches(choice, visited):
to_return = []
for team in matches_graph[choice]:
if team not in visited:
to_return.append([choice, [[team, next_teams(visited + [team])]]])
return to_return
expanded_tree = next_teams()
# Gives us a list of trees in the format:
# tree = [value, [tree, tree, ...]]
Есть ли лучший способ вычислить набор комбинаций матчей, чтобы матч состоял из 4 уникальных игроков, и в наборе было (N-1)*(N)/4 комбинаций уникальных матчей?