0

I stumbled upon a maths problem wich I need To solve for a current paper I am writing. Have you seen this before? Is it solved and more concretely is there an efficient algorithm for this problem? If there is any paper you can direct me to I`d be glad. Here is the Problem: Suppose you have a set of N Elements. Construct all Subsets with exactly 2 Elements. Using every subset exactly once, construct (N-1) sets where all N original elements are present.

Example: {A, B, C, D} Original Set {A, B}, {A, C}, {A, D} ,{B, C}, {B, D}, {C, D} All Subsets with two elements {{A, B}, {C, D}}, {{A, C}, {B, D}}, {{A, D}, {B, C}} final solution

While this Problem seem trivial for small N it becomes tedious quickly.

Thanks for your help!

Jean Marie
  • 81,803
Constantin Economides
  • 1

1 Answers1

1

The initial "set representation" of your question with its constraints can be transformed into an equivalent, more classical, "array representation" (strictly upper triangular arrays) with more easily handled constraints (no column, no line contains more than once a given element).

This transformation

  • allows a clearer understanding of the issue and its constraints.

  • allows to consider approaches that have been used in similar problems.

  • finally allows to make a connection with a classical issue, round robin tournaments. .

First of all, instead of using letters, let us use indices ; for example, the three partitions:

$$\begin{cases} p_1: &\{\{A, B\}, \{C, D\}\}\\ p_2: &\{\{A, C\}, \{B, D\}\}\\ p_3: &\{\{A, D\}, \{B, C\}\} \end{cases},$$

will be considered as a set of "boxes" in an array with matrix conventions:

$$\begin{cases} \text{partition} \ p_1:& (1,2),(3,4),\\ \text{partition} \ p_2:& (1,3),(2,4),\\ \text{partition} \ p_3:& (1,4),(2,3)\end{cases} $$

This information is entirely captured in this strictly upper triangular matrix:

$$M=\begin{array}{|c|c|c|c|c|}\hline &1&2&3&4\\ \hline 1&&\color{red}{p_1}&p_3&p_2\\ \hline 2&&&p_2&p_3\\ \hline 3&&&&\color{red}{p_1}\\ \hline 4&&&&\\ \hline \end{array}$$

(for example, partition $p_1$ can be retrieved by matrix indices $M_{(1,2)}$ and $M_{(3,4)}$ of the two boxes - in red - where one finds $"p_1"$).

In order to be more concise, we will write the previous matrix under the following form:

$$\begin{array}{|c|c|c|c|c|}\hline &\textit{1}&\textit{2}&\textit{3}&\textit{4}\\ \hline \textit{1}&&1&3&2\\ \hline \textit{2}&&&2&3\\ \hline \textit{3}&&&&1\\ \hline \textit{4}&&&&\\ \hline \end{array}$$

This was for a set of $N=4$ elements with $N-1=3$ partitions.

Let us consider now the next case : $N=6$. Here is a possible repartition (with the same conventions):

$$\begin{array}{|c|c|c|c|c|c|c|}\hline &\textit{1}&\textit{2}&\textit{3}&\textit{4}&\textit{5}&\textit{6}\\ \hline \textit{1}&&1&3&4&5&2\\ \hline \textit{2}&&&2&5&3&4\\ \hline \textit{3}&&&&1&4&5\\ \hline \textit{4}&&&&&2&3\\ \hline \textit{5}&&&&&&1\\ \hline \textit{6}&&&&&&\\ \hline \end{array}$$

The filling has been done "by hand" with the constraint that one must not have the same figure in a same line or in a same column.

I realized (a day later) that this issue is in fact plainly a round robin tournament for which there exists a classical algorithm very well "captured" in the following graphical representation (corresponding to the case $N=10$) that one finds in the upsaid Wikipedia article:

enter image description here

with the corresponding array :

$$\begin{array}{|c|c|c|c|c|c|c|c|c|c|}\hline &\textit{1}&\textit{2}&\textit{3}&\textit{4}&\textit{5}&\textit{6}&\textit{7}&\textit{8}&\textit{9}&\textit{10}\\ \hline \textit{1}&&6&2&7&3&8&4&9&5&1\\ \hline \textit{2}&&&7&3&8&4&9&5&1&2\\ \hline \textit{3}&&&&8&4&9&5&1&6&3\\ \hline \textit{4}&&&&&9&5&1&6&2&4\\ \hline \textit{5}&&&&&&1&6&2&7&5\\ \hline \textit{6}&&&&&&&2&7&3&6\\ \hline \textit{7}&&&&&&&&3&8&7\\ \hline \textit{8}&&&&&&&&&4&8\\ \hline \textit{9}&&&&&&&&&&9\\ \hline \textit{10}&&&&&&&&&&\\ \hline \end{array}$$

(the entries are now interpreted as being the $1st, 2nd, \cdots 9th$ competition days: for example, value $1$ is taken by the $N/2$ entries $M_{1,10}, M_{2,9}, M_{3,8},M_{4,7},M_{5,6}$).

Here is a very simple Matlab program implementing these ideas in order to create arrays of the type seen upwards:

   clear all;
   N=10;% must be even
   n=N/2;p=N-1;
   T=zeros(N);
   for i=1:p ; % row index 
       for j=i+1:p ; % column index
             s=i+j; % according to evenness of s:
             if mod(s,2)==0
                 T(i,j)=s/2;
             else
                 T(i,j)=mod((s+p)/2,p);
             end;
             if s==p;
                 T(i,j)=p;
             end;
       end
   end
   % separate creation of the last column:
   for i=1:p
       T(i,N)=i;
   end;
   T

Remark : the number of occupied entries in a strict upper triangular matrix $N \times N$ (where $N$ must be even) is $(N-1) \times N/2$. This explains the fact that we need exactly $(N-1)$ partitions having each $N/2$ classes (this was mysterious for me at first). For example, when $N=10$, we have $N-1=9$ partitions (aka competition days) $d_1,d_2,\cdots d_9$, each one with $N/2=5$ "instances".

Jean Marie
  • 81,803