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 ?
Array = [1,2,3,4,5,6,7,8]
Possible gamedays =
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.
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.
if not ls:
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.