Partitioning into groups with maximal mixing

Question

Suppose I have a class of 30 students and I want to give them 8 assignments to do in groups of 3. As far as possible I'd like the students to work with as many different students as possible. Ideally no two students would work with each other on more than one assignment.

In general I'd like to solve this for $n$ students in groups of size $k$ for $m$ assignments. I'd like pointers to when it is possible and suggestions for how to write a program to generate groups for a given list of students, assignments and group sizes.

Answer 1

Keywords here are "block design", "Steiner triple system" and "resolvable".

We want to find $8$ resolution classes: each partitioning $\{1,2,\ldots,30\}$ into $10$ sets of size $3$. This is going to be an ugly case, since $30 \not\equiv 1,3 \pmod 6$ (a condition for the existence of a Steiner triple system). [The question would be more mathematically interesting if you expel $3$ students from your class.]

Since any particular student partners with $2$ others for each test, we can't have more than $\lfloor (30-1)/2 \rfloor=14$ tests. I think, though, we'd be quite likely to succeed in finding $8$ tests by randomly searching.

Coincidentally, I just happen to have code left over from answering this question. It found a random $12$-test family:

[[1,2,3],[4,5,6],[7,8,9],[10,11,12],[13,14,15],[16,17,18],[19,20,21],[22,23,24],[25,26,27],[28,29,30]]
[[1,4,8],[2,5,14],[3,7,15],[6,9,11],[10,16,22],[12,13,26],[17,20,25],[18,23,29],[19,27,28],[21,24,30]]
[[1,5,10],[2,6,7],[3,4,12],[8,11,13],[9,14,24],[15,19,29],[16,21,25],[17,26,28],[18,22,30],[20,23,27]]
[[1,6,17],[2,8,23],[3,5,18],[4,13,21],[7,22,28],[9,12,16],[10,26,30],[11,27,29],[14,19,25],[15,20,24]]
[[1,7,24],[2,11,15],[3,14,16],[4,18,25],[5,20,26],[6,19,30],[8,10,27],[9,21,22],[12,23,28],[13,17,29]]
[[1,11,14],[2,22,26],[3,10,24],[4,16,27],[5,13,30],[6,15,23],[7,12,25],[8,17,19],[9,20,29],[18,21,28]]
[[1,12,29],[2,13,28],[3,19,26],[4,9,10],[5,17,22],[6,14,21],[7,11,20],[8,15,16],[18,24,27],[23,25,30]]
[[1,13,23],[2,25,29],[3,8,28],[4,19,22],[5,7,16],[6,12,18],[9,17,27],[10,15,21],[11,24,26],[14,20,30]]
[[1,15,27],[2,12,21],[3,13,22],[4,11,30],[5,9,28],[6,10,25],[7,26,29],[8,18,20],[14,17,23],[16,19,24]]
[[1,16,30],[2,10,17],[3,21,27],[4,7,14],[5,24,29],[6,13,20],[8,12,22],[9,19,23],[11,25,28],[15,18,26]]
[[1,18,19],[2,4,24],[3,6,29],[5,11,23],[7,10,13],[8,21,26],[9,15,25],[12,17,30],[14,22,27],[16,20,28]]
[[1,20,22],[2,27,30],[3,11,17],[4,15,28],[5,12,19],[6,16,26],[7,21,23],[8,24,25],[9,13,18],[10,14,29]]

My code basically attempts to extend the list by (a) creating a list of legal "triples", and (b) picks $10$ at random that don't clash. It keeps trying until it gets bored (I set it at $1000$ attempts), then backtracks and makes another random attempt. If we get enough rounds, the code switches to an exhaustive backtracking algorithm.

In some special cases, there's elegant constructions (in the sense of design theory). In general, it won't be so nicely behaved.

---

Here's my GAP code. I didn't attach it previously since it wasn't intended to be made public. It's not particularly neat nor optimized (and I've assumed the user would be able to edit it). It should be saved as a file and Read into GAP.

# S = scheme (all rounds)  A = arrangement (single round)  T = table (one table, one round)

ArrangementNoClash:=function(T_cand,S_curr)
  return not ForAny(S_curr,A->ForAny(A,T->Size(Intersection(T,T_cand))>1));
end;;

CompleteSBacktracking:=function(S,A,T_poss)
  local T,A_new,S_new,i,T_poss_new;
  for i in [1..Size(T_poss)] do
    T:=T_poss[i];
    A_new:=Concatenation(A,[T]);
    if(Size(A_new)=10) then
      S_new:=Concatenation(S,[A_new]);
      S_new:=SortedList(S_new);
      if(Size(S_new)>Size(S_best)) then S_best:=S_new; fi;
      Print("backtrack: S: ",Size(S_new)," (best=",Size(S_best),") ",S_new,"\n");
      T_poss_new:=Filtered(Combinations([1..30],3),Q->ArrangementNoClash(Q,S_new));
      if(not ForAny([1..30],i->Number(T_poss_new,T->i in T)=0)) then
        CompleteSBacktracking(S_new,[],T_poss_new);
      fi;
    else
      T_poss_new:=Filtered(T_poss,Q->Position(T_poss,Q)>i and Intersection(T,Q)=[]);
      CompleteSBacktracking(S,A_new,T_poss_new);
    fi;
  od;
end;;

nr_tries:=1000;

ExtendSRandom:=function(S,T_poss)
  local i,t,A_new,S_new,T_poss_filt,try;

  A_new:=[];
  try:=0;
  while(true) do
    try:=try+1;
    T_poss_filt:=T_poss;
    for t in [1..10] do
      if(t>1) then T_poss_filt:=Filtered(T_poss_filt,T->Intersection(T,A_new[t-1])=[]); fi;
      if(Size(T_poss_filt)=0) then break; fi;
      A_new[t]:=Random(T_poss_filt);
    od;
    if(Size(A_new)=10) then break; fi;
    if(try=nr_tries) then return 0; fi;
  od;

  S_new:=Concatenation(S,[SortedList(A_new)]);
  S_new:=SortedList(S_new);
  if(Size(S_new)>Size(S_best)) then S_best:=S_new; fi;
  Print("random: S: ",Size(S_new)," (best=",Size(S_best),") ",S_new,"\n");
  T_poss_filt:=Filtered(T_poss,T->ArrangementNoClash(T,S_new));
  if(not ForAny([1..30],i->Number(T_poss_filt,T->i in T)=0)) then
    if(Size(S_new)=7) then
      CompleteSBacktracking(S_new,[],T_poss_filt);
    else
      ExtendSRandom(S_new,T_poss_filt);
    fi;
  fi;
end;;

VerifyArrangement:=function(S)
  local A,A2,i,j,T1,T2;
  for A in S do
    if(Union(A)<>[1..30]) then return false; fi;
  od;
  A2:=Concatenation(S);
  for i in [1..Size(A2)] do
    T1:=A2[i];
    for j in [i+1..Size(A2)] do
      T2:=A2[j];
      if(Size(Intersection(T1,T2))>=2) then
        return false;
      fi;
    od;
  od;
  return true;
end;;

A_basic:=List([1..30/3],i->List([1..3],j->3*(i-1)+j));
S:=[A_basic];;
VerifyArrangement(S);
T_poss:=Combinations([1..30],3);;
T_poss:=Filtered(T_poss,T->ArrangementNoClash(T,S));;
S_best:=S;

while(true) do
  ExtendSRandom(S,T_poss);
od;