3

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.

fgregg
  • 3,173
  • 30
  • 37
  • 1
    [ {1,2,3,4}, {1,2,3}, {1,2}, {1} ] I doubt is it possible to avoid O(N^2) when the final graph is a complete graph? – shole Sep 13 '17 at 03:24
  • I feel like I should be able to exploit the partial orderablity to do better than that. – fgregg Sep 13 '17 at 03:35
  • 2
    You can start by ordering the sets by size, and going in increasing order, and when looking at the next set you can start comparing it to previous sets in *decreasing* order of size, and if it's a superset of one of them, then it's also a superset of its entire subgraph and you don't need to consider those smaller sets. – jkff Sep 13 '17 at 05:01
  • For finding which sets are subsets of a given set, see paper linked from https://stackoverflow.com/questions/9353100/quickly-checking-if-set-is-superset-of-stored-sets – jkff Sep 13 '17 at 05:06
  • 1
    Do you aim for a full graph holding all ribs of inclusion? How will you use the DAG after you construct it? – Boris Strandjev Sep 13 '17 at 13:46

0 Answers0