CODEWITHSUNDEEP
pythonlistset
René Jörg Spies
René Jörg Spies

Reputation: 2196

How can I check if sets in a list are subsets of each other?

I have a list which holds quite a lot of sets and I want to check if there are any subsets of those sets in the list testing each set against one another.

Right now I am doing this like so:

for set1 in list_of_sets:
    for set2 in list_of_sets:
        if set1 < set2:
            <do stuff>

Although I am a bit new to python, I have in my urine that this iterating method is a quite un-pythonic way. How can I improve this?

Upvotes: 0

Views: 413

Answers (3)

volcano
volcano

Reputation: 3582

You can use itertools.permutations to avoid redundant comparisons with itself combinations

for set1, set2 in itertools.permutations(list_of_sets, 2):
    if set1 < set2:
        <do something>

Upvotes: 0

alexis
alexis

Reputation: 50220

Never mind "pythonic". With this code, you'll be testing every pair of sets twice... and also testing each set against itself. Here is one case where it pays to use indices, and save yourself half the computation. But you can still wear the pythonic look and use iteration instead of incrementing an int:

for i, set1 in enumerate(list_of_sets):
    for set2 in list_of_sets[i+1:]:
        if set1 < set2:
           do stuff

If your collection is really large you could do other optimizations like building a partial order (because if set1 < set2 and set2 < set3, you can predict what set1 < set3 will do), but honestly i doubt it would be worth your trouble.

Upvotes: 2

sytech
sytech

Reputation: 41179

There is an issubset method.

t = {1,2,3}
s = {1,2}
s.issubset(t)  # True

Which is the same as s <= t

for set1 in list_of_sets:
    for set2 in list_of_sets:

Can be flattened with product from the itertools module.

from itertools import product

for set1, set2 in product(list_1, list_1):
    ...

Or perhaps even better, using combinations

from itertools import combinations

for (set1, set2) in combinations(list_of_sets, 2):
    ...

There's also perhaps optimization to be had in the approach, but as far as Python-specifics, I hope this helps.

Upvotes: 3

Related Questions