How to generate all possible X sets of matchups for N teams split into N/2 pairs?

Question

I wasn't sure how to word this question... Any suggestions or edits would be appreciated!

I am trying to get all possibilities for a league schedule. I have 8 teams that are playing against each other for 12 weeks. Each week there are four time slots at which one pair of teams would play.

How to split a list into pairs in all possible ways gives me a solution to get:

[(0, 1), (2, 3), (4, 5), (6, 7)]
[(0, 1), (2, 3), (4, 6), (5, 7)]
[(0, 1), (2, 3), (4, 7), (5, 6)]
...
[(0, 2), (1, 3), (4, 5), (6, 7)]
[(0, 2), (1, 3), (4, 6), (5, 7)]
[(0, 2), (1, 3), (4, 7), (5, 6)]

and so on. It seems that there are 105 = 15*7 such pairs.

However, these are not all the pairs. Since I have 4 time slots at which teams can play, the order of these pairs inside the lists can change.

Ex:
(0, 1) is the same as (1, 0) 
but
[(0, 1), (2, 3), (4, 5), (6, 7)]
is not the same as
[(2, 3), (0, 1), (4, 5), (6, 7)]

I want to ultimately have all possible sets of 12 of these 4-pair matchups where no team will play another team more than 2 times.

If I were to create all the possible schedules by doing:

schedules = list(itertools.combinations(<all_possible_4-pair_matchups>, 12))

that would be very inefficient and would take a very long time to run. This approach does not take into account whether a team has played another team more than twice.

I have this code so far:

# Author: Abraham Glasser, abrahamglasser@gmail.com
#
# This program determines if there's a schedule where
# each team will play at a specific hour exactly 3 times
#
# 12 weeks
# 8 teams
# 4 hours per week

from pandas import *

teams = [i for i in range(8)]

twelve_weeks = [[[-1 for i in range(2)] for j in range(4)] for k in range(12)]

# table to count how many times a team 
# has played at a specific time slot
hour_count = [[0 for i in range(4)] for j in range(8)]

# table to count how many times two teams have played each other
game_count = [[0 for i in range(8)] for j in range(8)]
for i in range(8):
    # a team cannot play against itself
    game_count[i][i] = "X"


# function to update game count
def update_game_count():
    for week in twelve_weeks:
        for hour in week:
            if hour[0] == -1:
                pass
            else:
                game_count[hour[0]][hour[1]] += 1
                game_count[hour[1]][hour[0]] += 1

# function to update hour count
def update_hour_count():
    for week in twelve_weeks:
        for hour in range(4):
            pair = week[hour]
            for team in teams:
                if team in pair:
                    hour_count[team][hour] += 1

# solution from 
# https://stackoverflow.com/questions/5360220/how-to-split-a-list-into-pairs-in-all-possible-ways
def all_pairs(lst):
    if len(lst) < 2:
        yield lst
        return
    a = lst[0]
    for i in range(1,len(lst)):
        pair = (a,lst[i])
        for rest in all_pairs(lst[1:i]+lst[i+1:]):
            yield [pair] + rest


x = list(all_pairs([0, 1, 2, 3, 4, 5, 6, 7]))

# TAKES TOO LONG AND DOES NOT ACCOUNT
# FOR TEAMS PLAYING MORE THAN TWICE
#
# schedules = list(itertools.combinations(x, 12))

# pretty printing

print("\nThe twelve weeks:")
print(DataFrame(twelve_weeks))

print("\n The hour counts:")
print(DataFrame(hour_count))

print("\n The game counts:")
print(DataFrame(game_count))

Answer 1

Do you have an estimate on the number of solutions? If this number is too large, then there won't be a way to list all of these pairings.

I did a recursive approach to list all possibilities in some tree-like way.

• Bad news: It probably takes too long (did not finish while writing this post).
• Good news: It looked fine for 6 teams and 8 weeks (and < 1s time), so maybe you/anyone can recycle some ideas.

Here it is:

import itertools
import numpy as np

n = 6
weeks = 8

def all_pairs(lst):
  if len(lst) < 2:
    yield lst
    return
  a = lst[0]
  for i in range(1,len(lst)):
    pair = (a,lst[i])
    for rest in all_pairs(lst[1:i]+lst[i+1:]):
      yield [pair] + rest

def recurse(so_far, rem_list, count):
  if len(so_far) == weeks: return [so_far]

  res = []
  for current in range(len(rem_list)):
    match = rem_list[current]
    new_count = count.copy()
    for pair in match:
      new_count[pair[0],pair[1]] += 1
      new_count[pair[1],pair[0]] += 1
    #set of pairs, whcih are not allowed any more
    forbidden = {(i,j) for i in range(n) for j in range(n) if new_count[i,j] == 2}
    #append current match, remove all now forbidden combinations
    res += recurse(so_far + [match], [entry for entry in rem_list[(current+1):] if set(entry) & forbidden == set([])], new_count)
  return res

l = list(all_pairs(list(range(n))))
foo = recurse([], l, np.zeros((n,n)))