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.
--
http://mail.python.org/mailman/listinfo/python-list
