Geek asks and answers

For N sets of elements, we find the minimal union of the sets M

Given the recipe as a set of ingredients, I try to find the minimum ingredients that make a week on food. This leads to the above problem: N is the number of recipes and M = 7.

eg. if the initial sets are [{1,2}, {2,3}, {1,2,3}, {1}, {2}], and M=3
The minimal union is {1,2}.

I am looking for high-level approaches to solve this problem. I feel this can be reduced to BFS, but I want other approaches to make it optimal as well.

Note: there may be several such sets with the same power.

+5
source share
1 answer

This problem is known as MINIMUM k-UNION, and it is NP-hard , as shown below:

, , .

, , : , . : , , . Python:

def small_union(sets, k):
    """
    Choose `k` elements from `sets` and return their union.  Attempt
    to return a fairly small union using a greedy approach.

    >>> small_union([{1,2}, {2,3}, {1,2,3}, {1}, {2}], 3)
    set([1, 2])
    >>> small_union([{1,2}, {2,3}, {3,4}, {1,4}], 3)
    set([1, 2, 3, 4])
    """
    union = set()
    for _ in xrange(k):
        s = min(sets, key = lambda s: len(s | union))
        sets.remove(s)
        union |= s
    return union
+5

More articles:


All Articles