pythonsetfrozenset

Search in set of sets


I would like to search in a set of sets in a specific way:

Example (Pseudocode):

search = {{1}, {3}}
search_base = {{1, 2}, {3, 4}}
# search results in True

because the 1 can be found in the first set and the 3 in the second. Order doesn't matter, but the number of subsets has to be identical, the search consists always of singletons.

Example (Intuition):

search = {{"Vitamin D"}, {"Sodium"}}
search_base = {{"Vitamin D", "Vitamin"}, {"Sodium", "NA"}}

I want to know if search (a combination of two materials with different hierachical names) is in the search base. The search base here only contains a single entry.


What I tried:

Using frozensets instead if sets for the hash.

search = frozenset([frozenset([1]), frozenset([3])])
search_base = frozenset([frozenset([1, 2]), frozenset([3, 4])])

all_matched = []
for i, set_ in enumerate(search):
    for bset_ in search_base:
        if not set_.isdisjoint(bset_):
            all_matched.append(True)
print(len(all_matched) == len(search))

It feels very clunky and therefore my question is if there is a much smarter (better performance) way to solve this.


Solution

  • As you said the data type is not important, I will just use a list of numbers and a list of sets. You can nest all and any, with in to check set membership:

    def search(nums, sets):
        return all(any(x in y for y in sets) for x in nums)
    
    print(search([1, 3], [{1, 2}, {3, 4}])) # True
    print(search([1, 2], [{1, 2}, {3, 4}])) # True
    print(search([1, 5], [{1, 2}, {3, 4}])) # False
    print(search(["Vitamin D", "Sodium"], [{"Vitamin D", "Vitamin"}, {"Sodium", "NA"}])) # True
    

    As for performance, this does not improve upon your current code. I doubt there are any (performance-wise) better ways unless there are more restrictions on the input data.