Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
953 views
in Technique[技术] by (71.8m points)

algorithm - Given N sets of elements, find minimal union of M sets

Given a recipe as a set of ingredients, I am trying to find minimum ingredients that make a week worth of meals. This translates to the above problem, with N as 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. I feel this can be reduced to a BFS, but I want to see if other approaches could also make it optimal.

Note: There might be multiple such sets, with same cardinality.

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

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

So no-one knows any algorithm to solve it that runs in time that's polynomial in the size of the input.

In your case, you would probably be happy to accept an approximate solution: that is, a collection of recipes with a small union of ingredients, but not necessarily the very smallest such collection. So I suggest that you try the greedy algorithm: iteratively build up a collection of recipes by adding at each stage the recipe that minimizes the size of the union. Here's a na?ve implementation in 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

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...