Finding the smallest array that intersects with a set of arrays
Let's 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 the minimum number of elements, the array I would get would be ['b', 'd']
. My question is, how can I find this array?
Similar ['a', 'b', 'c', 'd']
, of course, intersects all arrays, but this is not the minimum intersection - ['b', 'd']
.
Any ideas?
source to share
I don't have a good answer for the algorithm, but it's true that, as commenter Amit wrote, this is an NP-complete problem. This problem is referred to as the hit set problem, which is equivalent to cover assignment .
If you're okay with the approximation, then, according to the wiki article, eagerly select elements that fall into most arrays about as good as you get.
source to share
I think you can try trying 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 scrolling, we find that [1,2,3,4]
- all values that match more than one array.
Now we have to determine if there are any values that we can exclude from this list.
If we exclude 1
, will everything match?
No, we need 1
.
If we exclude 2
, will everything match?
Yes, we can exclude 2
from the array. Now we have [1,3,4]
.
If we exclude 3
, will everything match?
No, we need 3
.
If we eliminate 4
, will everything match?
No, we need 4
.
Our final array [1,3,4]
.
It won't work if you have a completely unique array. To account for this, you can create a boolean array of all false values and set the values to true when the arrays match. Any value that is still false at the end, you will need to select a value from this array.
source to share