[SOLVED]Get a minimal set whose elements hit all input sets?

[allfox]

Hello,

It's a question about algorithm.
I have some arrays. Each array contains at most 8 values. Each value could be a number in 0 to 7. No dumplicate value in a single array.
Example input for 4 arrays: { [1, 2, 3], [3, 4], [3, 4], [5] }
I want to get a minimal set whose elements hit every input array.
Example output: {3, 5}
3 hits [1, 2, 3] and [3, 4], 5 hits [5], so all input arrays have been hit.

How could I get this minimal hit set?

It's not that much about Pi though.....thanks for any help.

[jamesh]

Google for set intersection algorithms.

[jojopi]

I do not think this is a simple problem. Consider the input { [1,2], [1,2], [1,2], [1,3], [1,3], [1,3], [2,3] }. "1" appears in nearly all the arrays, yet the best solution is {2, 3}.

I think it is a problem in combinatorial optimization. The known optimal algorithms tend to be exponential in problem size, so the best algorithm in practice is to try solutions semi-randomly until you find one that is "good enough".

With the restriction to the integers 0…7 there are only 256 possible solutions, so you can just try them all, in order of cost.

[plugwash]

I do not think this is a simple problem. Consider the input { [1,2], [1,2], [1,2], [1,3], [1,3], [1,3], [2,3] }. "1" appears in nearly all the arrays, yet the best solution is {2, 3}.

Maybe i'm missing something but aren't [1,2] [1,3] and [2,3] all equally good soloutions to that one?

[jojopi]

Maybe i'm missing something but aren't [1,2] [1,3] and [2,3] all equally good soloutions to that one?

Yes, you are right. Let me try: { [1,2], [1,2], [1,2], [1,3], [1,3], [1,3], [2,4], [3,5] }.

[plugwash]

The known optimal algorithms tend to be exponential in problem size

Though with something like this we have to be careful about what we mean by "problem size" since the size of the problem can expand in several dimensions. Number of sets, size of the sets, number of unique elements across all sets.

For example consider the following algorithm (psuedocode)

Code: Select all

Sort the input sets by size, assume this sorting is a negligable part of the process.
Take the smallest set in the input and loop through the values in it.
  For each set in the input determine whether it is satisfied
  Recurse with the set of sets that is not satisfied.
end loop

This would in the worst case be of exponential complexity with the number of sets but only polynomial complexity with increasing set size.

On the other hand you could brute force starting with the smallest possible sets and gradually working up to larger sets. In the worst case this would be linear in the number of sets but exponential in terms of the number of unique elements.

[allfox]

Thank you very much!

I think the number of unique elements won't grow in near future. So I'll try brute fource method to write a breadth first search program.