Combinatorial problem

Arrangements, combinations and permutations, probability, ...
Post Reply
User avatar
jaap
Posts: 525
Joined: Tue Mar 25, 2008 3:57 pm
Contact:

Re: Combinatorial problem

Post by jaap » Wed Sep 17, 2014 7:48 am

lopez25 wrote:You can not build the 5-uple 1-2-3-4-5 if at least one of the triplet 1-2-3 or 1-2-4 is missing.
I don't understand how you are building the 5-tuples.
If you are just taking the union of some triplets, then for example {1,4,5} and {2,3,4} build {1,2,3,4,5} without using either {1,2,3} or {1,2,4}.

Bubbler
Posts: 28
Joined: Sat Feb 23, 2013 6:12 am

Re: Combinatorial problem

Post by Bubbler » Thu Sep 18, 2014 4:09 am

The problem is a variation of Set Cover(http://en.wikipedia.org/wiki/Set_cover_problem) whose optimization is NP-hard:

Take the set S of combinations of 5 numbers from 1-10, which will have 252 elements in total.
Take a new set of subsets of S where each subset contains all reachable 5-combinations from each 3-combination, and call this set T.

For example, an element in T associated with {1,2,3} would look like:
{ {1,2,3,4,5}, {1,2,3,4,6}, ..., {1,2,3,5,6}, ..., {1,2,3,9,10} }, which has 21 elements.

Then the problem becomes to choose minimal number of sets in T that will cover all elements in S.

I think the answer (20) you got is quite reasonable, though I didn't try to prove or verify it yet.
Image

Post Reply