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/)

• Caleth: Do you have specific values for "players per group" and/or "number of groups" or should this handle any arbitrary splitting?
• David162795: @Caleth I was trying to make universal algorithm, but it looks harder and harder to do. Numbers for my first case are 32ppl,8tables, 8 rounds and second case 28ppl, 7 tables, 8 rounds
• ZeroOne: You should post your solution as an answer to your question, not as an edit, and then accept it.

Answer 1

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.

Answer 2

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