title: Find unique set of identifiers/groups among several columns
body: <p>I have data with two (potentially more) columns of identifiers (typically long strings). These differ sometimes, are mistyped, or change over time. I want to identify unique subjects in the data. This requires identifying groups of cases which are connected via their ids at some level.</p>
  
  <p>An example</p>
  
  <pre><code>df &lt;- data.frame(ida = c("A", "B", "C", "C", "D", "E"),
                   idb = c(1, 1, 3, 4, 4, 7),
                   trueid = c("id1", "id1", "id2", "id2", "id2", "id3"))
  </code></pre>
  
  <pre><code>&gt; df
    ida idb trueid
  1   A   1    id1
  2   B   1    id1
  3   C   3    id2
  4   C   4    id2
  5   D   4    id2
  6   E   7    id3
  </code></pre>
  
  <p>Identifiers for <code>id1</code> are <code>"A", "B", 1</code>, for <code>id2</code> <code>"C", "D", 3, 4</code> and for <code>id3</code> <code>"E", 7</code>.</p>
  
  <p>I don't know <code>trueid</code> but need to find it using the information from columns <code>ida</code> and <code>idb</code>.</p>
  
  <p>The solution needs to scale to millions of observations with tens of thousands of unique ids. I am already using <code>data.table</code>.</p>
  
  <p><strong>Extension</strong>: There is another scenario where there are more than two columns, and some columns might be informative for others, i.e. have the same identifiers. I do not know which columns are informative for which. I think type can be disregarded though, all columns are strings or can safely be converted.</p>
  
  <p>Another example for this:</p>
  
  <pre><code>df &lt;- data.frame(ida = c("A", "B", "C", "C", "D", "E"),
                   idb = c("1", "2", "3", "4", "4", "7"),
                   idc = c("1", "1", "2", "3", "4", "5"),
                   idd = c("1", "A", "2", "3", "4", "5"),
                   trueid = c("id1", "id1", "id1", "id1", "id1", "id2"))
  </code></pre>
  
  <pre><code>&gt; df
    ida idb idc idd trueid
  1   A   1   1   1    id1
  2   B   2   1   A    id1
  3   C   3   2   2    id1
  4   C   4   3   3    id1
  5   D   4   4   4    id1
  6   E   7   5   5    id2
  </code></pre>
  
  <p><strong>Edit:</strong> As a commenter pointed out, this is essentially the clique problem of finding complete subgraphs in a graph. After reading a bit more, I understand this issue can be solved with <code>library(igraph)</code>. I am leaving the question open as I would prefer a solution that relies on <code>base</code>, <code>data.table</code> or <code>dplyr</code>. I cannot easily install packages on the server I am using, installing <code>igraph</code> involves dealing with a lot of red tape and delays.</p>
  
  <p><strong>Edit2:</strong> For anybody reading this and facing a similar problem: <code>zx8754</code>'s answer using igraph is considerably (several orders of magnitude) faster on larger (simulated) data with more groups. If you have the chance to use <code>igraph</code>, do so.</p>