9

I have this code:

from itertools import groupby
from itertools import combinations


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

The output is a list of 45 tuples.

[(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)]

I would like to divide 45 tuples into 9 groups of 5 tuples, each of which are unique items. For example like so:

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 =

So each list contains tuples with items from 1 to 10 without repetition.

Improve this question
7
  • It looks like you have an extra bracket before the second element, is that supposed to be there? Commented Jun 3, 2019 at 13:45
  • 1
    Do you need to divide existing 45 tuples? Or, maybe, generate such tuples from scratch? Commented Jun 3, 2019 at 13:45
  • @Sergius there are 945 such pairs Commented Jun 3, 2019 at 13:51
  • 5
    Possible duplicate of Groups of pairwise combinations where each member appears only once Commented Jun 3, 2019 at 13:52
  • there are 4725 combinations in all. Commented Jun 3, 2019 at 14:36

7 Answers 7

Reset to default
8

Here is a fairly straightforward approach based on a round robin tournament scheduling algorithm. Basically, this approach splits the list in half and pairs the first half of the list with a reversed version of the second half of the list. Then, for each stage it "rotates" all teams except for the first team in the list (the loop and list concatenation based on the stage or round number is simulating the rotation).

# 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)]
# ]
Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

2

Try this :

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)]

Output :

{(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]]}
Improve this answer

1 Comment

Image
Thanks, I want to divide the existing 45 tuples without repetitions.
2

My take on the problem:

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))

Prints:

[(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:

Maybe not the most efficient solution, but it works. We randomly chose 5 matches until the matches are unique and add it to the result list:

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))

Prints (for example):

[(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)]
Improve this answer

1 Comment

Image
Thanks, this is very close to what I need. Is that possible to make lists of equal number of tuples? Thats is 9 lists of 5 tuples each?
2

Every team appears 9 times so you will need at least 9 lists (rounds) to ensure that all 45 pairs appear in one of the non-repeating list. It is fairly easy to generate lists of games without repetition if we allow different number of games per list. But if you want 5 games per list on 9 lists, you will need to use a more sophisticated algorithm.

There is such an algorithm here: https://nrich.maths.org/1443

Here's an example of the algorithm in Python (works for even and odd number of teams):

def roundRobin(T):
    P = T[1:]+len(T)%2*[None]
    for _ in range(len(T)-1):
        yield [g for g in zip(T[:1]+P[1:len(P)//2+1],P[:1]+P[::-1])]
        P.append(P.pop(0))

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

[('A', 'B'), ('C', None), ('D', 'G'), ('E', 'F')] # C sits out
[('A', 'C'), ('D', 'B'), ('E', None), ('F', 'G')] # E sits out
[('A', 'D'), ('E', 'C'), ('F', 'B'), ('G', None)] # G sits out
[('A', 'E'), ('F', 'D'), ('G', 'C'), (None, 'B')] # B sits out
[('A', 'F'), ('G', 'E'), (None, 'D'), ('B', 'C')] # D sits out
[('A', 'G'), (None, 'F'), ('B', 'E'), ('C', 'D')] # F 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')]
Improve this answer

1 Comment

Image
Of course you are right. But I need them to play only one time against each other over 9 rounds...
1

I think the following code will work:

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]))

The output is:

[(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)]
Improve this answer

Comments

1

You can use recursion to generate combinations of combo that contain all the elements of teams and then use an iterator to filter:

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)

Output:

[[(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)]]
Improve this answer

Comments

0

Unless I'm missing something about the question, maybe something like this using frozensets will do?

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)

outputs (e.g.)

[(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)]
Improve this answer

1 Comment

Image
Items in each list are not unique, in other words each team should play only once each round.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.