Вам нужно, чтобы количество людей было кратно 4 от 16 и далее, если вы хотите пройти более одного раунда без повторного сопряжения.
Например, если у вас есть игроки 1, 2, 3, 4 за первым столом (независимо от того, как вы организуете другие столы), для вашего второго раунда потребуется как минимум 4 стола (по одному на каждого из 4 игроков), чтобы гарантировать, что эти четверо не сидят за одним столом. Вам нужно 16 человек, чтобы заполнить эти четыре стола. Эти 16 человек должны позволить вам пройти 5 раундов без повторной пары. Учитывая, что игроки 1, 2, 3 и 4 никогда не смогут снова встретиться, каждый из них будет монополизировать по одному столу до конца раундов. В этот момент у каждого из них есть еще 12 человек, против которых можно сыграть, и, если вы идеально все смешаете, это будет 3 человека на раунд, всего еще 4 раунда (всего 5 раундов). Таким образом, 5 раундов — это лучшее, что вы можете сделать с 16 людьми.
[EDIT2] Сначала я думал, что нужно число, кратное 16, но оказалось, что я допустил ошибку в манипуляциях с наборами. Вы можете получить несколько раундов для 20 человек. Я исправил это в обоих примерах.
Ниже приведен подход грубой силы, в котором используется возврат для поиска комбинации четверок, которая не будет повторно соединять кого-либо. Он использует наборы для управления парными коллизиями и функцию itertoolscombinations() для генерации четверок (комбинаций 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() (из коллекций) вместо наборов, чтобы реализовать «максимальное количество повторных пар» для каждого игрока.
[EDIT] Вот вариант функции с максимальным параметром спаривания и рандомизацией разброса игроков:
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 из списка оставшихся игроков. Это также позволяет раннее фильтровать оставшихся игроков за столом, объединяя только тех противников, которые не попали в пару с игроком, занимающим первое место.
person
Alain T.
schedule
11.03.2019
