Expert: Josh - 4/11/2009

Question
We have six golf teams in our conference, and in matches all six teams play together, with three players in each group. In each match we pair up different schools (1,2,3,4,5,6).

We want to have the combinations so that we play with each school and equal, or close to equal number of times.

For instance, in the first match of the year the pairings would be as follows(where each school is represented by a number):

Schools 1  2  3 play together
Schools 4  5  6 play together

Above would be the pairings for the first match.  We play six matches.  What would the other pairings be to maximize the combinations.

Thanks.

Answer
Bob,

You guys are terrible (tongue in cheek) always give me these complex problems to work on. I think a fitting punishment is to make you read what is to follow. Just kidding...

Honestly, this type of problem is notoriously difficult to answer. If the size of the problem is any bigger, we may have no hope of finding a solution as simulation would take forever to run. Luckily this approach is feasible for this particular problem.

In brief, here is one possible playing schedule.

%The following shows your playing partners for each day
%    1 2 3 4 5 6 (Day 1) Grouping:{1,2,3} {4,5,6}
%  -------------
%1 | 0 1 1 0 0 0
%2 | 1 0 1 0 0 0
%3 | 1 1 0 0 0 0
%4 | 0 0 0 0 1 1
%5 | 0 0 0 1 0 1
%6 | 0 0 0 1 1 0

%    1 2 3 4 5 6 (Day 2) {1,2,4} {3,5,6}
%  -------------
%1 | 0 1 0 1 0 0
%2 | 1 0 0 1 0 0
%3 | 0 0 0 0 1 1
%4 | 1 1 0 0 0 0
%5 | 0 0 1 0 0 1
%6 | 0 0 1 0 1 0

%    1 2 3 4 5 6 (Day 3) {1,2,6} {3,4,5}
%  -------------
%1 | 0 1 0 0 0 1
%2 | 1 0 0 0 0 1
%3 | 0 0 0 1 1 0
%4 | 0 0 1 0 1 0
%5 | 0 0 1 1 0 0
%6 | 1 1 0 0 0 0

%    1 2 3 4 5 6 (Day 4) {1,3,4} {2,5,6}
%  -------------
%1 | 0 0 1 1 0 0
%2 | 0 0 0 0 1 1
%3 | 1 0 0 1 0 0
%4 | 1 0 1 0 0 0
%5 | 0 1 0 0 0 1
%6 | 0 1 0 0 1 0

%    1 2 3 4 5 6 (Day 5) {1,5,6} {2,3,4}
%  -------------
%1 | 0 0 0 0 1 1
%2 | 0 0 1 1 0 0
%3 | 0 1 0 1 0 0
%4 | 0 1 1 0 0 0
%5 | 1 0 0 0 0 1
%6 | 1 0 0 0 1 0

%    1 2 3 4 5 6 (Day 6) {3,4,6} {1,2,5}
%  -------------
%1 | 0 1 0 0 1 0
%2 | 1 0 0 0 1 0
%3 | 0 0 0 1 0 1
%4 | 0 0 1 0 0 1
%5 | 1 1 0 0 0 0
%6 | 0 0 1 1 0 0

%=========================
%Now, comes the punishment that I promised.
%You should see what you have put me through
%Below is a MATLAB script that I used to answer your question.

%form groups of 3 from 6
N=6; count=1;
for i=1:N-2
 for j=i+1:N-1
   for k=j+1:N
     X(count,:)=[i,j,k]; count=count+1;
   end
 end
end
%X=
%1,2,3
%1,2,4
%1,2,5
%1,2,6
%1,3,4
%1,3,5
%1,3,6
%1,4,5
%1,4,6
%1,5,6
%2,3,4
%2,3,5
%2,3,6
%2,4,5
%2,4,6
%2,5,6
%3,4,5
%3,4,6
%3,5,6
%4,5,6
    
%find complementary groupings
Y=X(end:-1:1,:);
%same as X written from bottom up

%calculate the number of possible selections when we are
%interesting in choosing 6 of the 20 groups (without
%any additional constraint) 20!/(6!14!) equals
combo=2.43290200817664e+018/(720*87178291200);%38760

%enumerate each possible combination with indices.
%for example (1,2,4,6,8,16) refers to {X(1),X(2),X(4),X(6),X(8),X(16)}
%a schedule over six days. In particular, indexing the 4th entry in
%the X, Y lookup tables, we form the groups {1,2,6} and {3,4,5}
%on day three. The co-occurence matrix typically looks something like this
%    1 2 3 4 5 6
%  -------------
%1 | 0 3 3 3 0 3
%2 | 3 0 2 2 3 2
%3 | 3 2 0 2 3 2
%4 | 3 2 2 0 3 2
%5 | 0 3 3 3 0 3
%6 | 3 2 2 2 3 0
   
%The average number of encounters per person is always 2.4,
%but the standard deviation for each person might be different.
%The idea is to find one arrangement out of 38760 combinations
%which has the smallest spread. We can impose additional
%constraints on the maximum and minimum number of encounters
%to be no more than (respectively no less than) "x".

