What algorithm should I use to sort students?

Question

In a program that generates random groups of students, I give the user the ability to force individual students to group, as well as block students from mating. I tried for two days to make my own algorithm to achieve this, but I got lost in all recursion. I am creating a program in Lua, but I can understand any pseudocode. Here is an example of how students are sorted:

students = { Student1 = {name=Student1, force={"Student2"}, deny={}}; Student2 = {name=Student2, force={"Student1","Student3"}, deny={}}; Student3 = {name=Student3, force={"Student2"}, deny={}}; }-- A second name property is given in the case that the student table needs to be accessed by students[num] to retrieve a name 

Then I create temporary tables:

 forced = {}--Every student who has at least 1 entry in their force table is placed here, even if they have 1 or more in the deny table denied = {}--Every student with 1 entry for the deny table and none in the force table is placed here leftovers = {}--Every student that doesn't have any entries in the force nor deny tables is placed here unsortable = {}--None are placed here yet -- this is to store students that are unable to be placed according to set rules(ie a student being forced to be paired with someone in a group that also contains a student that they can't be paired with SortStudentsIntoGroups()--predefined; sorts students into above groups 

After each student is placed in these groups (note that they also remain in the students table), I start by inserting students who are forced to mate in groups (well, I tried), insert students who have one or more records in the deny table into groups where they can be placed, and simply fill in the remaining groups with residues.

There are a few things that will be helpful:

 numGroups--predefined number of groups maxGroupSize--automatically calculated; quick reference to largest amount of students allowed in a group groups = {}--number of entries is equivalent to numGroups(ie groups = {{},{},{}} in the case of three groups). This is for storing students in so that the groups may be displayed to the end user after the algorithm is complete. sortGroups()--predefined function that sorts the groups from smallest to largest; will sort largest to smallest if supplied a true boolean as a parameter) 

As I said, I don’t know how to set up a recursive algorithm for this. Each time I try to insert forced students together, I end up getting the same student in several groups, forced couples don't connect together, etc. Also pay attention to the formats. Each student’s strength / rejection table indicates the name of the target student — there is no direct reference to the student. What algorithm should I use (if it exists for this case)? Any help is appreciated.

Answer 1

It seems to me that you are facing the NP-Hard problem.

This is equivalent to a graphic coloring with colors k , where the edges are prohibition lists.

Graphic arts:

 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 

Reduction from coloring the graph to your problem:
Given the problem of coloring the graph (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 the student, and the student denies all students that there is an edge between the vertices representing them. Number of groups - a given number of colors.

Now, given the solution to your problem, we get groups k that, if student u rejects 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.
Another way is similar

So, we got here a polynomial reduction from the problem of graph coloring, and thus find the optimal solution to your problem - NP-Hard, and there is no effective solution to this problem , and most believe that this does not exist.

Some alternatives use heuristics, such as Genetic algorithms , which do not provide optimal solutions or use brute force for a lot of time (which is not possible for a large number of students).
Brute force will generate all possible partitions into groups k and check if this is an acceptable solution, in the end - the best solution will be found.