list of unique non-subset sets

Steven Bethard steven.bethard at gmail.com
Thu Mar 17 21:15:48 CET 2005


les_ander at yahoo.com wrote:
> Hi,
> I have many set objects some of which can contain same group of object
> while others can be subset of the other. Given a list of sets,
> I need to get a list of unique sets such that non of the set is an
> subset of another or contain exactly the same members.
> 
> Tried to do the following:
> s1=set(['a','b','c'])
> s2=set(['a','c'])
> s3=set(['a','d','e','f'])
> s4=set(['r','k','l'])
> s5=set(['r','k','l'])
> L=[s1,s2,s3,s4,s5]
> ----------------------- > cleaned-up list should contain s1, s3, s5

py> s1 = set(['a','b','c'])
py> s2 = set(['a','c'])
py> s3 = set(['a','d','e','f'])
py> s4 = set(['r','k','l'])
py> s5 = set(['r','k','l'])
py> lst = [s1, s2, s3, s4, s5]
py> uniqlst = []
py> for lstset in lst:
...     for uniqlstset in uniqlst:
...         if lstset.issubset(uniqlstset):
...             break
...     else:
...         uniqlst.append(lstset)
...
py> uniqlst
[set(['a', 'c', 'b']), set(['a', 'e', 'd', 'f']), set(['k', 'r', 'l'])]

Not horribly efficient, mind you.  But I believe it's correct.

I basically took your description "Given a list of sets, I need to get a 
list of unique sets such that non[e] of the set[s] is an subset of 
another" and translated that to code.  So I iterate through each element 
in lst, and and only add that element to uniqlst if it's not a subset of 
any of the items already in uniqlst.

STeVe



More information about the Python-list mailing list