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

[Xah Lee]

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]

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

>For those of you unfamiliar with math lingoes, partition a list means[color=blue]
> to create sublists, based on some criteria.[/color]

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]

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

Xah Lee wrote:[color=blue]
> 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[/color]

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(mat rix, matrix), 0)
if alltrue(ravel(n ext == 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.

[John Lenton]

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

On Thu, Feb 17, 2005 at 03:46:20PM -0800, Xah Lee wrote:[color=blue]
> 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[/color]

in Python:

def merge(pairings) :
rev = {}
res = []
for pairing in pairings:
first, second = pairing
has_first = first in rev
has_second = second in rev
if has_first and has_second:
rev[first].extend(rev[second])
rev[second][:] = []
rev[second] = rev[first]
elif has_first:
rev[first].append(second)
rev[second] = rev[first]
elif has_second:
rev[second].append(first)
rev[first] = rev[second]
else:
copy = [first, second]
res.append(copy )
rev[first] = rev[second] = copy
return filter(None, res)

and in Perl:

sub merge($)
{
my %rev = ();
my @res = ();
my ($pairing, $first, $second, $has_first, $has_second);
foreach $pairing (@{$_[0]})
{
($first, $second) = @$pairing;
$has_first = exists $rev{$first};
$has_second = exists $rev{$second};
if ($has_first and $has_second)
{
push @{$rev{$first}} , @{$rev{$second} };
@{$rev{$second} } = ();
$rev{$second} = $rev{$first};
}
elsif (exists $rev{$first})
{
push @{$rev{$first}} , $second;
$rev{$second} = $rev{$first};
}
elsif (exists $rev{$second})
{
push @{$rev{$second} }, $first;
$rev{$first} = $rev{$second};
}
else
{
my @copy = ($first, $second);
push @res, \@copy;
$rev{$first} = $rev{$second} = \@copy;
}
}
return [grep @$_, @res];
}

although in Perl you wouldn't define it to take a reference to a list
(as you did), but rather a list, and you wouldn't define it to return
a reference to a list, but rather a list in list context (and possibly
a reference in scalar context).

Both versions are (IMHO) pretty clear (when the docstring/pod is
included), and O(n) because dict/hash lookup and list
appending/pushing is O(1) in both languages. Both versions can
probably be tweaked for speed quite a bit, but I don't *think* there's
a better-than-O(n) algorithm for this.

Note that the Python version assumes that the pairs' elements are
hashable; your example used numbers, so I thought it was pretty safe
assumption. The Perl version has no such restriction.


--
John Lenton (john@grulic.or g.ar) -- Random fortune:
Noble cosa es, aún para un anciano, el aprender.
-- Sófocles. (497-406 a.C.) Filósofo griego.

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.0 (GNU/Linux)

iD8DBQFCFhXjgPq u395ykGsRAus5AJ 9iCSbGsyP3QHZy/whP195GSVNIwwCc Dyqf
hIA+oWaLBHdSGUi 7t79Wfx8=
=BlC7
-----END PGP SIGNATURE-----

[John Machin]

Re: exercise: partition a list by equivalence


John Lenton wrote:[color=blue]
> On Thu, Feb 17, 2005 at 03:46:20PM -0800, Xah Lee wrote:[color=green]
> > here's another interesting algorithmic exercise, again from part of[/color][/color]
a[color=blue][color=green]
> > 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[/color]
>
> in Python:
>
> def merge(pairings) :
> rev = {}
> res = []
> for pairing in pairings:
> first, second = pairing
> has_first = first in rev
> has_second = second in rev[/color]
Not robust in the face of input like:
[[1,1]]
or
[[1,2], [1,2]]
or
[[1,2], [2,1]]
or
[[1,2], [2,3], [3,1]]

needs "if first == second: continue" here
[color=blue]
> if has_first and has_second:[/color]

needs "if rev[first] == rev[second]: continue" here
[color=blue]
> rev[first].extend(rev[second])
> rev[second][:] = []
> rev[second] = rev[first]
> elif has_first:
> rev[first].append(second)
> rev[second] = rev[first]
> elif has_second:
> rev[second].append(first)
> rev[first] = rev[second]
> else:
> copy = [first, second]
> res.append(copy )[/color]

My reaction to the "magic" by which res grows was "omigod that's the
most horrible thing I've seen for quite a while" but there was worse to
come :-)
[color=blue]
> rev[first] = rev[second] = copy
> return filter(None, res)
>
> and in Perl:
>[/color]
[snip]
[color=blue]
>
> Both versions are (IMHO) pretty clear (when the docstring/pod is
> included), and O(n) because dict/hash lookup and list
> appending/pushing is O(1) in both languages. Both versions can
> probably be tweaked for speed quite a bit, but I don't *think*[/color]
there's[color=blue]
> a better-than-O(n) algorithm for this.[/color]

List appending is O(1) only in the amortised sense. Extending is not
O(1) in any sense. Neither is the list comparison that is necessary for
robustness (using your data structure, that is).

You don't need to think. This problem has been extensively picked over
by folk who are a lot smarter than us, starting from 30 years ago.
Google for "disjoint set" and "union-find". One gets the impression
that the best possible algorithm would be slightly *worse* than O(n).
[color=blue]
>
> Note that the Python version assumes that the pairs' elements are
> hashable; your example used numbers, so I thought it was pretty safe
> assumption. The Perl version has no such restriction.[/color]

In the real world, the objects under comparison (images, fingerprints,
customer records, etc) may not themselves be hashable and comparison
for equality may be expensive but a unique identifier would be assigned
to each object and that ID would of course be cheaply hashable and
comparable.

[John Lenton]

Re: exercise: partition a list by equivalence

On Fri, Feb 18, 2005 at 03:21:10PM -0800, John Machin wrote:[color=blue]
> Not robust in the face of input like:
> [[1,1]]
> or
> [[1,2], [1,2]]
> or
> [[1,2], [2,1]]
> or
> [[1,2], [2,3], [3,1]][/color]

oops, my bad.
[color=blue]
>
> needs "if first == second: continue" here
> [color=green]
> > if has_first and has_second:[/color]
>
> needs "if rev[first] == rev[second]: continue" here[/color]

an 'is' is enough, and better.
[color=blue][color=green]
> > rev[first].extend(rev[second])
> > rev[second][:] = []
> > rev[second] = rev[first]
> > elif has_first:
> > rev[first].append(second)
> > rev[second] = rev[first]
> > elif has_second:
> > rev[second].append(first)
> > rev[first] = rev[second]
> > else:
> > copy = [first, second]
> > res.append(copy )[/color]
>
> My reaction to the "magic" by which res grows was "omigod that's the
> most horrible thing I've seen for quite a while" but there was worse to
> come :-)[/color]

