title: Combine a list of pairs (tuples)?
body: <p>From a list of linked pairs, I want to combine the pairs into groups of common IDs, so that I can then write group_ids back to the database, eg:</p>
  
  <pre><code>UPDATE table SET group = n WHERE id IN (...........);
  </code></pre>
  
  <p>Example:</p>
  
  <pre><code>[(1,2), (3, 4), (1, 5), (6, 3), (7, 8)]
  </code></pre>
  
  <p>becomes</p>
  
  <pre><code>[[1, 2, 5], [3, 4, 6], [7, 8]]
  </code></pre>
  
  <p>Which allows:</p>
  
  <pre><code>UPDATE table SET group = 1 WHERE id IN (1, 2, 5);
  UPDATE table SET group = 2 WHERE id IN (3, 4, 6);
  UPDATE table SET group = 3 WHERE id IN (7, 8);
  </code></pre>
  
  <p>and</p>
  
  <pre><code>[(1,2), (3, 4), (1, 5), (6, 3), (7, 8), (5, 3)]
  </code></pre>
  
  <p>becomes</p>
  
  <pre><code>[[1, 2, 5, 3, 4, 6], [7, 8]]
  </code></pre>
  
  <p>Which allows:</p>
  
  <pre><code>UPDATE table SET group = 1 WHERE id IN (1, 2, 5, 3, 4, 6);
  UPDATE table SET group = 2 WHERE id IN (7, 8);
  </code></pre>
  
  <p>I have written some code which works. I pass in a list of tuples, where each tuple is a pair of linked ids.  I return a list of lists, where each internal list is a list of common id's.</p>
  
  <p>I iterate over the list of tuples and assign each tuple element to groups as follows:</p>
  
  <ul>
  <li>if neither a nor b is in a list, create a new list, appened a and b and append the new list to the list of lists</li>
  <li>if a is in a group but b isn't, add b to the a group</li>
  <li>if b is in a group but a isn't, add a to the b group</li>
  <li>if a and b are already in separate groups merge the a and b groups</li>
  <li>if a and b are already in the same group, do nothing</li>
  </ul>
  
  <p>I am expecting millions of linked pairs, and I am expecting hundreds of thousand of gropus and hunderds of thousands of group members.   So, I need the algorithm to be fast, I am looking for some suggestions for some really efficient code.  Although I have implemented this to build a list of lists, I am open to anything, they key thing is being able to build the above SQL to get the group ids back to the database.</p>
  
  <pre><code>def group_pairs(list_of_pairs):
      """
  
      :param list_of_pairs:
      :return:
      """
      groups = list()
      for pair in list_of_pairs:
          a_group = None
          b_group = None
  
          for group in groups:
              # find what group if any a and b belong to
  
              # don't bother checking if a group already found
              if a_group is None and pair[0] in group:
                  a_group = group
              # don't bother checking if b group already found
              if b_group is None and pair[1] in group:
                  b_group = group
              # if a and b found, stop looking
              if a_group is not None and b_group is not None:
                  break
  
          if a_group is None:
              if b_group is None:
                  # neither a nor b are in a group; create a new group and
                  # add a and b
                  groups.append([pair[0], pair[1]])
              else:
                  # b is in a group but a isn't, so add a to the b group
                  b_group.append(pair[0])
          elif a_group != b_group:
              if b_group is None:
                  # a is in a group but b isn't, so add b to the a group
                  a_group.append(pair[1])
              else:
                  # a and b are in different groups, add join b to a and get
                  # rid of b
                  a_group.extend(b_group)
                  groups.remove(b_group)
          elif a_group == b_group:
              # a and b already in same group, so nothing to do
              pass
  
      return groups
  </code></pre>