I suppose what you would have to do is this:
Starting with 400 students, loop through and select 100 students at random.
Then go through those 100 students and group then until you have 50 groups.
If you have 2 students who are together on the incompatibility list, flip them with another set at random, as described below:
1 & 2
v
^
3 & 4
3 & 2
1 & 4
If any of those 2 are on the incompatibility list, then repeat the process. Once everything is OK, then you've got your list.
Here's the script I made to accompany this concept:
PHP Code:
function onCreated()
{
this.start = timevar2;
this.incompatability = {
{102, 284},
{392, 126},
{1, 2},
{3, 4},
{5, 6},
{7, 8}
};
this.studentsSelected.clear();
this.studentGroups.clear();
numStudentsSelected = 0;
// Select students at random
for (i = 0; i < 100; i++)
{
f = int(random(0, 400));
if (this.studentsSelected.index(f) == -1)
{
this.studentsSelected.add(f);
} else
{
i--; continue;
}
}
// Group them
for (i = 0; i < this.studentsSelected.size(); i += 2)
{
this.studentGroups.add({this.studentsSelected[i], this.studentsSelected[i+1]});
}
// Remove incompatabilities
for (i = 0; i < 50; i++)
{
sGroup = this.studentGroups[i];
for (a = 0; a < this.incompatability.size(); a++)
{
if ((sGroup[0] == this.incompatability[a][0] || sGroup[0] == this.incompatability[a][1]) && (sGroup[1] == this.incompatability[a][0] || sGroup[1] == this.incompatability[a][1]))
{
echo("INCOMPATABILITY: " @ sGroup);
// we've found an incompatability, so lets flip this student with the next group
sGroup2 = this.studentGroups[i+1];
sGroup[0] = sGroup2[0];
}
}
}
this.end = timevar2;
echo(this.end - this.start);
for (i = 0; i < 50; i++)
{
echo("Group " @ (i+1) @ ": {" @ this.studentGroups[i][0] @ ", " @ this.studentGroups[i][1] @ "}");
}
}
Time taken: 0.002021789
Example Output:
PHP Code:
0.002021789
Group 1: {137, 114}
Group 2: {282, 284}
Group 3: {47, 288}
Group 4: {267, 53}
Group 5: {19, 329}
Group 6: {345, 299}
Group 7: {141, 228}
Group 8: {93, 50}
Group 9: {347, 390}
Group 10: {166, 207}
Group 11: {139, 41}
Group 12: {130, 336}
Group 13: {140, 376}
Group 14: {262, 238}
Group 15: {196, 0}
Group 16: {352, 79}
Group 17: {368, 151}
Group 18: {54, 387}
Group 19: {81, 108}
Group 20: {332, 380}
Group 21: {249, 160}
Group 22: {73, 300}
Group 23: {64, 66}
Group 24: {316, 204}
Group 25: {248, 24}
Group 26: {8, 111}
Group 27: {215, 396}
Group 28: {252, 148}
Group 29: {270, 240}
Group 30: {229, 378}
Group 31: {172, 209}
Group 32: {227, 333}
Group 33: {283, 127}
Group 34: {42, 194}
Group 35: {359, 302}
Group 36: {6, 292}
Group 37: {30, 293}
Group 38: {105, 374}
Group 39: {371, 324}
Group 40: {242, 119}
Group 41: {83, 348}
Group 42: {256, 158}
Group 43: {189, 128}
Group 44: {232, 389}
Group 45: {322, 191}
Group 46: {225, 197}
Group 47: {33, 334}
Group 48: {239, 121}
Group 49: {39, 213}
Group 50: {230, 29}
Probably not very efficient, but it works. I couldn't find any incompatibilities! XD
06-14-2008, 05:57 AM
Hybrid Mode
