In a smallish class, some lectures are set aside for working in groups. The instructors don't want people to group themselves together with the same people every time; instead, they create the groups beforehand, trying to make sure that all students work with one another as equally as possible. Your job is to write a program that makes student groups for one class, given all the groups in previous classes, in a way that minimizes the same people working together often.
Format for groups for a single class
Students in the class will be numbered as consecutive integers, starting at 1 (or 0 if you prefer). The set of groups for a single class (hereafter called a "day of groups") will be a list of lists, or any reasonable alternative. Every group must have size 3 or 4; and the number of 3-person groups must be as small as possible. For example, in a 15-student class, the following is a valid day of groups:
{{1,8,10,15},{2,7,9},{3,6,12,13},{4,5,11,14}}
But five 3-student groups is invalid. Of course, no student can be in two different groups in a single day of groups.
Input structure
The input will consist of one or more days of groups, each in the format described above; the days of groups can be separated from each other by commas, newlines, or anything reasonable. These represent the student groups that have already taken place in the past. You may not assume that every student was present in every day of groups—students are sometimes absent! For example, the following is a valid input (consisting of three days of groups) for a 13-person class:
{{1,2,3,4},{5,6,7},{8,9,10},{11,12,13}}
{{1,3,5,7},{9,11,13,2},{4,6,8,10}}
{{8,6,7,5},{3,10,9,13},{12,11,1}}
You may also include, if you wish, the number of students in the class (13 in this case) as an additional explicit input. Otherwise you may assume that the number of students equals the largest integer appearing in the input (assuming you 1-index as I am; for 0-indexed, the number of students equals 1 + the largest integer appearing in the input).
Output structure
The output will be a single day of groups, representing the chosen group assignments for the next day of groups, containing all of the students in the class. You may write a program, function, snippet, or other useful code to accomplish this, and take input and generate output in any reasonable way. The goal of the code is to generate a new day of groups with as small a "score" as possible, as described below.
Given an input (representing the past days of groups), the "score" of a proposed output (representing the new day of groups) is calculated as follows:
- For every pair of students who are in the same group, count how many times they have been together in groups before; that number (0 or more) is added to the score.
- For every student in a 3-person group, count how many times they have been in a 3-person group in the past; that number (0 or more) is also added to the score.
For example, suppose the input for a 7-student class is given by
{{1,2,3,4},{5,6,7}}
{{1,3,5,7},{2,4,6}}
For the proposed output
{{1,6,7},{2,3,4,5}}
the score would be calculated as follows:
- 1 and 6 have never been in the same group before, so +0 to the score
- 1 and 7 have been in the same group once before, so +1 to the score
- 6 and 7 have been in the same group once before, so +1 to the score
- 2 and 3 have been in the same group once before, so +1 to the score
- 2 and 4 have been in the same group twice before, so +2 to the score
- 2 and 5 have never been in the same group before, so +0 to the score
- 3 and 4 have been in the same group once before, so +1 to the score
- 3 and 4 have been in the same group once before, so +1 to the score
- 4 and 5 have never been in the same group before, so +0 to the score
- 1 has never been in a 3-student group before, so +0 to the score
- 6 has been in a 3-student group twice before, so +2 to the score
- 7 has been in a 3-student group once before, so +1 to the score
Therefore the total score for that proposed day of groups is 10.
However, that proposed day of groups is not optimal—several possible days of groups have a score of 8, including:
{{1,2,5,6},{3,4,7}}
Input/output size and runtime
You should assume that there are at least 6 students in the class, and you may assume that there are at most 30 students in the class. You may also assume that there will be at least 1 and at most 100 days of groups in the input.
Evaluation criteria
This challenge is popularity contest. While I can't control the votes of the population, to me the ideal solution will contain:
- code that computes an output day of groups with the minimal score possible given the input, not just one with a "good" score;
- code that runs quickly (for example, in 10 seconds or less on a class of size 20);
- a justification for why the code produces the minimal possible score;
- a link to an online implementation of the code.
Example inputs and outputs
Input #1:
{{1,2,3,4},{5,6,7,8},{9,10,11,12}}
Output #1: there are many configurations with a score of 3, one of which is:
{{1,2,5,9},{3,6,7,10},{4,8,11,12}}
Input #2:
{{1,2,3,4},{5,6,7,8},{9,10,11,12},{13,14,15}}
{{1,5,9,13},{2,6,10,14},{3,7,11,15},{4,8,12}}
{{1,8,10,15},{2,7,9},{3,6,12,13},{4,5,11,14}}
{{1,7,12,14},{2,8,11,13},{3,5,10},{4,6,9,15}}
Output #2, with a score of 0, is unique in this case (up to reordering within each list):
{{1,6,11},{2,5,12,15},{3,8,9,14},{4,7,10,13}}
Input #3:
{{1,2,3},{4,5,6},{7,8,9}}
{{1,2,4},{3,5,8},{6,7,9}}
{{1,5,6},{2,3,9},{4,7,8}}
{{1,6,8},{2,4,9},{3,5,7}}
{{1,3,7},{2,6,8},{4,5,9}}
{{1,8,9},{2,5,7},{3,4,6}}
{{1,4,7},{2,5,8},{3,6,9}}
Output #3, with a score of 72, is also unique (up to reordering):
{{1,5,9},{2,6,7},{3,4,8}}
