Seems to me like you are facing an NP-Hard Problem here.
This is equivalent to graph-coloring problem with k
colors, where edges are the denial lists.
Graph Coloring:
Given a graph G=(V,E), and an integer `k`, create coloring function f:V->{1,2,..,k} such that:
f(v) = f(u) -> (v,u) is NOT in E
The reduction from graph coloring to your problem:
Given a graph coloring problem (G,k)
where G=(V,E)
, create an instance of your problem with:
students = V
for each student: student.denial = { student' | for each edge (student,student')}
#groups = k
Intuitively, each vertex is represented by a student, and a student denies all students that there is an edge between the vertices representing them. The number of groups is the given number of colors.
Now, given a solution to your problem - we get k
groups that if student u
denies student v
- they are not in the same group, but this is the same as coloring u
and v
in different colors, so for each edge (u,v) in the original graph, u
and v
are in different colors.
The other way around is similar
So, we got here a polynomial reduction from graph-coloring problem, and thus finding an optimal solution to your problem is NP-Hard, and there is no known efficient solution to this problem, and most believe one does not exist.
Some alternatives are using heuristics such as Genetic Algorithms that does not provide optimal solution, or using time consuming brute force approaches (that are not feasible for large number of students).
The brute force will just generate all possible splits to k
groups, and check if it is a feasible solution, at the end - the best solution found will be chosen.