Print all possible gamedays

help
#1

Suppose there is an array without duplicates and with an even number of elements.
A match is a set of two elements from this array, and a gameday is a set of matches such that every element is in exactly one match. Is there an efficient way to print all possible gamedays of an array ?

Example:
Array = [1,2,3,4,5,6,7,8]
Possible gamedays =
[[1,2][3,4][5,6][7,8]],
[[1,2][3,4][5,8][7,6]],
[[1,2][3,4][5,7][6,8]],
…

i am looking for related problems or outlined solutions.

#2

You’re looking to enumerate all possible partitions of a set of numbers into partitions of size 2.

You could do this with a recursive algorithm or you’d have to look into TAoCP for something more iterative/efficient.

There’s an exponential amount of possible gamedays.

1 Like
#3

Just found python - How to split a list into pairs in all possible ways - Stack Overflow. There are several possibilites.
Thank you.

#4

Yes, this can help you a bit to build that recursion but it is not necessary.

Code below does what you want I believe, although a bit inefficiently.

If your set of teams is empty, there’s no partitions.
Otherwise we pick a team x from the list of teams ls that we will pair with one team y from the rest of teams ys (does not include x). Then the remaining teams zs (does not include x or y) are paired with the same process. Once we pair zs we add the (x,y) tuple to one of the possible partitions.

def partitions(ls):
	if not ls:
		yield []
		return
	x, *ys = ls
	for y in ys:
		for p in partitions([z for z in ys if z!=y]):
			yield [(x, y)]+p

Disclaimer, I have only run this code, but have not proven its correctness :smiley: The function should work if length of the array is divisible by 2.

I noticed that the number of partitions grows exponentially and the number matches this OEIS sequence.