list of unique non-subset sets

[Dirk Thierbach]

Raymond Hettinger <vze4rx4y at verizon.net> wrote:
> [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:

> 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