How can I assign people to groups of 4 and optimize for "strangers" on a week-to-week basis when the group can change?

Question

Let's say I have a group of people that meets every week. I would like to assign them to groups of 4. How can I assign these people such that, week after week, collectively, every group consists largely of "strangers"?

For example, John, Paul, George, and Ringo being assigned together means John has been grouped with Paul a minimum amount of times, and George has been assigned together with Ringo a minimum amount of times, etc. Same with John and George, John and Ringo, Paul and George, etc. Not only that, but the other 5 groups must consist of people who are largely "strangers" to each other.

Here's the big kicker. Let's also say that week after week, the people are not the same. Sometimes new people get introduced to this group (substitutions). Some weeks there can be less people or more people. Order doesn't matter. How would I tackle this problem?

For full context, I am trying to automatically assign people in groups of 4 for a 2v2 volleyball league that plays every week, and I can't really count on people to show up every week.

Answer 1

A standard approach that is very general is to formulate this as an instance of integer linear programming, and apply an off-the-shelf ILP solver. The field of operations research deals with a lot of combinatorial optimization problems, such as arise in scheduling and logistics, and ILP solvers are one standard tool for this (there are other tools as well).