I have a set of n numbers (e.g. 1 to n). For the sake of clarity, in the remaining I will use n = 10.
From these 10 numbers there is $\binom{10}{3} = 120$ combinations of 3, for instance (1, 3, 5), (3, 5, 10),...
Every combination of 5 covers 10 combinations of 3, as $\binom{5}{3} = 10$. For instance (3, 6, 10, 4, 7) covers : (3, 6, 10), (3, 6, 4), (3, 6, 7), (3, 10, 4), (3, 10, 7), (3, 4, 7), (6, 10, 4), (6, 10, 7), (6, 4, 7) and (10, 4, 7).
What I am trying to do is to generate a set of combinations of 5, that cover all the combinations of 3 once. Since there is 120 combinations of 3 and each combination of 5 covers 10 combinations of 3, I assume that I can reach my goal with 12 combinations of 5 but I am still struggling to find a way to do that.
I tried a method, but it always fails as I keep ending up with more than 12 combinations of 5 and therefore some combinations of 3 being covered more than once. Here is the pseudo code that I used.
pool: set of numbers (here 1 to 10)
allComb3: list of all the (120) combinations of 3
uncoveredComb3: list of combinations of 3 not yet covered, this list is initially equal to allComb3. As combination of 3 get covered, this list shrinks until it is empty.
candidatesFor4th: for a given (not covered) combination of 3, this is a list of numbers such that when any of them is appended to the combination of 3, it forms a combination of 4, that covers (4) uncovered trinoms (those still found in uncoveredComb3)
candidatesFor5th: for a given combination of 4, this is a list of numbers such that when any of them is appended to the combination of 4, it forms a combination of 5 that covers (10) uncovered trinoms (those still found in uncoveredComb3)
while there are members of allComb3 not covered
for member in allComb3
if member is covered
go to next member
else
look for candidatesFor4th
if candidatesFor4th is not empty
Select randomly one number from candidatesFor4th to form a combination of 4: quadri
else
add a random number from pool\{member} to member to form a combination of 4: quadri
end if
look for candidatesFor5th
if candidatesFor5th is not empty
Select randomly one number from candidatesFor5th to form a combination of 5
else
add a random number from pool\{quadri} to quadri to form a combination of 5
end if
end if
end for
end while
Implementing this algorithm (in matlab) never led to hit the goal. For instance it can yield 19 combinations of 5 with some of the combinations of 3 covered 4 times, many others covered twice. Is there another way of solving this? Any suggestion on how to achieve this would be greatly appreciated. Thanks in advance.