What Sort Of Algorithm Should I Use To Sort Students?

Question

In a program that generates random groups of students, I give the user the option to force specific students to be grouped together and also block students from being paired. I have tried for two days to make my own algorithm for accomplishing this, but I get lost in all of the recursion. I'm creating the program in Lua, but I'll be able to comprehend any sort of pseudo code. Here's an example of how the 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

I then 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(i.e. 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 every student is placed in those groups(note that they also remain in the students table still), I begin by inserting the students who are forced to be paired together in groups(well, I have tried to), insert students who have one or more entries in the deny table into groups where they are able to be placed, and just fill the remaining groups with the leftovers.

There are a couple of things that will be of some use:

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(i.e. 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 stated before, I have no clue how to set up a recursive algorithm for this. Every time I try and insert the forced students together, I end up getting the same student in multiple groups, forced pairs not being paired together, etc. Also note the formats. In each student's force/deny table, the name of the target student is given -- not a direct reference to the student. What sort of algorithm should I use(if one exists for this case)? Any help is greatly appreciated.

Answer 1

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.