what is magic about it? is it really that horrible?
[color=blue]
> List appending is O(1) only in the amortised sense. Extending is not
> O(1) in any sense. Neither is the list comparison that is necessary for
> robustness (using your data structure, that is).
>
> You don't need to think. This problem has been extensively picked over
> by folk who are a lot smarter than us, starting from 30 years ago.
> Google for "disjoint set" and "union-find". One gets the impression
> that the best possible algorithm would be slightly *worse* than O(n).[/color]

Of course! I'd forgotten clean about union-find. And yes, it's
O(n*log(n)) union and find, and my implementation is O(n**2) for
union, O(1) for find; I'm pleased that, in spite of having forgotten
about union-find, I "reinvented " (heh) something that is better than
the "naive" implementation we saw in class.

Now I'm even more worried about your dismissal of this as magic and
horrible.

--
John Lenton (john@grulic.or g.ar) -- Random fortune:
Why don't you fix your little problem... and light this candle?
-- Alan Shepherd, the first man into space, Gemini program

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.0 (GNU/Linux)

iD8DBQFCFoBIgPq u395ykGsRApUIAK CnNmctznqq1KTfZ hi7Dl8YpjPnbQCg uo2E
z/Ss9rWC64h9vuDrJ M//Ge8=
=rVAU
-----END PGP SIGNATURE-----

