Формирование игровых пар случайным образом (Python)
Пробую составить распиание для спортсменов, формирующих случайным образом команды, состоящие из двух человек (теннис, настольный теннис итд) Каждый игрок может сыграть с другим в одной команде один раз Каждый игрок может выступить соперником другого игрока не более двух раз
После формирования определенного числа выборок на игровой тур новые выборки не добавляются, возможно и предыдущие туры нужно пересобрать Буду благодарен за идею реализации.
Нужно получить и вывести все возможные сочетания, например: [3, 9, 10, 4, 11, 8, 5, 7, 1, 12, 2, 6] т.е. в данном туре команда из игроков 3, 9 играет против игроков 10, 4; игроки 11,8 играют против игроков 5 и 7 и т д.
import random
def check_candid(fields):
for k in range(0, fields, 4):
if candid[k] not in pro[candid[k+1]]:
return False
if candid[k] not in contra[candid[k+1]] or candid[k] not in contra[candid[k+2]]:
return False
return True
def correct(fields):
for k in range(0, fields):
pro[candid[4*k]].remove(candid[4*k+1])
pro[candid[4*k+1]].remove(candid[4*k])
pro[candid[4*k+2]].remove(candid[4*k+3])
pro[candid[4*k+3]].remove(candid[4*k+2])
contra[candid[4*k]].remove(candid[4*k+2])
contra[candid[4*k]].remove(candid[4*k+3])
contra[candid[4*k+1]].remove(candid[4*k+2])
contra[candid[4*k+1]].remove(candid[4*k+3])
contra[candid[4*k+2]].remove(candid[4*k])
contra[candid[4*k+2]].remove(candid[4*k+1])
contra[candid[4*k+3]].remove(candid[4*k])
contra[candid[4*k+3]].remove(candid[4*k+1])
if __name__ == '__main__':
random.seed(100)
players = 12 # количество игроков
fields = 3 # количество площадок
pro = [[k for k in range(1,players+1) if k != i] for i in range(0, players+1)] # потенциальные игроки-партнеры
pro[0] = []
contra = [item + item for item in pro] # потенциальные соперники
rasp = []
stage = 0
for t in range(100):
cur_pl = [x for x in range(1, players+1)]
candid = [] # candidate for rasp
for field in range(fields):
x = random.choice(cur_pl) # 1st player
ok1 = True # Correct queue?
cur_pl.remove(x)
set1 = set(cur_pl) & set(pro[x])
list2 = sorted(list(set1)) # чтобы уйти от произвольной выборки из множества при отладке
if not list2: # пустой список - идем на слледующую итерацию
ok1 = False
break
pro1 = random.choice(list2) # выбрали партнера
candid.append(x)
candid.append(pro1) # добавили игрока и партнера в список кандидатов на корректный тур
cur_pl.remove(pro1)
cont1 = random.choice(cur_pl)
cur_pl2 = list(cur_pl)
cur_pl2.remove(cont1)
while (cont1 not in contra[x] or cont1 not in contra[pro1]):
# если 1го кандидата в соперники в списке возможных кандидатов нет, то выбираем из оставшихся в cur_pl2
if not cur_pl2: # пустой список - идем на слледующую итерацию
ok1 = False
break
cont1 = random.choice(cur_pl2)
cur_pl2.remove(cont1)
if not ok1:
break
cur_pl.remove(cont1)
cont2 = random.choice(cur_pl)
cur_pl2 = list(cur_pl)
cur_pl2.remove(cont2)
while cont2 not in contra[x] or cont2 not in contra[pro1] or cont2 not in pro[cont1]:
# если 2го кандидата в соперники в списке возможных кандидатов нет, то выбираем из оставшихся в cur_pl2
if not cur_pl2: # пустой список - идем на слледующую итерацию
ok1 = False
break
cont2 = random.choice(cur_pl2)
cur_pl2.remove(cont2)
if not ok1:
break
cur_pl.remove(cont2)
candid.append(cont1)
candid.append(cont2) # составили потенциальный состав участников на след. тур
if ok1:
ok = check_candid(fields)
if ok: # корректная выборка, корректируем pro и contra
stage +=1
correct(fields)
print('----------')
print('pro:', pro)
print('contra:', contra)
print('Next stage:', stage, candid) # состав на след. тур
Ответы (1 шт):
Попробуйте, устроит ли вот такой несложный метод:
import random
from collections import Counter
def gen(n):
cnt = Counter()
pairs = [(a,b) for a in range (n-1) for b in range(a+1,n)]
random.shuffle(pairs)
#print(pairs)
ll = len(pairs)
while ll > 1:
pair = pairs[ll-1]
for i in range(ll-1):
p = pairs[i]
if len(set([p[0], p[1], pair[0], pair[1]])) == 4:
ps = [(p[i], pair[j]) for i in range(2) for j in range(2)]
for x in ps:
if cnt[x] == 2:
break
else:
for x in ps:
cnt[x] += 1
print(p, ':', pair)
pairs[i] = pairs[ll-2]
ll -= 2
break
else:
ll -= 1
gen(8)
(1, 6) : (0, 7)
(0, 3) : (6, 7)
(0, 6) : (3, 4)
(4, 7) : (0, 5)
(5, 6) : (0, 1)
(0, 4) : (2, 5)
(4, 5) : (3, 7)
(3, 6) : (1, 4)
(1, 3) : (5, 7)
(3, 5) : (2, 6)
(4, 6) : (2, 7)
(0, 2) : (1, 5)
(1, 7) : (2, 3)
Генерируются все пары. Их список перемешивается. Выбираем играющую пару (у меня последняя), для неё ищем первую подходящую пару - игроки не пересекаются, счётчики "играл против" не более двух. Если нашли - выводим обе пары, увеличиваем счётчики, убираем обе пары из дальнейшего рассмотрения. Если не нашли ли ни одной подходящей - убираем не сыгравшую пару.
В примере сыграло 26 из 28 возможных пар. Если брать 6 игроков, то в большинстве случаев играет максимум пар - 14 из 15, иногда 12.
Заготовка для учёта нескольких площадок в одном туре (проверка счётчиков пока слишком громоздкая получается)
def gen(n, nfields):
cnt = Counter()
pairs = [(a,b, (1<<a)|(1<<b)) for a in range (n-1) for b in range(a+1,n)]
random.shuffle(pairs)
#print(pairs)
ll = len(pairs)
while ll > 1:
first = pairs[ll-1]
mask = first[2]
pool = []
for i in range(ll-1):
if pairs[i][2] & mask == 0:
pool.append(pairs[i])
mask |= pairs[i][2]
if len(pool) == 2 * nfields - 1:
#здесь пробуем образовать пары, учитывая счётчики