CODEWITHSUNDEEP
algorithmsetintersectionbrute-force
Eddie Jamsession
Eddie Jamsession

Reputation: 1006

Maximal sets intersection

Given 5 finite sets a,b,c,d,e. Each set is assigned the arbitrary number:

a = 100, b = 34, c = 15, d = 89, e = 57

complement of each set has the same number assigned but negated e.g. for (a') it will be -100.

We need to find such intersection of these all sets or their complements so the resulting set is not null set, and the sum of the assigned numbers is maximal.

I only see one brute force solution to this problem, but it will be very inefficient and it's not elegant. In this case we just generate all combinations and resolve them to see if they are not empty, combinations look like this:

{a∩b'∩c'∩d'∩e'}, {a'∩b∩c'∩d∩e'}, {a'∩b'∩c∩d'∩e'}, {a'∩b'∩c'∩d∩e'}, {a'∩b'∩c'∩d'∩e} {a∩b∩c'∩d'∩e'}, {a∩b'∩c∩d'∩e'}, {a∩b'∩c'∩d∩e}, {a∩b'∩c'∩d'∩e}, {a'∩b∩c∩d'∩e'} {a'∩b∩c'∩d∩e'} {a'∩b∩c'∩d'∩e} ...

and then just pick the max number.

Looking forward to see if someone can think of something better :)

Upvotes: 2

Views: 178

Answers (1)

Paul Hankin
Paul Hankin

Reputation: 58211

Define score(x, X) be to be the value of set X if x is in X, otherwise its negation.

Then, letting * represent an element that's not in any of the 5 sets, the highest score possible is:

max_{x in union(A, B, C, D, E, {*}} sum_{X in A, B, C, D, E} score(x, X)

This follows from the observation that any particular x is either in a set or its complement. You don't actually have to compute the union here. In Python you might write:

def max_config(A, B, C, D, E):
    best = None
    for S in A, B, C, D, E, set([None]):
        for x in S:
            best = max(best, sum(score(x, X) for X in A, B, C, D, E)))
    return best

Assuming a set membership test is O(1), this has complexity O(N), where N is the total size of the given sets.

Upvotes: 1

Related Questions