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.

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

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