0

I’m not sure how to ask this question or really what the correct terminology is.

I have 7 traits, {a, b, c, d, e, f, g}, and I have 12 items. Each of these items has a specific combination of these traits. I need to know which combinations of 3 items gets me all 7 traits. They are as follows:

1 = {a, b, e}

2 = {a, b}

3 = {a, c, d, e}

4 = {b, d, f}

5 = {b, d, g}

6 = {a, c, f}

7 = {a, c, g}

8 = {c, d, f}

9 = {b, e, g}

10 = {c, e, g}

11 = {d, f, g}

12 = {a, b, e}

I know there are 220 available combinations, so I’m not necessarily asking for anyone to list all possible solutions. If someone could offer some sort of formula or program I could use to find the possible solutions for myself, it would be highly appreciated.

Josh
  • 3
  • 1
    The generalized problem can be quite difficult and may be best described using graph theory. Given the manner in which you asked this question however, I expect the details will be too complex to bother going over. For small examples, brute force would probably be sufficient. Just write some code in your preferred programming language and check each possibility individually. – JMoravitz Mar 30 '22 at 14:15
  • For the generalized problem, see the Set Cover Problem which is known to be NP-Complete or other related covering problems such as that of finding an edge cover. – JMoravitz Mar 30 '22 at 14:18
  • Do you want the list of all possible unions of these subsets that are equal to ${a,b,c,d,e,f,g}$ with possible overlap (for example $a$ present twice ?) – Jean Marie Mar 30 '22 at 14:31

1 Answers1

1

As alluded to already in the comments, this is related to the Set Cover Problem which is NP-Complete. You however aren't interested in the smallest and are instead interested in all outcomes using three sets whose union is the universe.

Smaller example in javascript:

opts = ['abe','ab','acde','bdf','bdg','acg'];
letters = 'abcdefg';
for(a=0;a<opts.length;a++){for(b=a+1;b<opts.length;b++){for(c=b+1;c<opts.length;c++){
   word = opts[a]+opts[b]+opts[c];
   flag=true;
   for(i=0;i<letters.length;i++){
       if(!word.includes(letters[i])){flag=false;break;}}
   if (flag){console.log(''+(a+1)+(b+1)+(c+1)}
}}}

This output the following: 146,345,346

For instance 146 corresponds to

$$\{a , b , e\}\cup \{b,d,f\}\cup \{a,c,g\}=\{a,b,c,d,e,f,g\}$$

The above can of course be modified to accept a generic collection of sets and a generic number of sets you are allowed to combine, etc... It could surely be optimized and the output cleaned up, but for small examples with only a few hundred combinations it will run instantly regardless.

JMoravitz
  • 79,518