Student grouping algorithm
A friend of mine is an English teacher. He has 24 students in his writing class, and 5 workshops over the course of the semester. For each workshop, he would like to divide his students into 6 groups of 4, such that each student is never in a group with the same classmate twice.
The first division is trivial. The second division is easy. The third division can be figured out with a piece of paper and some trial and error. By the fourth division, we need an Algorithm.
I wrote a quick brute-force solution last night. It took milliseconds to find the first grouping, 3 minutes and 54915874 combinations to find the 2nd and 3rd groupings, and 4 hours and 2169198469 combinations to find the 4th and 5th groupings. (The only possible remaining 6th grouping is not valid, which is okay as long as we only need 5.)
Now, I have no doubt that a better algorithm exists. I suspect that it's graph theory, and that all I have to do is find a greedy coloring of a subgraph isomorphism of a maximally Hamiltonian clique, or something.
But I can't figure out what the abstraction is, nor can my Google-fu locate the answer.
Any ideas?