finding the smallest array that intersects with a set of arrays

Question

Say I have three arrays - ['a', 'b'], ['b', 'c'] and ['d']. If I were to create a fourth array that intersects with these three arrays with a minimal number of elements the array I'd get would be ['b', 'd']. My question is... how would I go about finding this array?

Like ['a', 'b', 'c', 'd'] certainly intersects with all the arrays but it's not the minimal intersection - ['b', 'd'] is.

Any ideas?

Answer 1

I don't have a good answer for an algorithm, but it is true that, like commenter Amit wrote, this is an NP-complete problem. This problem is called the hitting set problem, which is equivalent to the set cover problem.

If you're fine with approximation, then according to the wiki article, greedily picking the elements that hit the most arrays as about as good as it gets.

Answer 2

I think what you might want to try is going through each array to grab values that match more than one array. Then once you have those values, determine which values you can remove from the array.

Example:

[1,2] [2,3] [2,4] [1,5] [3,7] [4,8]

After looping through, we find that [1,2,3,4] are all values which match in more than one array.

Now we must determine if there are any values we can eliminate from this list.

If we eliminate 1, will everything still match?

No, we need 1.

If we eliminate 2, will everything still match?

Yes, we can eliminate 2 from the array. Now we have [1,3,4].

If we eliminate 3, will everything still match?

No, we need 3.

If we eliminate 4, will everything still match?

No, we need 4.

Our final array is [1,3,4].

This will not work if you have a completely unique array. To account for this, you could create a boolean array of all false values and set values to true as you match arrays. Any value that is still false in the end, you would have to pick a value from that array.