Вам нужно, чтобы количество людей было кратным 4 от 16, если вы хотите пройти более одного раунда без повторного объединения.
Например, если у вас есть игроки 1, 2, 3, 4 на первом столе (независимо от того, как вы организовываете другие столы), для вашего второго раунда потребуется как минимум 4 стола (по одному для каждого из 4 игроков) чтобы эти четверо не сидели за одним столом. Вам нужно 16 человек, чтобы заполнить эти четыре таблицы. Эти 16 человек должны позволить вам пройти 5 раундов без повторного соединения. Учитывая, что игроки 1, 2, 3 и 4 больше никогда не встретятся, каждый из них будет монополизировать один стол до конца раундов. В этот момент у каждого из них есть еще 12 человек, с которыми можно сыграть, и, если вы будете отлично их смешивать, это будет 3 человека за раунд в общей сложности еще 4 раунда (всего 5 раундов). Таким образом, 5 раундов - лучшее, что вы можете сделать с 16 людьми.
[EDIT2] Сначала я думал, что нужно умножить число на 16, но оказывается, что я допустил ошибку в манипуляциях с сетами. Вы можете получить несколько раундов на 20 человек. Я исправил это в обоих примерах.
Ниже приводится метод грубой силы, в котором используется обратный поиск, чтобы найти комбинацию четверок, которая никого не объединит. Он использует наборы для контроля парных коллизий и функции itertools комбинаций () для генерации четверок (комбинаций 4) и пар (комбинаций 2 в четверке).
from itertools import combinations,chain
def arrangeTables(players, tables, alreadyPaired):
result = [[]] * tables # list of foursomes
tableNumber = 0
allPlayers = set(range(1,players+1))
foursomes = [combinations(allPlayers,4)]
while True:
foursome = next(foursomes[tableNumber],None)
if not foursome:
tableNumber -= 1
foursomes.pop()
if tableNumber < 0: return None
continue
foursome = sorted(foursome)
pairs = set(combinations(foursome,2))
if not pairs.isdisjoint(alreadyPaired): continue
result[tableNumber] = foursome
tableNumber += 1
if tableNumber == tables: break
remainingPlayers = allPlayers - set(chain(*result[:tableNumber]))
foursomes.append(combinations(remainingPlayers,4))
return result
def tournamentTables(players, tables=None):
tables = tables or players//4
rounds = [] # list of foursome for each round (one foresome per table)
paired = set() # player-player tuples (lowest payer number first)
while True:
roundTables = arrangeTables(players,tables,paired)
if not roundTables: break
rounds.append(roundTables)
for foursome in roundTables:
pairs = combinations(foursome,2)
paired.update(pairs)
return rounds
Это даст следующий результат:
for roundNumber,roundTables in enumerate(tournamentTables(16)):
print(roundNumber+1,roundTables)
1 [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 16]]
2 [[1, 5, 9, 13], [2, 6, 10, 14], [3, 7, 11, 15], [4, 8, 12, 16]]
3 [[1, 6, 11, 16], [2, 5, 12, 15], [3, 8, 9, 14], [4, 7, 10, 13]]
4 [[1, 7, 12, 14], [2, 8, 11, 13], [3, 5, 10, 16], [4, 6, 9, 15]]
5 [[1, 8, 10, 15], [2, 7, 9, 16], [3, 6, 12, 13], [4, 5, 11, 14]]
Если вы хотите сделать больше раундов, чем позволяет количество людей, вы можете адаптировать это, чтобы использовать Counter () (из коллекций) вместо наборов для реализации «максимального количества повторных пар» для каждого игрока.
[РЕДАКТИРОВАТЬ] Вот вариант функции с максимальным параметром сопряжения и рандомизацией спреда игрока:
from itertools import combinations,chain
from collections import Counter
from random import shuffle
def arrangeTables(players, maxPair, alreadyPaired):
tables = players//4
result = [[]] * tables # list of foursomes
tableNumber = 0
allPlayers = set(range(1,players+1))
def randomFoursomes():
remainingPlayers = list(allPlayers - set(chain(*result[:tableNumber])))
if maxPair > 1: shuffle(remainingPlayers)
return combinations(remainingPlayers,4)
foursomes = [randomFoursomes()]
allowedPairs = 1
while True:
foursome = next(foursomes[tableNumber],None)
if not foursome and allowedPairs < maxPair:
foursomes[tableNumber] = randomFoursomes()
allowedPairs += 1
continue
if not foursome:
tableNumber -= 1
if tableNumber < 0: return None
allowedPairs = 1
foursomes.pop()
continue
foursome = sorted(foursome)
if any(alreadyPaired[pair] >= allowedPairs for pair in combinations(foursome,2)):
continue
result[tableNumber] = foursome
tableNumber += 1
if tableNumber == tables: break
foursomes.append(randomFoursomes())
allowedPairs = 1
return result
def tournamentTables(players, maxPair=1):
rounds = [] # list of foursome for each round (one foresome per table)
paired = Counter() # of player-player tuples (lowest payer number first)
while True:
roundTables = arrangeTables(players,maxPair,paired)
if not roundTables: break
shuffle(roundTables)
rounds.append(roundTables)
for foursome in roundTables:
pairs = combinations(foursome,2)
paired = paired + Counter(pairs)
return rounds
Эта версия позволит вам решить, сколько пар вы готовы принять на игрока, чтобы достичь большего количества раундов.
for roundNumber,roundTables in enumerate(tournamentTables(12,2)):
print(roundNumber+1,roundTables)
1 [[3, 6, 8, 10], [1, 2, 5, 7], [4, 9, 11, 12]]
2 [[1, 4, 5, 11], [3, 6, 7, 8], [2, 9, 10, 12]]
3 [[1, 4, 8, 9], [5, 6, 7, 12], [2, 3, 10, 11]]
Обратите внимание, что вы все равно можете использовать его с максимумом 1, чтобы не допустить повторного спаривания (т.е. 1 спаривание на комбинацию игрока):
for roundNumber,roundTables in enumerate(tournamentTables(20)):
print(roundNumber+1,roundTables)
1 [[1, 2, 3, 4], [13, 14, 15, 16], [17, 18, 19, 20], [9, 10, 11, 12], [5, 6, 7, 8]]
2 [[3, 7, 14, 18], [4, 11, 15, 19], [1, 5, 9, 13], [2, 6, 10, 17], [8, 12, 16, 20]]
3 [[2, 5, 12, 18], [1, 6, 11, 14], [4, 9, 16, 17], [3, 8, 13, 19], [7, 10, 15, 20]]
[EDIT3] Оптимизированная версия.
Я немного поэкспериментировал с этой функцией и добавил несколько оптимизаций. Теперь он может закончить прохождение комбинации из 36 игроков за разумное время. Как я и подозревал, большую часть времени тратится (и не удается) найти решение 6-го раунда. Это означает, что если вы выйдете из функции, как только у вас будет 5 раундов, вы всегда получите быстрый ответ.
Идя дальше, я обнаружил, что после 32 некоторые подсчеты игроков занимают гораздо больше времени. Они тратят дополнительное время, чтобы определить, что больше нет возможных раундов после нахождения тех, которые возможны (например, 5 раундов для 36 человек). Таким образом, 36, 40 и 44 игрока занимают больше времени, но 48 сходятся к 5-раундовому решению намного быстрее. Вероятно, у математиков есть объяснение этому явлению, но на данный момент оно мне недоступно.
На данный момент я обнаружил, что функция производит более 5 раундов, когда у вас 64 человека или больше. (остановка на 5 кажется разумной)
Вот оптимизированная функция:
def arrangeTables(players, tables, alreadyPaired):
result = [[]] * tables # list of foursomes
tableNumber = 0
threesomes = [combinations(range(2,players+1),3)]
firstPlayer = 1 # first player at table (needs 3 opponents)
placed = set() # players sitting at tables so far (in result)
while True:
opponents = next(threesomes[tableNumber],None)
if not opponents:
tableNumber -= 1
threesomes.pop()
if tableNumber < 0: return None
placed.difference_update(result[tableNumber])
firstPlayer = result[tableNumber][0]
continue
foursome = [firstPlayer] + list(opponents)
pairs = combinations(foursome,2)
if not alreadyPaired.isdisjoint(pairs): continue
result[tableNumber] = foursome
placed.update(foursome)
tableNumber += 1
if tableNumber == tables: break
remainingPlayers = [ p for p in range(1,players+1) if p not in placed ]
firstPlayer = remainingPlayers[0]
remainingPlayers = [ p for p in remainingPlayers[1:] if (firstPlayer,p) not in alreadyPaired ]
threesomes.append(combinations(remainingPlayers,3))
return result
def tournamentTables(players):
tables = players//4
rounds = [] # list of foursome for each round (one foresome per table)
paired = set() # player-player tuples (lowest payer number first)
while True: # len(rounds) < 5
roundTables = arrangeTables(players,tables,paired)
if not roundTables: break
rounds.append(roundTables)
for foursome in roundTables:
paired.update(combinations(foursome,2))
return rounds
Оптимизация основана на том факте, что для каждого нового стола первым игроком может быть любой из оставшихся. Если существует действительная комбинация игрока, мы найдем ее с этим игроком на первом месте. Проверять комбинации с другими игроками в этом месте не нужно, поскольку они будут просто перестановками оставшихся столов / игроков, которые будут накрыты этим первым игроком на месте 1.
Это позволяет логике работать с комбинациями 3 вместо комбинаций 4 из списка оставшихся игроков. Он также позволяет раннюю фильтрацию оставшихся игроков за столом, комбинируя только противников, которые не были в паре с игроком, занимающим первое место.