list of unique non-subset sets

Steven Bethard steven.bethard at gmail.com
Thu Mar 17 22:25:02 CET 2005


Kent Johnson wrote:
> Raymond Hettinger wrote:
> 
>> [les_ander at yahoo.com]
>>
>>> 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
>>
>>
>>
>> This should do the trick:
>>
>>
>> result = []
>> for s1 in L:
>>     for s2 in result:
>>         if s1 <= s2:
>>             break
>>     else:
>>         result.append(s1)
>>
>> print result
> 
> 
> If I understand the original post correctly, you also need to check for 
> an existing set being a subset of the set you are adding. A better test 
> case is
> 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'])
> s6=set(['g', 'h'])
> s7=set(['h', 'i'])
> s8=set(['g', 'h', 'i'])
> 
> L=[s1,s2,s3,s4,s5,s6,s7,s8]
> # ----------------------- > cleaned-up list should contain s1, s3, s5, s8
> 
> which both Raymond and STeVe's proposals fail.

Can you just do:

py> def uniq(lst):
...     result = []
...     for s1 in sorted(lst, reverse=True):
...         for s2 in result:
...             if s1 <= s2:
...                 break
...         else:
...             result.append(s1)
...     return result
...
py> lst = [set(['a','b','c']),
...        set(['a','c']),
...        set(['a','d','e','f']),
...        set(['r','k','l']),
...        set(['r','k','l']),
...        set(['g', 'h']),
...        set(['h', 'i']),
...        set(['g', 'h', 'i'])]
py> uniq(lst)
[set(['a', 'c', 'b']), set(['a', 'e', 'd', 'f']), set(['k', 'r', 'l']), 
set(['i', 'h', 'g'])]

Haven't thought about it too hard though...

STeVe



More information about the Python-list mailing list