Raymond Hettinger <[EMAIL PROTECTED]> wrote:
> [EMAIL PROTECTED] ]
>>> 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:
> 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).
I don't know what the application is trying to do, but if I understand
it correctly, he is asking for something called a "maximal anti-chain".
For any partial order (e.g., subset relation), a chain is a set of
elements which are all comparable (and hence there is a linear or
total order on this set). In a similar way, an anti-chain is a set of
elements consisting of elements that are incomparable to each
other. Anti-chains themselves can be ordered by subset inclusion, and
thefore maximal ("largest") anti-chains can be found, but in general
there is no unique "greatest" anti-chain.
So the spec is perfectly ok and makes a lot of sense mathematically,
it's just that there is no unique solution.
Maybe googling for "maximal anti-chain" digs up some more information
(I haven't tried).
- Dirk
--
http://mail.python.org/mailman/listinfo/python-list
