list of unique non-subset sets

Bengt Richter bokr at oz.net
Sat Mar 19 02:10:04 CET 2005


On 18 Mar 2005 15:46:44 -0800, les_ander at yahoo.com wrote:

>OK, so I need to be more precise.
>Given a list of sets, output the largest list of sets (from this list,
>order does not matter) such that:
>1) there is no set that is a PROPER subset of another set in this list
>2) no two sets have exactly the same members (100% overlap)
>
>Seems like this problem is much harder than I thought...
>
two from the above come out length 5:

  5: [set(['k', 'r', 'l']), set(['a', 'c', 'b']), set(['a', 'e', 'd', 'f']), set(['h', 'g']), set(['i', 'h'])]
  5: [set(['k', 'r', 'l']), set(['a', 'e', 'd', 'f']), set(['a', 'c']), set(['h', 'g']), set(['i', 'h'])]

How do you define "largest" ? ;-)
I guess you could sum(map(len, setlist)) as a measure, but what if that makes
a tie between two setlists (as I think it could, in general)?

Regards,
Bengt Richter



More information about the Python-list mailing list