# How to make an algorithm to optimally make student groups without overlap

My sister (a high school teacher) came and asked me the following question:

"Hi bro I'm having 28 new students in my class. They need to know each other. So I want everybody to work together in small groups. I'm thinking splitting them in groups of 4 and having 9 rounds. Then everyone meets 3 people in every round and after 9 rounds they have been in a group with everybody. Isn't that pretty. But I'm just missing an algorithm to set up the groups and you are a CS-master that must a be a job for you!"

I have been trying to figure it out, but the combinatoric search space is to big. Do you have a good suggestion for a way to create these groups.

• This frankly sounds more like a question for Math.SE (it's some kind of combinatorial design). But if you want to try to solve it with CS methods, you could express it as an instance of SAT and see if a SAT solver is able to find a solution for you.
– D.W.
Aug 23, 2022 at 19:52

## 1 Answer

You can solve it with satisfiability. Here i have created the SAT formula for you. Sorry i deleted this answer earlier because i forgot to add a formula, i fixed it, it should be correct now.

• Notice that all the formula is in conjunctive normal form
– LLL
Aug 25, 2022 at 1:04
• Edited the post to add explanation on why p-3 amount of Ati,j
– LLL
Aug 25, 2022 at 1:21