I have a large collection of sets, some of which are subsets of each others, like:
[{1, 2, 3, 4}, {1, 2}, {1, 5}, {1, 2, 3, 4, 5}, {2, 6}]
I'd like to take this collection and output a DAG of partial order of the subset relations
{1, 2, 3, 4, 5} >= {1, 2, 3, 4} >= {1, 2}
{1, 2, 3, 4, 5} >= {1, 5}
{2, 6}
Is there a way to do this other than comparing all combinations of sets (which is prohibitive when there is a large number of sets). This seems close to a number of set cover problems but, I can't find a problem that this reduces to.
One optimization is to create an inverted index which would help avoid comparing sets that had no common element like {2, 6} and {1, 5}.
This problem seems related to Topological sorting and Linear Extensions of a partial order.
This is nearly a duplicate of Generate a DAG from a poset using stricly functional programming, but I'm open to a solution that is not purely functional.