Cheers! This problem bothers me for a long time and I have no idea what is the solution and/or approach to it.
k-combinations formula is of course super-easy {n!/[k!*(n-k)!]}
but let's imagine this:
1) you have a set of N items
2) you have Y and Z where N>Y>Z
you can do both k-combination (N,Z) and (Y,Z) /by Y I mean any possible combination resulting from (N,Y)/
the question(s) being
What is the minimum number of subsets from N with the size Y to contain all possible (N,Z)? And how to find them?
Example:
N=5, Y=4, Z=3
(N,Z)=10
{123,124,125,134,135,145,234,235,245,345}
{1,2,3,4} as Y "covers" (Y,Z) {123,124,134,234}
remaining uncovered (N,Z) are {125,135,145,235,245,345}
{1,2,3,5} as Y "covers" (Y,Z) {125,135,235} /excluding duplicates/
remaining uncovered (N,Z) are {145,245,345}
{2,3,4,5} as Y "covers" (Y,Z) {245,345} /excluding duplicates/
remaining uncovered (N,Z) is {145}
so we can pick whatever as long as it contains 1,4 and 5.
=> even though (N,Y)=5, we need only 4 subsets of size Y from N to cover all (N,Z) by creating (Y,Z) from the selected subsets.
But this brute-force approach of course fails for larger numbers and gives no picture of the underlying logic.
k-combinations formula is of course super-easy {n!/[k!*(n-k)!]}
but let's imagine this:
1) you have a set of N items
2) you have Y and Z where N>Y>Z
you can do both k-combination (N,Z) and (Y,Z) /by Y I mean any possible combination resulting from (N,Y)/
the question(s) being
What is the minimum number of subsets from N with the size Y to contain all possible (N,Z)? And how to find them?
Example:
N=5, Y=4, Z=3
(N,Z)=10
{123,124,125,134,135,145,234,235,245,345}
{1,2,3,4} as Y "covers" (Y,Z) {123,124,134,234}
remaining uncovered (N,Z) are {125,135,145,235,245,345}
{1,2,3,5} as Y "covers" (Y,Z) {125,135,235} /excluding duplicates/
remaining uncovered (N,Z) are {145,245,345}
{2,3,4,5} as Y "covers" (Y,Z) {245,345} /excluding duplicates/
remaining uncovered (N,Z) is {145}
so we can pick whatever as long as it contains 1,4 and 5.
=> even though (N,Y)=5, we need only 4 subsets of size Y from N to cover all (N,Z) by creating (Y,Z) from the selected subsets.
But this brute-force approach of course fails for larger numbers and gives no picture of the underlying logic.