title: Algorithm for nesting nesting sets
body: <p>I have a large collection of sets, some of which are subsets of each others, like:</p>
  
  <pre><code>[{1, 2, 3, 4}, {1, 2}, {1, 5}, {1, 2, 3, 4, 5}, {2, 6}]
  </code></pre>
  
  <p>I'd like to take this collection and output a DAG of partial order of the subset relations</p>
  
  <pre><code>{1, 2, 3, 4, 5} &gt;= {1, 2, 3, 4} &gt;= {1, 2}
  {1, 2, 3, 4, 5} &gt;= {1, 5}
  {2, 6}
  </code></pre>
  
  <p>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.</p>
  
  <p>One optimization is to create an inverted index which would help avoid comparing sets that had no common element like <code>{2, 6}</code> and <code>{1, 5}</code>.</p>
  
  <p>This problem seems related to <a href="https://en.wikipedia.org/wiki/Topological_sorting" rel="nofollow noreferrer">Topological sorting</a> and <a href="https://en.wikipedia.org/wiki/Linear_extension" rel="nofollow noreferrer">Linear Extensions of a partial order</a>.</p>
  
  <p>This is nearly a duplicate of <a href="https://stackoverflow.com/questions/8838779/generate-a-dag-from-a-poset-using-stricly-functional-programming">Generate a DAG from a poset using stricly functional programming</a>, but I'm open to a solution that is not purely functional.</p>