Need an adaptive algorithm for participant subgroups that balances repeated pairings I want to build a utility that helps manage small groups of participants. It is an acting class setting.
For each exercise, the facilitator will usually have some number of participants get up to do a scene. Two is the most common, but sometimes 1 or 3 or 4. More than 4 is not common.
I want the utility to have a list of participants and then the facilitator can just ask it for a specified number of people. E.g. 2.
The utility should do a good job of balancing combinations. For example, let's say there are 5 participants, A, B, C, D, E. If A and B work together, then ideally they should have also worked with C, D, and E before working together again.
I know how to manage this well if it's always just pairs. You can create, in advance an ordered list of all the pairings.
But once you add the possibility of other changeable group sizes, I don't know how to manage it.
My starting point is to keep track of how often each participant has worked with every other participant. So, I could look at A and know how often she has worked with B, C, D, and E, and then if A is due to get up, pair her with the person/people she has worked least often with.
The problem with this, is that it can lead to situations where the last remaining unmatched pair have already worked together.
As a simple counter-example: Say I have 6 participants - A - F. In the first lot of exercises, these are the pairs. AB CD EF. Then next round, I might (if not thinking) do AC, then BD, but now I'm left with E and F again. This is not ideal, and is what I need the algorithm to avoid.
I think part of the solution should be that everyone should get a roughly even number of turns. So, at any given point, we have a group of participants who have had fewer turns that the others, and we need to balance them out so that they don't work with people they've worked with (where possible) or at least with the people they've worked with least, and it needs to anticipate the possible remaining combinations and avoid duplication there too. Part of the complexity is that you don't know in advance what group sizes will be used for the remaining groups.
Does this type of algorithm / problem set have a specific name? Are there known algorithms for solving it?
(As an extra complication, there is the possibility of a participant having to leave unexpectedly, or an extra participant who arrives late, but that might be for later)
This is my first time asking here, so I hope I've posted this appropriately. Thanks for your patience and assistance!
It sounds like the stakes are low, so I would suggest something simple and &quot;good enough&quot;, rather than looking for fancy algorithms that will be guaranteed to give the optimal solution.  One approach is to take the approach you're already considering, but break ties randomly.  This seems like it may do well enough in practice: it is possible to get  into a bad situation, but the randomness might make that unlikely; and this might occasionally have one student participate a little more than they otherwise would, but that I'd expect that to average out over time and so maybe it isn't a big deal.