Algorithm for splitting players into unique group every round

Question

For a match I have certain number of players, certain number of groups (players and groups are aliquot) and certain number of rounds to be played (players are reshuffled every round). Ideally, I'd like players to meet new people every round.

It seems like a common problem that had to be solved many times before, If I only knew how to search for it. I tried bruteforce algorithm without success thanks to factorial growth.

Also, I'd like to split players of the same nationality as much as possible, but I think this can be done as a separate problem when filling real people into precalculated bracket.

edit: Found out tournament golfers had similar problems and their pre-calculated solution matched just my needs (more on http://csplib.org/Problems/prob010/)

Answer 1

This is called "Social golfer problem" and in general, it is considered unsolved problem. There exists calculated ideal solutions for certain input values and the best aproach is to look into these if you can apply one of them.

read more on:

http://csplib.org/Problems/prob010/

http://web.archive.org/web/20130602000640/http://www.maa.org/editorial/mathgames/mathgames_08_14_07.html

Answer 2

Although I don't quite understand the role of groups in your problem, I'll try to give some hints.

You can develop a backpropagation algorithm and try to minimize possible combinations.

Or you can go for an optimization algorithm. The first step here would be to define a score function for each possible solution. Maybe it's enough to generate random solutions and take the best one, maybe you need a more sophisticated optimization algorithm.