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.
