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

Author

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

Xah Lee

2005-02-17, 8:58 pm

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

For those of you unfamiliar with math lingoes, partition a list means
to create sublists, based on some criteria. In our case, the input list
comes in the form of pairs, and its members are the union of all
members in the pairs. The criterion for partition in our case is that
of equivalence, specified in the pairs input.

Try to write a Python code for this. In the Python code, the input
should be a list of couples. (for Perlers, sketch out the algorithm on
paper and try to code in Python directly.)

I'll post Perl & Python code tomorrow.

==This is brought to you by the Perl-Python community.==
== http://xahlee.org/perl-python/python.html ==

Xah
xah@xahlee.org
http://xahlee.org/PageTwo_dir/more.html

alex23

2005-02-18, 3:58 am

>For those of you unfamiliar with math lingoes, partition a list means
> to create sublists, based on some criteria.

Typical moronic mathematicians with their exclusionary lingoes...why
can't they just say "create sublists based on some criteria" like
normal people?

- alex23

anton muhin

2005-02-18, 3:58 pm

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.

Paul McGuire

2005-02-23, 3:59 pm

Please consider my submission also (Python 2.3-compatible).

-- Paul McGuire

.. import sets
..
.. input = [[1, 2], [3, 4], [2, 3], [4, 5]]
.. input = [[1, 2], [3, 4], [4, 5]]
.. input = [[1, 2],[2,1], [3, 4], [4, 5],[2,2],[2,3],[6,6]]
..
.. def merge(pairings):
.. ret = []
.. for a,b in pairings:
.. s1 = None
.. s2 = None
.. for s in ret:
.. if a in s or b in s:
.. if s1 is None:
.. s1 = s
.. else:
.. s2 = s
.. break
.. else:
.. for s in ret:
.. if a in s:
.. s.add(b)
.. break
.. elif b in s:
.. s.add(a)
.. break
.. else:
.. ret.append(sets.Set([a,b]))
.. continue
.. ret.remove(s1)
.. ret.remove(s2)
.. ret.append(s1.union(s2))
..
.. return [list(s) for s in ret]
..
.. print merge(input)

Paul McGuire

2005-02-24, 8:57 pm

A slightly better version, only walks the set of cumulative list of
sets once per pairing.

-- Paul

.. import sets
..
.. input = [[1, 2], [3, 4], [2, 3], [4, 5]]
.. input = [[1, 2], [3, 4], [4, 5]]
.. input = [[1, 2],[2,1], [3, 4], [4, 5],[2,2],[2,3],[6,6]]
..
..def merge(pairings):
.. ret = []
.. for a,b in pairings:
.. aset = None
.. bset = None
.. for s in ret:
.. if not aset and a in s:
.. aset = s
.. if not bset and b in s:
.. bset = s
.. if aset and bset:
.. break
.. else:
.. if aset:
.. aset.add(b)
.. elif bset:
.. bset.add(a)
.. else:
.. ret.append(sets.Set([a,b]))
.. continue
.. if aset is not bset:
.. ret.remove(aset)
.. ret.remove(bset)
.. ret.append(aset.union(bset))
..
.. return [list(s) for s in ret]
..
..print merge(input)

Sponsored Links