title: Get disjoint sets from a list in R
body: <p>Given a list:</p>
  
  <pre><code>foo &lt;- list(c("a", "b", "d"), c("c", "b"), c("c"),
              c("b", "d"), c("e", "f"), c("e", "g"))
  </code></pre>
  
  <p>what is an efficient way to get a list that contains the disjoint sets of its content?</p>
  
  <p>Here I want to obtain:</p>
  
  <pre><code>[[1]]
  [1] "a" "b" "c" "d"
  
  [[2]]
  [1] "e" "f" "g"
  </code></pre>
  
  <p>The solutions I have managed to come up with seemed overly complicated and slow (I'm working with a largish list (4000+ elements) that contain up to hundreds of elements).</p>
  
  <p>Thanks!</p>
  
  <hr>
  
  <p><strong>Solutions benchmarking</strong></p>
  
  <p>Thank you all for your input. The igraph approach is really nice. I did some benchmarking of the proposed solutions and using igraph with @flodel suggestion is efficient. The example here (<code>iGrp</code>) has 3170 elements.</p>
  
  <pre><code>&gt; microbenchmark(igraph_method(iGrp), igraph_method2(iGrp), iterative_method(iGrp), times=10L)
  ## Unit: milliseconds
  ##                    expr       min        lq    median        uq       max neval
  ##     igraph_method(iGrp) 6892.8534 7140.0287 7229.5569 7396.2458 8044.9796    10
  ##    igraph_method2(iGrp)  381.4555  391.2097  442.3282  472.5641  537.4885    10
  ##  iterative_method(iGrp) 7118.7857 7272.9568 7595.9700 7675.2888 8485.4388    10
  
  #### functions used
  
  igraph_method &lt;- function(lst) {
      edg &lt;- do.call("rbind", lapply(lst, function(x) {
          if (length(x) &gt; 1) t(combn(x, 2)) else NULL
          }))
      g &lt;- graph.data.frame(edg)
      split(V(g)$name, clusters(g)$membership)
  }
  
  igraph_method2 &lt;- function(lst) {
      edg &lt;- do.call("rbind", lapply(lst, function(x) {
          if (length(x) &gt; 1) cbind(head(x, -1), tail(x, -1)) else NULL
      }))
      g &lt;- graph.data.frame(edg)
      split(V(g)$name, clusters(g)$membership)
  }
  
  iterative_method &lt;- function(lst) {
      Reduce(function(l, x)  {
          matches &lt;- sapply(l, function(i) any(x %in% i))
  
          if (any(matches)) {
              combined &lt;- unique(c(unlist(l[matches]), x))
              l[matches] &lt;- NULL        # Delete old entries
              l &lt;- c(l, list(combined)) # Add combined entries
          } else {
              l &lt;- c(l, list(x))        # New list entry
          }
          l
      }, lst, init=list())
  }
  </code></pre>