[Cyril BAZIN]

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

Hello John,

Try your python code on this example:
merge([[1,2], [3,4], [1,2], [5,3]])

The result given by your function is:
[[3, 4, 5]]

Sorry...

To Xah: next time you propose an exercise, write some UNIT TESTS!!!
Then people will be able to test if there answers are correct or not.

Cyril



On Fri, 18 Feb 2005 13:20:51 -0300, John Lenton <john@grulic.or g.ar> wrote:[color=blue]
> On Thu, Feb 17, 2005 at 03:46:20PM -0800, Xah Lee wrote:[color=green]
> > 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[/color]
>
> in Python:
>
> def merge(pairings) :
> rev = {}
> res = []
> for pairing in pairings:
> first, second = pairing
> has_first = first in rev
> has_second = second in rev
> if has_first and has_second:
> rev[first].extend(rev[second])
> rev[second][:] = []
> rev[second] = rev[first]
> elif has_first:
> rev[first].append(second)
> rev[second] = rev[first]
> elif has_second:
> rev[second].append(first)
> rev[first] = rev[second]
> else:
> copy = [first, second]
> res.append(copy )
> rev[first] = rev[second] = copy
> return filter(None, res)
>
> and in Perl:
>
> sub merge($)
> {
> my %rev = ();
> my @res = ();
> my ($pairing, $first, $second, $has_first, $has_second);
> foreach $pairing (@{$_[0]})
> {
> ($first, $second) = @$pairing;
> $has_first = exists $rev{$first};
> $has_second = exists $rev{$second};
> if ($has_first and $has_second)
> {
> push @{$rev{$first}} , @{$rev{$second} };
> @{$rev{$second} } = ();
> $rev{$second} = $rev{$first};
> }
> elsif (exists $rev{$first})
> {
> push @{$rev{$first}} , $second;
> $rev{$second} = $rev{$first};
> }
> elsif (exists $rev{$second})
> {
> push @{$rev{$second} }, $first;
> $rev{$first} = $rev{$second};
> }
> else
> {
> my @copy = ($first, $second);
> push @res, \@copy;
> $rev{$first} = $rev{$second} = \@copy;
> }
> }
> return [grep @$_, @res];
> }
>
> although in Perl you wouldn't define it to take a reference to a list
> (as you did), but rather a list, and you wouldn't define it to return
> a reference to a list, but rather a list in list context (and possibly
> a reference in scalar context).
>
> Both versions are (IMHO) pretty clear (when the docstring/pod is
> included), and O(n) because dict/hash lookup and list
> appending/pushing is O(1) in both languages. Both versions can
> probably be tweaked for speed quite a bit, but I don't *think* there's
> a better-than-O(n) algorithm for this.
>
> Note that the Python version assumes that the pairs' elements are
> hashable; your example used numbers, so I thought it was pretty safe
> assumption. The Perl version has no such restriction.
>
> --
> John Lenton (john@grulic.or g.ar) -- Random fortune:
> Noble cosa es, aún para un anciano, el aprender.
> -- Sófocles. (497-406 a.C.) Filósofo griego.
>
>
> --
> http://mail.python.org/mailman/listinfo/python-list
>
>
>[/color]

[John Machin]

Re: exercise: partition a list by equivalence


John Lenton wrote:[color=blue]
> On Fri, Feb 18, 2005 at 03:21:10PM -0800, John Machin wrote:[color=green]
> > Not robust in the face of input like:
> > [[1,1]]
> > or
> > [[1,2], [1,2]]
> > or
> > [[1,2], [2,1]]
> > or
> > [[1,2], [2,3], [3,1]][/color]
>
> oops, my bad.
>[color=green]
> >
> > needs "if first == second: continue" here
> >[color=darkred]
> > > if has_first and has_second:[/color]
> >
> > needs "if rev[first] == rev[second]: continue" here[/color]
>
> an 'is' is enough, and better.[/color]

Good point. You're redeeming yourself :-)
[color=blue]
>[color=green][color=darkred]
> > > rev[first].extend(rev[second])
> > > rev[second][:] = []
> > > rev[second] = rev[first]
> > > elif has_first:
> > > rev[first].append(second)
> > > rev[second] = rev[first]
> > > elif has_second:
> > > rev[second].append(first)
> > > rev[first] = rev[second]
> > > else:
> > > copy = [first, second]
> > > res.append(copy )[/color]
> >
> > My reaction to the "magic" by which res grows was "omigod that's[/color][/color]
the[color=blue][color=green]
> > most horrible thing I've seen for quite a while" but there was[/color][/color]
worse to[color=blue][color=green]
> > come :-)[/color]
>
> what is magic about it? is it really that horrible?[/color]

Try explaining to the newbies over on the tutor list how despite "res"
only ever *explicitly* having little bits like [3, 4] appended to it,
it (or more properly the thing to which it refers) is actually
festering and growing and being mutated under the surface until at the
finale it bursts out dripping slime just like the creature from the
black lagoon ...

[Brian Beck]

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

Xah Lee wrote:[color=blue]
> 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]];[/color]

Not sure how efficient this is, but I decided to take advantage of the
operations provided by sets:

def merge(pairs):
pairs = set(tuple(sorte d(p)) for p in pairings)
merged = []
# Each loop will result in a new, complete sublist in the result.
while pairs:
p = set(pairings.po p())
remove = set([])
for pair in pairs:
pairSet = set(pair)
if pairSet & p:
p |= pairSet
remove.add(pair )
pairs -= remove
merged.append(l ist(p))
return merged

--
Brian Beck
Adventurer of the First Order

[Brian Beck]

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

Brian Beck wrote:[color=blue]
> [code][/color]

Whoops, that should say:

def merge(pairs):
pairs = set(tuple(sorte d(p)) for p in pairs)
merged = []
# Each loop will result in a new, complete sublist in the result.
while pairs:
p = set(pairs.pop() )
remove = set([])
for pair in pairs:
pairSet = set(pair)
if pairSet & p:
p |= pairSet
remove.add(pair )
pairs -= remove
merged.append(l ist(p))
return merged

--
Brian Beck
Adventurer of the First Order

[Brian Beck]

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

Brian Beck wrote:[color=blue]
> Brian Beck wrote:[color=green]
> > [code][/color][/color]

Ah heck, nevermind... it worked for my small test cases but the
algorithm is just wrong.

--
Brian Beck
Adventurer of the First Order

[David Eppstein]

Re: exercise: partition a list by equivalence

In article <1108768870.455 974.244590@c13g 2000cwb.googleg roups.com>,
"John Machin" <sjmachin@lexic on.net> wrote:
[color=blue]
> You don't need to think. This problem has been extensively picked over
> by folk who are a lot smarter than us, starting from 30 years ago.
> Google for "disjoint set" and "union-find". One gets the impression
> that the best possible algorithm would be slightly *worse* than O(n).[/color]

