4
$\begingroup$

I have a list of 6 elements (A...F) that I need to organize into the smallest number of unique two-element combinations (AB, AC, etc) possible so that they form all possible four-element combinations (AB + CD = ABCD). The order of the elements is unimportant and I can use each two-element combination as many times as possible (i.e. AB + CD, but also AB + EF)

I know that:

-There are fifteen possible 4-way combinations and -it should be solvable with 9 two-element combinations

...but I can't figure out conceptually how to generate my list of two-element combinations.

Any ideas on how I could get started on this?

$\endgroup$
6
  • $\begingroup$ If you just need this one case I would start with brute force. Write down all $15$ subsets of $4$ (in alphabetical order) and then play with breaking them down into pairs of pairs. $\endgroup$ Jul 30, 2019 at 15:56
  • $\begingroup$ That's been the strategy thus far, but it's proving a little more challenging than I thought! Also, I'd like to be able to develop at least a rudimentary area of how to approach it because I will have other similar problems like this to solve in the future. $\endgroup$
    – user640234
    Jul 30, 2019 at 16:01
  • $\begingroup$ Fair enough. I don't know where your "should be solvable with $9$" comes from. I have my doubts. Upvoting the question. $\endgroup$ Jul 30, 2019 at 16:04
  • $\begingroup$ Thanks, the idea was that each element would have to appear at least three times, but each each two-element set would count as two, so (6*3)/2 = 9. IT's quite possible that my logic is faulty here! $\endgroup$
    – user640234
    Jul 30, 2019 at 16:11
  • $\begingroup$ It isn't, I've got a nine pair solution, just writing down the reasoning. Lot of educated guess work though. $\endgroup$ Jul 30, 2019 at 16:12

3 Answers 3

2
$\begingroup$

Workable solution: $AB,\ AC,\ AD,\ EF,\ BC,\ BE,\ CF,\ DE$ and $ DF$.

This was mostly done by brute force but with some insights:

Every letter has to appear at least 3 times in one of the nine pairs. Suppose it did not and we only had $AB$ and $AC$, then $ADEF$ could not be formed. Since there are only $18$ letters in $9$ pairs this means that every letter has to appear exactly $3$ times.

This gives us a start with $AB$, $AC$ and $AD$. It follows we need $EF$. To make $ABCD$ we need to add $BC$, $CD$ or $EF$. Due to symmetry the choice is arbitratry so we can pick $BC$. The rest of the pairs have to contain either $E$ or $F$ to ensure those appear often enough, giving us $BE$, $CF$, $DE$ and $DF$.

$\endgroup$
1
  • $\begingroup$ this is amazing. Thanks so much! $\endgroup$
    – user640234
    Jul 30, 2019 at 16:30
1
$\begingroup$

Let's formalize your problem a little:

Given a Universe $U= \{A_1,...,A_n\}$, we're searching for the smallest $C\subseteq \binom{U}{2}$ so that $\binom U 4\subseteq P(C)$.

(Here, $\binom{U}{k} := \{M\subseteq U\mid |M| = k\}$ i.e. $\binom{U}{k}$ consists of all sets of $k$-element subsets of $U$.)

This already gives us a way to brute-force the whole thing:

  • Compute $P(\binom{U}{2})$, i.e. the set of all possible combinations of 2-element pairs
  • For each element $M\in P(\binom{U}{2})$, test $\binom{U}{4}\subseteq \{K\mid \ \exists S_1,S_2\in M: S_1\cup S_2 = K \}$
  • Choose the smallest $M$ that fulfills this test.

Note that this is the raw brute-force algorithm. There are many optimizations, both obvious and unobvious to improve this algorithm.

$\endgroup$
1
  • $\begingroup$ this is great. thanks so much! $\endgroup$
    – user640234
    Jul 30, 2019 at 16:31
1
$\begingroup$

You can solve this problem via integer programming as follows. Let binary variable $x_{ij}$ indicate whether pair $\{i,j\}$ (with $i < j$) is selected, and let binary variable $y_{i j k\ell}$ represent the product $x_{ij} x_{k\ell}$, where $\{i,j\} \cap \{k,\ell\} = \{\}$ and $i<k$. Let $Q = \{(i,j,k,\ell):i<j<k<\ell\}$. Then the problem is to minimize $\sum_{i,j} x_{ij}$ subject to \begin{align} y_{i j k\ell} &\le x_{ij} &&\text{for all } i,j,k,\ell\\ y_{i j k\ell} &\le x_{k\ell} &&\text{for all } i,j,k,\ell\\ \sum_{\{i',j',k',\ell'\}=\{i,j,k,\ell\}} y_{i'j'k'\ell'} &\ge 1 &&\text{for all } (i,j,k,\ell)\in Q \end{align} For $n = 6$, this minimum is 9. For general $n \ge 3$, the first several values match $n(n-3)/2$. Maybe one of the interpretations in OEIS entry A000096 applies.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .