CODEWITHSUNDEEP
pythonsettuples
alliedtoasters
alliedtoasters

Reputation: 430

How to find all frozensets that are subsets of another frozenset in a set of frozensets?

I am having trouble searching for the solution (if previously asked) to this problem because it's kind of hard to explain in a search.

I have a set of frozensets, like:

my_set = {
    frozenset({1, 2, 3}),
    frozenset({1, 2, 3, 4}),
    frozenset({1, 2, 3, 5}),
    frozenset({1, 3, 5}),
    frozenset({1, 2})
}

I want all the frozensets that are subsets of any other frozenset in the set, with a function get_subsets whose output is like:

subsets = get_subsets(my_set)
subsets == {
    frozenset({1, 2, 3}),
    frozenset({1, 3, 5}),
    frozenset({1, 2})
}

would return True. How can I get this? I previously had a set of tuples but revised to frozensets, as I was using touples before because they are hashable. I also asked to do it without iterating over the set because in my case I have hundreds of thousands of items in my set; now I revise to:

What's the fastest way to do this (now embracing iteration)?

Upvotes: 0

Views: 1368

Answers (2)

Aaditya Ura
Aaditya Ura

Reputation: 12669

I tried with itertools , Here is my approach:

import itertools
my_set = {
    (1, 2, 3),
    (1, 2, 3, 4),
    (1, 2, 3, 5),
    (1, 3, 5),
    (1,2)
}

With itertools.product :

print(set([ii[0] for ii in itertools.product(my_set,repeat=2) if ii[0]!=ii[1] and set(ii[0]).issubset(set(ii[1]))]))

output:

{(1, 3, 5), (1, 2), (1, 2, 3)}

With itertools.combination :

print(list(filter(None,set([i[0] if set(i[0]).issubset(i[1]) else i[1] if set(i[1]).issubset(set(i[0])) else None for i in itertools.combinations(my_set,r=2)]))))

output:

[(1, 3, 5), (1, 2), (1, 2, 3)]

Upvotes: 2

jfish003
jfish003

Reputation: 1332

If I understand what you are asking correctly, it is impossible. You can't do the comparisons that are necessary without iteration. With that in mind I have some workable code which does what you want:

def get_subsets(SET):
my_List = [] #a list to hold the sets   
L = [] #another list for later
for Set in SET:
    New = set(Set)
    my_List.append(New)

for i in range(len(my_List)):
    for j in range(i+1,len(my_List)):

        if i+2 == len(my_List): #this is so the last element doesn't get double counted
            break

        if my_List[i].issubset(my_List[j]):
            L.append(tuple(my_List[i]))
        if my_List[i].issuperset(my_List[j]):
            L.append(tuple(my_List[j]))


return set(L)

Testing this on your set gives the desired results. This is by no means the best code which could be written to get the job done, but it does what you want it to.

Upvotes: 1

Related Questions