Method to generate group division which is unique over multiple levels

Often I'm challenged to find unique group divisions to run my experiments. Up till now I always succeeded by looping a random generator to generate such a division. However since quantities get bigger, this does not seem to work anymore.

The problem I'm trying to solve: Each level there are 12 elements which should be divide in 4 groups (3 elements per group). There are 5 levels. The objective is that the division is unique in the way that over the 5 different levels, each element never meets another element more than once.

Example:

elements = [1:12];

• groups for level 1: [1 2 3]; [4 5 6]; [7 8 9]; [10 11 12];
• groups for level 2: [4 2 12]; [7 5 3]; [10 8 6]; [1 11 9];

Looking over these 2 different levels, each element never meets another element more than once, because:

• element 1 meets [2 3 9 11]
• element 2 meets [1 3 4 12]
• element 3 meets [1 2 5 7]
• ...

So over n levels, each element meets 2*n different elements. Over 5 levels, each element would meet 10 other elements, which is theoretically possible as there are in total 12 elements.

Does anybody has a suggestion how to generate an unique set over 5 levels?

Answer 1

[Roger Stafford]

It is easy to show that if you have found a five-level solution to your intriguing problem, you can apply any permutation to the elements and as long as it is the same permutation for each level, the result will also be a solution. For that reason you can, without loss of generality, restrict yourself to a level 1 grouping which is always the same as that you have given in your example: (1,2,3), (4,5,6), (7,8,9), and (10,11,12).

Altogether there are 12!/3!/3!/3!/3!/4! = 15400 different possible groupings of 12 elements into four sets of three each. Based on some trials with 'randperm' I estimate that only about 8.5 percent of these will be such that none of the 12 pairings in them are the same as any of the 12 pairings of the above fixed level 1 grouping. This would mean that there are only roughly thirteen hundred different sets of groupings possible for each of the the remaining four levels. For the sake of this discussion let us assume that the number is exactly 1300.

Skipping over the necessary code to achieve the following, it is quite reasonable to obtain a logical array, call it L, with (about) 1300 rows and 54 columns which consists of all the above groupings which are compatible with the fixed level one grouping - that is, no element is a member of two groups. The 54 columns correspond to all the possible pairings exclusive of the 12 that occur in level 1. For each possible grouping the elements of its row should be true for the positions of the 12 pairings that occur in that grouping and false for all others.

Such a logical array can then be used to obtain all possible solutions for the four remaining level groupings using four nested for-loops.

 N = size(L,1);
 for k1 = 1:N-3
   r1 = L(k1,:);
   for k2 = k1+1:N-2
     r2 = L(k2,:);
     if ~any(r1&r2)
       r2 = r1|r2;
       for k3 = k2+1:N-1
         r3 = L(k3,:);
         if ~any(r2&r3)
           r3 = r2|r3;
           for k4 = k3+1:N
             r4 = L(k4,:);
             if ~any(r3&r4)
               % If this point is reached, we have found a solution
               % The k1,k2,k3,k4 values should be stored somewhere
             end
           end
         end
       end
     end
   end
 end

It is this set of nested for-loops that will require the most computation time, and it will undoubtedly be an extended time. However, note that though execution will enter the second for-loop for each value of k1, it will enter the third loop for only a fraction of the k2 values, and of these only a very tiny fraction of the k3 will enter the fourth loop. It remains to be seen if any solutions at all will be found within this fourth loop. For this reason the execution time may not be as long as might be thought at first sight of this deeply nested code along with the size of N.

Whatever solutions are found can be said to be all that are possible with the understanding that, as mentioned above, all other solutions can be obtained by like permutations of the elements of all five levels of groupings and by permutations among the five levels themselves.

[Roger Stafford]

In the above I neglected to mention that matlab's 'nchoosek' function can be used to assist in generating the L array I described. It takes just three calls to 'nchoosek', one for three out of twelve things, one for three out of nine things, and one for three out of six things. To get an idea of the technique used you can refer to:

 http://www.mathworks.com/matlabcentral/answers/112670

[John Woods]

Thanks a lot Roger !!!