list of unique non-subset sets

Raymond Hettinger vze4rx4y at verizon.net
Sat Mar 19 02:43:42 CET 2005


[les_ander at yahoo.com ]
> >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)

[Bengt Richter]
> 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)?

With multiple outputs satisfying the constraints, I would suspect that there is
something wrong with the original spec (not as a stand-alone problem, but as
component of a real application).


Raymond Hettinger





More information about the Python-list mailing list