Группы уникальных пар, члены которых появляются один раз на группу

Question

У меня есть этот код:

from itertools import groupby
from itertools import combinations


teams = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
combo = list(combinations(teams, 2))

В результате получается список из 45 кортежей.

[(1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (1, 7), (1, 8), (1, 9), (1, 10), (2, 3), (2, 4), (2, 5), (2, 6), (2, 7), (2, 8), (2, 9), (2, 10), (3, 4), (3, 5), (3, 6), (3, 7), (3, 8), (3, 9), (3, 10), (4, 5), (4, 6), (4, 7), (4, 8), (4, 9), (4, 10), (5, 6), (5, 7), (5, 8), (5, 9), (5, 10), (6, 7), (6, 8), (6, 9), (6, 10), (7, 8), (7, 9), (7, 10), (8, 9), (8, 10), (9, 10)]

Я хотел бы разделить 45 кортежей на 9 групп по 5 кортежей в каждойиз которых уникальные предметы.Например, вот так:

list_1 = [(1, 2), (3, 4), (5, 6), (7, 8), (9, 10)]
list_2 = [(1, 3), (2, 4), (5, 7), (6, 9), (8, 10)]
list_3 = 
list_4 = 
list_5 = 

Таким образом, каждый список содержит кортежи с элементами от 1 до 10 без повторений.

Answer 1

Вот довольно простой подход, основанный на алгоритме планирования турниров в раунде .По сути, этот подход разбивает список пополам и объединяет первую половину списка с обращенной версией второй половины списка.Затем для каждого этапа он «вращает» все команды, кроме первой команды в списке (объединение циклов и списков на основе номера этапа или раунда моделирует ротацию).

# even number of teams required
teams = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
n = int(len(teams) / 2)

stages = []
for i in range(len(teams) - 1):
    t = teams[:1] + teams[-i:] + teams[1:-i] if i else teams
    stages.append(list(zip(t[:n], reversed(t[n:]))))

print(stages)
# [
#     [(1, 10), (2, 9), (3, 8), (4, 7), (5, 6)],
#     [(1, 9), (10, 8), (2, 7), (3, 6), (4, 5)],
#     [(1, 8), (9, 7), (10, 6), (2, 5), (3, 4)],
#     [(1, 7), (8, 6), (9, 5), (10, 4), (2, 3)],
#     [(1, 6), (7, 5), (8, 4), (9, 3), (10, 2)],
#     [(1, 5), (6, 4), (7, 3), (8, 2), (9, 10)],
#     [(1, 4), (5, 3), (6, 2), (7, 10), (8, 9)],
#     [(1, 3), (4, 2), (5, 10), (6, 9), (7, 8)],
#     [(1, 2), (3, 10), (4, 9), (5, 8), (6, 7)]
# ]

Answer 2

Каждая команда появляется 9 раз, поэтому вам понадобится как минимум 9 списков (раундов), чтобы все 45 пар оказались в одном из неповторяющихся списков. Довольно легко генерировать списки игр без повторов, если мы разрешаем разное количество игр в списке. Но если вам нужно 5 игр в списке из 9 списков, вам нужно использовать более сложный алгоритм.

Здесь есть такой алгоритм: https://nrich.maths.org/1443

Вот пример алгоритма в Python (работает для четного и нечетного числа команд):

def roundRobin(teams):
    result    = []
    count     = len(teams)
    even      = 1-(count&1)
    poly      = teams[even:]
    for _ in range(count-even):
        games  = [(teams[0],poly[0])]*even
        games += [(poly[i],poly[count-i-even]) for i in range(1,(count+1)//2)]
        result.append(games)
        poly = poly[1:]+poly[:1]
    return result

# Odd number of teams (7) 
for games in roundRobin(["A","B","C","D","E","F","G"]):
    print(games)
# [('B', 'G'), ('C', 'F'), ('D', 'E')] ("A" sits out)
# [('C', 'A'), ('D', 'G'), ('E', 'F')] ("B" sits out)
# [('D', 'B'), ('E', 'A'), ('F', 'G')] ("C" sits out)
# [('E', 'C'), ('F', 'B'), ('G', 'A')] ("D" sits out)
# [('F', 'D'), ('G', 'C'), ('A', 'B')] ("E" sits out)
# [('G', 'E'), ('A', 'D'), ('B', 'C')] ("F" sits out)
# [('A', 'F'), ('B', 'E'), ('C', 'D')] ("G" sits out)

# Even number of teams (10)
for games in roundRobin(["A","B","C","D","E","F","G","H","I","J"]):
    print(games)     
# [('A', 'B'), ('C', 'J'), ('D', 'I'), ('E', 'H'), ('F', 'G')]
# [('A', 'C'), ('D', 'B'), ('E', 'J'), ('F', 'I'), ('G', 'H')]
# [('A', 'D'), ('E', 'C'), ('F', 'B'), ('G', 'J'), ('H', 'I')]
# [('A', 'E'), ('F', 'D'), ('G', 'C'), ('H', 'B'), ('I', 'J')]
# [('A', 'F'), ('G', 'E'), ('H', 'D'), ('I', 'C'), ('J', 'B')]
# [('A', 'G'), ('H', 'F'), ('I', 'E'), ('J', 'D'), ('B', 'C')]
# [('A', 'H'), ('I', 'G'), ('J', 'F'), ('B', 'E'), ('C', 'D')]
# [('A', 'I'), ('J', 'H'), ('B', 'G'), ('C', 'F'), ('D', 'E')]
# [('A', 'J'), ('B', 'I'), ('C', 'H'), ('D', 'G'), ('E', 'F')]

Answer 3

Мое мнение о проблеме:

from itertools import combinations

teams = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
combo = list(combinations(teams, 2))

sets = []

def is_combo_value_in_set(c, s):
    for val in c:
        for val_s in s:
            for v in val_s:
                if val == v:
                    return True
    return False

for c in combo:
    should_add_set = True
    for current_set in sets:
        if is_combo_value_in_set(c, current_set) is False:
            should_add_set = False
            current_set.add(c)
            break
    if should_add_set:
        sets.append(set())
        sets[-1].add(c)

for v in sets:
    print(sorted(v))

Печать:

[(1, 2), (3, 4), (5, 6), (7, 8), (9, 10)]
[(1, 3), (2, 4), (5, 7), (6, 8)]
[(1, 4), (2, 3), (5, 8), (6, 7)]
[(1, 5), (2, 6), (3, 7), (4, 8)]
[(1, 6), (2, 5), (3, 8), (4, 7)]
[(1, 7), (2, 8), (3, 5), (4, 6)]
[(1, 8), (2, 7), (3, 6), (4, 5)]
[(1, 9), (2, 10)]
[(1, 10), (2, 9)]
[(3, 9), (4, 10)]
[(3, 10), (4, 9)]
[(5, 9), (6, 10)]
[(5, 10), (6, 9)]
[(7, 9), (8, 10)]
[(7, 10), (8, 9)]

Edit:

Возможно, не самое эффективное решение, но оно работает. Мы случайным образом выбрали 5 совпадений, пока совпадения не станут уникальными, и добавим их в список результатов:

from itertools import combinations, chain
from random import choice

teams = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
combo = list(combinations(teams, 2))

available = combo.copy()
rv = []

def random_pop(l):
    ch = choice(l)
    l.remove(ch)
    return ch

num_tries = 0

while True:
    num_tries += 1
    if num_tries > 99999:
        available = combo.copy()
        rv = []
        num_tries = 0

    l = [random_pop(available), random_pop(available), random_pop(available), random_pop(available), random_pop(available)]
    flat = list(chain.from_iterable(l))
    if len(set(flat)) == len(flat):
        #is unique
        rv.append(l)
    else:
        for i in l:
            available.append(i)
    if len(available) == 0:
        break

for l in rv:
    print(sorted(l))

Отпечатки (например):

[(1, 8), (2, 4), (3, 5), (6, 10), (7, 9)]
[(1, 5), (2, 7), (3, 6), (4, 9), (8, 10)]
[(1, 10), (2, 6), (3, 8), (4, 7), (5, 9)]
[(1, 3), (2, 9), (4, 8), (5, 6), (7, 10)]
[(1, 9), (2, 3), (4, 6), (5, 10), (7, 8)]
[(1, 4), (2, 5), (3, 7), (6, 8), (9, 10)]
[(1, 7), (2, 10), (3, 4), (5, 8), (6, 9)]
[(1, 6), (2, 8), (3, 9), (4, 10), (5, 7)]
[(1, 2), (3, 10), (4, 5), (6, 7), (8, 9)]

Answer 4

Попробуйте:

d = {}
for i in combo:
    s = set(teams) - set(i)
    d[i] = [list(s)[k:k+2] for k in range(0, len(s), 2)]

Вывод :

{(5, 9): [[1, 2], [3, 4], [6, 7], [8, 10]], (4, 7): [[1, 2], [3, 5], [6, 8], [9, 10]], (1, 3): [[2, 4], [5, 6], [7, 8], [9, 10]], (4, 8): [[1, 2], [3, 5], [6, 7], [9, 10]], (5, 6): [[1, 2], [3, 4], [7, 8], [9, 10]], (2, 8): [[1, 3], [4, 5], [6, 7], [9, 10]], (6, 9): [[1, 2], [3, 4], [5, 7], [8, 10]], (8, 9): [[1, 2], [3, 4], [5, 6], [7, 10]], (1, 6): [[2, 3], [4, 5], [7, 8], [9, 10]], (3, 7): [[1, 2], [4, 5], [6, 8], [9, 10]], (2, 5): [[1, 3], [4, 6], [7, 8], [9, 10]], (5, 8): [[1, 2], [3, 4], [6, 7], [9, 10]], (1, 2): [[3, 4], [5, 6], [7, 8], [9, 10]], (4, 9): [[1, 2], [3, 5], [6, 7], [8, 10]], (2, 9): [[1, 3], [4, 5], [6, 7], [8, 10]], (3, 10): [[1, 2], [4, 5], [6, 7], [8, 9]], (6, 10): [[1, 2], [3, 4], [5, 7], [8, 9]], (8, 10): [[1, 2], [3, 4], [5, 6], [7, 9]], (1, 5): [[2, 3], [4, 6], [7, 8], [9, 10]], (3, 6): [[1, 2], [4, 5], [7, 8], [9, 10]], (1, 10): [[2, 3], [4, 5], [6, 7], [8, 9]], (7, 9): [[1, 2], [3, 4], [5, 6], [8, 10]], (4, 10): [[1, 2], [3, 5], [6, 7], [8, 9]], (2, 6): [[1, 3], [4, 5], [7, 8], [9, 10]], (7, 10): [[1, 2], [3, 4], [5, 6], [8, 9]], (4, 5): [[1, 2], [3, 6], [7, 8], [9, 10]], (1, 4): [[2, 3], [5, 6], [7, 8], [9, 10]], (2, 10): [[1, 3], [4, 5], [6, 7], [8, 9]], (9, 10): [[1, 2], [3, 4], [5, 6], [7, 8]], (3, 9): [[1, 2], [4, 5], [6, 7], [8, 10]], (2, 3): [[1, 4], [5, 6], [7, 8], [9, 10]], (1, 9): [[2, 3], [4, 5], [6, 7], [8, 10]], (6, 8): [[1, 2], [3, 4], [5, 7], [9, 10]], (6, 7): [[1, 2], [3, 4], [5, 8], [9, 10]], (3, 5): [[1, 2], [4, 6], [7, 8], [9, 10]], (2, 7): [[1, 3], [4, 5], [6, 8], [9, 10]], (5, 10): [[1, 2], [3, 4], [6, 7], [8, 9]], (4, 6): [[1, 2], [3, 5], [7, 8], [9, 10]], (7, 8): [[1, 2], [3, 4], [5, 6], [9, 10]], (5, 7): [[1, 2], [3, 4], [6, 8], [9, 10]], (3, 8): [[1, 2], [4, 5], [6, 7], [9, 10]], (1, 8): [[2, 3], [4, 5], [6, 7], [9, 10]], (1, 7): [[2, 3], [4, 5], [6, 8], [9, 10]], (3, 4): [[1, 2], [5, 6], [7, 8], [9, 10]], (2, 4): [[1, 3], [5, 6], [7, 8], [9, 10]]}

Answer 5

Вы можете использовать рекурсию для генерации комбинаций combo, которые содержат все элементы teams, а затем использовать итератор для фильтрации:

import itertools
teams = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
combo = list(itertools.combinations(teams, 2))
def group(c = [], s = []):
   _c = {i for b in c for i in b}
   if all(i in _c for i in teams):
     yield c
     _s = [i for i in combo if i not in s]
     if _s:
       yield from group(c=[_s[0]], s=s+[_s[0]])
   else:
     _c = {i for b in c for i in b}
     _s = [i for i in combo if i not in s and all(j not in _c for j in i)]
     for i in _s:
       yield from group(c=c+[i], s = s+[i])


results, combos = [], group()
_start = next(combos)
while all(all(j not in i for i in results) for j in _start):
   results.append(_start)
   _start = next(combos)

Вывод:

[[(1, 2), (3, 4), (5, 6), (7, 8), (9, 10)], 
 [(1, 3), (2, 4), (5, 7), (6, 9), (8, 10)], 
 [(1, 4), (2, 3), (5, 8), (6, 10), (7, 9)], 
 [(1, 5), (2, 6), (3, 7), (4, 10), (8, 9)], 
 [(1, 6), (2, 5), (3, 8), (4, 9), (7, 10)], 
 [(1, 7), (2, 8), (3, 9), (4, 6), (5, 10)], 
 [(1, 8), (2, 9), (3, 10), (4, 5), (6, 7)], 
 [(1, 9), (2, 10), (3, 5), (4, 7), (6, 8)], 
 [(1, 10), (2, 7), (3, 6), (4, 8), (5, 9)]]

Answer 6

Я думаю, что следующий код будет работать:

import copy


def extract_one_list(xdata):
    """
    `xdata` .......... `external data`
    """
    old_type = type(xdata[0])
    # we are going to be testing for whether
    # two tuples have any elements in common.
    # For example, do (4, 5) and (7, 8) have any elements common?
    # the answer is `no`.
    prohibited_elements = set(xdata.pop(0))
    iout = [copy.copy(prohibited_elements)]
    # `iout`.......... `internal output`
    candi = 0
    while True:
        # `candi`......... candidate index
        # `candy`......... candidate
        if candi >= len(xdata):
            break
        candy = set(xdata[candi])
        if len(prohibited_elements.intersection(candy)) == 0:
            iout.append(candy)
            prohibited_elements.update(xdata.pop(candi))
        candi = candi + 1

    # Next, convert sets into the type of container
    # which was originally used (tuples, lists,
    # or some other type of container
    # Let external iout (xout) be:
    # the old_type of the internal element (ielem)
    # for each internal element in the internal iout (iout)
    xout = [old_type(ielem) for ielem in iout]
    return xout

def extract_all_lists(xdata):
    lol = list()
    # `lol`...... `list of lists`
    while len(xdata) > 0:
        lyst = extract_one_list(unsorted_data)
        lol.append(lyst)
    return lol

unsorted_data = [(1, 2), (1, 3), (1, 4), (1, 5), (1, 6),
                 (1, 7), (1, 8), (1, 9), (1, 10), (2, 3),
                 (2, 4), (2, 5), (2, 6), (2, 7), (2, 8),
                 (2, 9), (2, 10), (3, 4), (3, 5), (3, 6),
                 (3, 7), (3, 8), (3, 9), (3, 10), (4, 5),
                 (4, 6), (4, 7), (4, 8), (4, 9), (4, 10),
                 (5, 6), (5, 7), (5, 8), (5, 9), (5, 10),
                 (6, 7), (6, 8), (6, 9), (6, 10), (7, 8),
                 (7, 9), (7, 10), (8, 9), (8, 10), (9, 10)]

lol = extract_all_lists(unsorted_data)
print('\n'.join([str(x) for x in lol]))

Вывод:

[(1, 2), (3, 4), (5, 6), (8, 7), (9, 10)]
[(1, 3), (2, 4), (5, 7), (8, 6)]
[(1, 4), (2, 3), (8, 5), (6, 7)]
[(1, 5), (2, 6), (3, 7), (8, 4)]
[(1, 6), (2, 5), (8, 3), (4, 7)]
[(1, 7), (8, 2), (3, 5), (4, 6)]
[(8, 1), (2, 7), (3, 6), (4, 5)]
[(1, 9), (2, 10)]
[(1, 10), (9, 2)]
[(9, 3), (10, 4)]
[(10, 3), (9, 4)]
[(9, 5), (10, 6)]
[(10, 5), (9, 6)]
[(9, 7), (8, 10)]
[(10, 7), (8, 9)]

Answer 7

Если я не пропустил что-то по этому вопросу, может быть, что-то подобное с использованием frozenset s подойдет?

from itertools import combinations


teams = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
games = set(frozenset(combo) for combo in combinations(teams, 2))
brackets = []

while games:
    bracket = []
    while games and len(bracket) < 5:
        bracket.append(tuple(sorted(games.pop())))
    brackets.append(bracket)

for bracket in brackets:
    print(bracket)

выходы (например)

[(4, 10), (2, 8), (1, 4), (4, 6), (2, 3)]
[(3, 9), (2, 6), (4, 5), (7, 9), (7, 8)]
[(4, 9), (1, 10), (2, 9), (5, 9), (3, 4)]
[(6, 9), (1, 7), (7, 10), (8, 10), (2, 4)]
[(1, 8), (5, 6), (3, 5), (1, 6), (5, 8)]
[(1, 3), (4, 7), (3, 7), (6, 7), (3, 6)]
[(3, 8), (1, 5), (6, 8), (5, 10), (2, 7)]
[(5, 7), (1, 9), (2, 10), (9, 10), (1, 2)]
[(8, 9), (6, 10), (2, 5), (3, 10), (4, 8)]