It can be solved by union-find
(e.g. with UnionFind from <http://www.ics.uci.edu/~eppstein/PADS/>):

import UnionFind
import sets

def merge(pairs):
uf = UnionFind.Union Find()
items = sets.Set()
for a,b in pairs:
uf.union(a,b)
items.add(a)
items.add(b)
leaders = {}
for a in items:
leaders.setdefa ult(uf[a],sets.Set()).ad d(a)
return[list(component) for component in leaders.values( )]

If you do all the unions before all the finds, as in this algorithm,
union-find is O(n).

However it might be easier to treat the input pairs as the edges of a
graph and apply a depth-first-search based graph connected components
algorithm.

--
David Eppstein
Computer Science Dept., Univ. of California, Irvine

http://www.ics.uci.edu/~eppstein/

[Brian Beck]

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

Well, it looks like David posted a good solution, but I haven't tested
it (I'm assuming his works fine). I fixed mine up anyway... it actually
works now. If you're not using 2.4 you'll have to import sets.Set as set.

def merge(pairList) :
pairList = set(tuple(sorte d(p)) for p in pairList)
# Sort & set to remove duplicates, tuple to make hashable
merged = []
removePairs = set([])

# Each loop will result in a new, complete sublist in the result
while pairList:
if removePairs:
removePairs = set([])
else:
subList = set(pairList.po p()) # Start a new sublist

for pair in pairList:
pairSet = set(pair)
# True when pairSet and subList share at least one element
if pairSet & subList:
subList |= pairSet # Merge pair with subList
removePairs.add (pair) # Mark pair for removal

if removePairs:
pairList -= removePairs
else:
merged.append(l ist(subList))

return merged

--
Brian Beck
Adventurer of the First Order

[John Lenton]

Re: exercise: partition a list by equivalence

On Fri, Feb 18, 2005 at 04:52:46PM -0800, John Machin wrote:[color=blue][color=green][color=darkred]
> > > needs "if rev[first] == rev[second]: continue" here[/color]
> >
> > an 'is' is enough, and better.[/color]
>
> Good point. You're redeeming yourself :-)[/color]

this, together with you saying that it is hard to explain, makes me
think that you aren't comfortable thinking of lists as mutable
objects.

[color=blue][color=green]
> > what is magic about it? is it really that horrible?[/color]
>
> Try explaining to the newbies over on the tutor list how despite "res"
> only ever *explicitly* having little bits like [3, 4] appended to it,
> it (or more properly the thing to which it refers) is actually
> festering and growing and being mutated under the surface until at the
> finale it bursts out dripping slime just like the creature from the
> black lagoon ...[/color]

understanding why that works, and why it is 'is' and not '==', are
both part of the same thing. Lists are mutable, and you can mutate
them, and they mutate. Unless you actually write code that uses the
fact you will forget it, and it will bite you. Of course, don't use it
just for the heck of it, but that creature you dismiss as a
slime-dripping mutation is actually quite useful.

While I'm at being unpolite, do you really think this code was harder
to understand than the code posted by anton, using numarray?

And, of course, if this code were for anything non-throw-awayable,
there would've been quite a bit of explaining going on between those
lines of code.

Ok, now back to being polite :)

--
John Lenton (john@grulic.or g.ar) -- Random fortune:
Hay más días que longanizas.

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.0 (GNU/Linux)

iD8DBQFCFq8rgPq u395ykGsRAnTNAJ 4rtCpfoFUYJYLpQ 6WmvHbmTLSsYgCe JzRE
dXMUU9lYxyECNtl d9JjcdeA=
=2pzJ
-----END PGP SIGNATURE-----

[David Eppstein]

Re: exercise: partition a list by equivalence

In article <eppstein-8851A4.18394418 022005@news.ser vice.uci.edu>,
David Eppstein <eppstein@ics.u ci.edu> wrote:
[color=blue]
> It can be solved by union-find
> (e.g. with UnionFind from <http://www.ics.uci.edu/~eppstein/PADS/>):[/color]

Here's a cleaned up version, after I added a proper iter() method to the
UnionFind data structure:

import UnionFind

def merge(pairs):
uf = UnionFind.Union Find()
for a,b in pairs:
uf.union(a,b)
components = {}
for a in uf:
components.setd efault(uf[a],[]).append(a)
return components.valu es()
[color=blue]
> If you do all the unions before all the finds, as in this algorithm,
> union-find is O(n).[/color]

That was a little too sloppy. It is possible to solve the union find
problem, with all unions before all finds, in time O(n). However the
usual union find data structure takes more time, O(n alpha(n)).
[color=blue]
> However it might be easier to treat the input pairs as the edges of a
> graph and apply a depth-first-search based graph connected components
> algorithm.[/color]

This would be O(n), though.

--
David Eppstein
Computer Science Dept., Univ. of California, Irvine

http://www.ics.uci.edu/~eppstein/