%Obviously, if the combinatorial problem is any bigger, we
%have little hope of doing this in reasonable time.
N=20; p=6; count=1;
for i=1:N-p+1
 for j=i+1:N-4
   for k=j+1:N-3
     for l=k+1:N-2
       for m=l+1:N-1
         for n=m+1:N
           Z(count,:)=[i,j,k,l,m,n]; count=count+1;
         end
       end
     end
   end
 end
end
B=zeros(combo,p);%matrix for average encounters
C=zeros(combo,p);%matrix for standard deviation in encounters
Max=zeros(combo,p);%max encounters
Min=zeros(combo,p);%min encounters
k=1/(p-1);%normalization factor for occupancy (occurrence) matrix
for i=1:size(Z,1)
 A=zeros(6,6);%occupancy matrix
 for m=1:6 %day
   tmp=X(Z(i,m),:); a=tmp(1); b=tmp(2); c=tmp(3);
   tmp=Y(Z(i,m),:); d=tmp(1); e=tmp(2); f=tmp(3);
   A(a,b)=A(a,b)+1; A(b,a)=A(b,a)+1;
   A(a,c)=A(a,c)+1; A(c,a)=A(c,a)+1;
   A(b,c)=A(b,c)+1; A(c,b)=A(c,b)+1;
   A(d,e)=A(d,e)+1; A(e,d)=A(e,d)+1;
   A(d,f)=A(d,f)+1; A(f,d)=A(f,d)+1;
   A(e,f)=A(e,f)+1; A(f,e)=A(f,e)+1;
 end
 %disp(sprintf('(%d,%d,%d),(%d,%d,%d)',a,b,c,d,e,f))
 %A
 B(i,:)=k*sum(A');
 C(i,1)=k*sum((A(1,:)-B(i,1)).^2);
 C(i,2)=k*sum((A(2,:)-B(i,2)).^2);
 C(i,3)=k*sum((A(3,:)-B(i,3)).^2);
 C(i,4)=k*sum((A(4,:)-B(i,4)).^2);
 C(i,5)=k*sum((A(5,:)-B(i,5)).^2);
 C(i,6)=k*sum((A(6,:)-B(i,6)).^2);
 Max(i,:)=max(A');
 AA=A; AA(1,1)=p+1; AA(2,2)=p+1; AA(3,3)=p+1;
       AA(4,4)=p+1; AA(5,5)=p+1; AA(6,6)=p+1;
 Min(i,:)=min(AA');
end

%some statistics about the spread in mean encounters per person
%averaged over time (6 days)
%S.D. >> max: 4.992 min: 1.392
%number of encounters >> max: 6 min: 0

%find candidate groupings with no. of encounters between 2 and 3
idx1=find(max(Max')<=3); %there are 960
idx2=find(min(Min')>=2); %there are 960
%find combinations where both constraints are satisfied
count=1; L=length(idx1); compare=zeros(L,1);
for i=1:L
 compare(i)=~isempty(find(idx2==idx1(i)));
 if(compare(i))
   idx(count)=idx1(i); count=count+1;
 end
end
%unfortunately, there are no solutions
%i.e., not possible to form groups where the number of
%encounters is strictly between 2 and 3, let us relax the
%constraints, allowing maximum no. of encounters to be <=4
idx1=find(max(Max')<=4); %there are now 28980
count=1; L=length(idx1); compare=zeros(L,1);
for i=1:L
 compare(i)=~isempty(find(idx2==idx1(i)));
 if(compare(i))
   idx(count)=idx1(i); count=count+1;
 end
end
%it turns out there are 960 out of 38760 combinations
%with this property. next, we find amongst these, the
%ones with the least mean spread
[sol, val]=min(mean(C(idx,:)'))
%it turns out they all have the same average spread of 1.792
%(averaged over all players within the group)
%so, the solution is not unique...many groupings have similar
%statistical properties, let us pick one from idx(k), where
%k<=960...say k=25, idx(25)=738th entry w.r.t. Z

%Z(738) selects #1, #2, #4, #5, #10 and #18 from the earlier
%X, Y combinations which put 3 in a group,
%
%Day 1: X(1)={1,2,3} Y(1)={4,5,6}
%Day 2: X(2)={1,2,4} Y(2)={3,5,6}
%Day 3: X(4)={1,2,6} Y(4)={3,4,5}
%Day 4: X(5)={1,3,4} Y(5)={2,5,6}
%Day 5: X(10)={1,5,6} Y(10)={2,3,4}
%Day 6: X(18)={3,4,6} Y(18)={1,2,5}
%
%Let's verify the properties from the co-occurence matrix
%This shows the number of encounters after 6 days between
%player i and j
%
%    1 2 3 4 5 6
%  -------------
%1 | 0 4 2 2 2 2
%2 | 4 0 2 2 2 2
%3 | 2 2 0 4 2 2
%4 | 2 2 4 0 2 2
%5 | 2 2 2 2 0 4
%6 | 2 2 2 2 4 0

%This matrix is obtained by adding all 6 matrices I have given you in
%the beginning.