CODEWITHSUNDEEP
pythonpython-3.xsettuples
Plato's Cave
Plato's Cave

Reputation: 99

How to find if multiple sets are all found in multiple tuples (but never the same tuple)?

I have a list of lists, which each consists of three tuples of four-value combinations of the integers 0 to 11, e.g.: 

[(0, 1, 4, 7), (2, 3, 6, 9), (5, 8, 10, 11)]

I want to be able to find if this list (and others) contains certain integers in at least one of the tuples, and contains other integers in at least one of the other tuples.

It's simple enough if I want to check if at least one tuple contains certain integers. For instance, you could have something like:

def func_1(lst):
    for tup in lst:
        if {0,1}.issubset(tup):
            return True
    return False

which returns True for [(0, 1, 4, 7), (2, 3, 6, 9), (5, 8, 10, 11)]
...but False for [(0, 4, 7, 9), (1, 2, 3, 6), (5, 8, 10, 11)]

But what if I want to find if one tuple contains {0,1} and another separate tuple contains {2, 3}? Something like this won't work:

def func_2(lst):
    for tup in lst:
        if {0,1}.issubset(tup) or {2,3}.issubset(tup):
            return True
    return False

That would return True for both of the above lists, when it is only True for the first one.

Upvotes: 0

Views: 83

Answers (2)

Attersson
Attersson

Reputation: 4876

Use 2 functions. The first checks for your first match. Then call the second on the remaining elements to check for your second match. If there is none, continue your previous search.

def sub_search(lst):
    for tup in lst:
        if {2,3}.issubset(tup):
            return True
    return False

def search(lst):
    for i,tup in enumerate(lst):
        if {0,1}.issubset(tup):
            if sub_search(lst[0:i]+lst[i+1:]):
                return True
    return False

Upvotes: 0

Martijn Pieters
Martijn Pieters

Reputation: 1125018

You'd have to iterate over the tuples, and test each against both sets. Then if one of the sets matches, remove that set from consideration and only return true if the all sets have matches in the remainder:

def func_2(lst):
    sets_to_test = {frozenset({0,1}), frozenset({2,3})}
    for tup in lst:
        matched = next((s.issubset(tup) for s in sets_to_test), None)
        if matched:
            s.remove(matched)
            if not sets_to_test:
                # all sets have matches to separate tuples
                return True
    return False

This approach will extend to more sets too.

Note that this could miss matches if there are tuples that are subsets of either one of the sets. If this is a possibility you need to account for, I'd use recursion to handle this option:

def func_2(lst, sets_to_test=None):
    if sets_to_test is None:
        sets_to_test = {frozenset({0,1}), frozenset({2,3})}
    if not sets_to_test:
        # all sets have matched
        return True
    if not lst:
        # no tuples remain
        return False
    for i, tup in enumerate(lst):
        for set_to_test in sets_to_test:
            if set_to_test.issubset(tup):
                if func_2(lst[i + 1:], sets_to_test - {set_to_test}):
                    return True
    return False

So whenever one of the sets matches, recursion is used to test the remaining sets and list of tuples; if that recursive call doesn't return True, further sets are tested.

Upvotes: 1

Related Questions