Algorithm for round robin foursomes

[Kaz]

Hello, I'm trying to solve a problem with foursomes that don't care about pairs within. It's an ever-person-for-themselves card game. I'd like to write a program that takes 2 inputs:  n multiples of 4, and m rounds.
The Whist tables are nice but I wonder if the problem is even easier if the pairs within don't matter. I just want to Minimize the amount of repeat groupings, or maximize the number of unique groups, making sure that everyone plays with everyone else at least once but not too many times.
I'd prefer to do this in python, but if Excel can do it I'd be interested in that option as well.
Thank you.

[Ian Wakeling]

The problem is harder than you imagine, as there is no easy to program formula that you can use.  Algorithms are possible, for example you could just start by assigning people to tables at random and then swap people between tables, within a round, to improve the balance, and keep making more swaps to get further improvements.  My advice would be to take a different approach and build a library of schedules.  This page by Ed Pegg should get you started - in particular take heed of his warning in the last 2 sentences of the article!  Ed's point is that some perfect solutions exist, but you are very unlikely to find them with a general algorithm. Take for example n=10 and m=13, there is a solution here made with combinatorial math, which you are unlikely to find with days/weeks of computer search.  As there are no repeated pairs in this schedule, you are free to throw away as many rounds as you want, so it solves the problem for n=10 m<=13.  For m>13 you can use some rounds taken from a second copy.  Hope that helps.

[Kaz]

Thanks for the links. I did find an n=4, m=5 solutions there (i.e., 16 players, 5 rounds). Does that mean any further rounds should just be a random permutation of those 5? 

Also, it starts at 16 players, what if we have less than that? So my question would be how many days can 12 players play in foursomes, ensuring everyone gets in a group with everyone else at least once and without repeating groups. And what if there's 13 with one person getting a bye each week? 

How did you find the solution for n=10 and m=13? I'm interested in learning to solve these. I've done complex mat before but not combinatorics. Do I just need to look into the "Resolvable Balanced Incomplete Block Design" or is there some other fundamental that helps for more types of problems?

Initially I was thinking a linear programming problem could be formulated but it does appear to be more complicated that that. Brute force might be possible on a large cluster but I also understand the curse of dimensionality. Maybe a parallel dynamic programming approach could work? There have been new methods that have been efficiently parallelized on cpu/gpu clusters to solve problems previously thought unsolvable

I'm not really interested in n>8 or m>10, so I would still think an algorithm could work without dimensions becoming too problematic. 

Possibly a genetic algorithm could work if you penalize pairing with the same person more than once. 

[Ian Wakeling]

With 16 players and more than 5 rounds you can reuse the 1st 5 rounds, but randomly reassign the player names to the player numbers, so it's unlikely that you end up with the same 4 people sitting at a table.  Or even better you could use part of the schedule here (see my reply #1) that guarantees that the same 3 people never sit together.

For lower numbers of players, in general when there are fewer tables than players at a single table, then it is not possible to play 2 rounds without having some pairs of players oppose each other twice.  In these instances the best solution will depend on the number of rounds, however the problem will be small enough that a computer search by LP, GA, etc should work well.

Byes add another layer of complexity - to balance the byes you need a specific number of rounds.  In the case of 13 players, the 13 round whist tournament (ignoring the 2-v-2 aspect) is best.

The n=10, m=13 schedule came from this paper by Kageyama. Which also answers your other question about RBIBDs being the right thing to look for.