title: Efficient grouping of rows from Nx2 integer numpy array to match sequential elements in rows
body: <p>Allright, got a strange one for the numpy speed-freaks out there.</p>
  
  <p>I have data such that:</p>
  
  <ul>
  <li>Nx2 array of integer values</li>
  <li>Each integer between 0 and N-1 appears twice</li>
  <li>There will be one or more 'loops' through the data. </li>
  </ul>
  
  <p>A 'loop' would be a subset of the rows ordered such that each row shares a single element with the row above it and the other element with the row below it. Goal is to find arrays of indices to the data that yield the closed loops. </p>
  
  <p>Example data (single loop):</p>
  
  <pre><code>In: data = np.array([[0, 7],
                       [1, 8],
                       [2, 9],
                       [3, 0],
                       [4, 1],
                       [5, 2],
                       [6, 3],
                       [4, 7],
                       [8, 5],
                       [9, 6]])
  </code></pre>
  
  <p>Example solution:</p>
  
  <pre><code>In: ordered_indices = np.array([0, 7, 4, 1, 8, 5, 2, 9, 6, 3])
  
  In: data[ordered_indices]
  Out: array([[0, 7],
              [4, 7],
              [4, 1],
              [1, 8],
              [8, 5],
              [5, 2],
              [2, 9],
              [9, 6],
              [6, 3],
              [3, 0]])
  </code></pre>
  
  <p>There is no guarantee of the order of elements in the row; i.e., 7 could be the first element in both rows it appears in, or the first in one and the second in the other.</p>
  
  <p>The data is on the order of N=1000; solutions with loops are too slow. </p>
  
  <p>For convience, typical data can be generated with the script below. Here, the indices of the ordered data follow a periodic pattern, but that wouldn't be true in the actual data.</p>
  
  <p>Generate sample data:</p>
  
  <pre><code>import numpy as np
  import sys
  
  # parameters
  N = 1000
  M = 600
  
  # initialize array
  data = np.empty((N,2), dtype=np.int)
  
  # populate first column
  data[:,0] = np.arange(N)
  
  # populate second column by shifting first column; create two loops within the data
  inds1 = np.arange(0,M)[np.arange(-7,M-7)]
  inds2 = np.arange(M,N)[np.arange(-9,N-M-9)]
  data[:M,1] = data[inds1,0]
  data[M:,1] = data[inds2,0]
  
  # shuffle order of two entries in rows
  map(np.random.shuffle, data)
  </code></pre>
  
  <p>I've written a method that gets the proper results, but it's pretty slow (around 0.5 seconds on my ageing laptop):</p>
  
  <p>Baseline solution:</p>
  
  <pre><code>def groupRows(rows):
  
      # create a list of indices
      ungrouped_rows = range(len(rows))
  
      # initialize list of lists of indices
      grouped_rows = []
  
      # loop until there are no ungrouped rows
      while 0 &lt; len(ungrouped_rows):
  
          # remove a row from the beginning of the list
          row_index = ungrouped_rows.pop(0)
  
          # start a new list of rows
          grouped_rows.append([row_index])
  
          # get the element at the start of the loop
          stop_at = data[grouped_rows[-1][0],0]
  
          # search target
          look_for = data[grouped_rows[-1][0],1]
  
          # continue until loop is closed
          closed = False
  
          while not closed:
  
              # for every row left in the ungrouped list
              for i, row_index in enumerate(ungrouped_rows):
  
                  # get two elements in the row being checked
                  b1,b2 = data[row_index]
  
                  # if row contains the current search target
                  if look_for in (b1,b2):
  
                      # add it to the current group
                      grouped_rows[-1].append(ungrouped_rows.pop(i))
  
                      # update search target
                      if look_for == b1:
                          look_for = b2
                      elif look_for == b2:
                          look_for = b1
  
                      # exit the loop through the ungrouped rows
                      break
  
              # check if the loop is closed
              if look_for == stop_at:
                  closed = True
  
      return map(np.array, grouped_rows)
  </code></pre>
  
  <p>So my approach works, but with lists and two nested loops; there must be a slicker way to to do this using numpy's more efficient methods. Any ideas?</p>