[perl-python] exercise: partition a list by equivalence

[anton muhin]

Xah Lee wrote:
> here's another interesting algorithmic exercise, again from part of a
> larger program in the previous series.
> 
> Here's the original Perl documentation:
> 
> =pod
> 
> merge($pairings) takes a list of pairs, each pair indicates the
> sameness
> of the two indexes. Returns a partitioned list of same indexes.
> 
> For example, if the input is
> merge( [ [1,2], [2,4], [5,6] ] );
> 
> that means 1 and 2 are the same. 2 and 4 are the same. Therefore
> 1==2==4. The result returned is
> 
> [[4,2,1],[6,5]];
> 
> (ordering of the returned list and sublists are not specified.)
> 
> =cut

Almost a joke:

from numarray import *

def merge(*pairs):
   flattened = reduce(tuple.__add__, pairs, tuple())
   m, M = min(flattened), max(flattened)

   d = M - m + 1
   matrix = zeros((d, d), type = Bool)

   for x, y in pairs:
     X, Y = x - m, y - m

     matrix[X, X] = 1
     matrix[X, Y] = 1
     matrix[Y, X] = 1
     matrix[Y, Y] = 1

   while True:
     next = greater(dot(matrix, matrix), 0)
     if alltrue(ravel(next == matrix)):
       break
     matrix = next

   results = []
   for i in range(d):
     eqls, = nonzero(matrix[i])
     if eqls.size():
       if i == eqls[0]:
         results.append(tuple(x + m for x in eqls))

   return results

Disclaimer: I'm not an expert in numarray and suppose the something can 
be dramatically imporved.