On Thu, Feb 17, 2005 at 03:46:20PM -0800, 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
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, [EMAIL PROTECTED];
$rev{$first} = $rev{$second} = [EMAIL PROTECTED];
}
}
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 ([EMAIL PROTECTED]) -- Random fortune:
Noble cosa es, aún para un anciano, el aprender.
-- Sófocles. (497-406 a.C.) Filósofo griego.
signature.asc
Description: Digital signature
-- http://mail.python.org/mailman/listinfo/python-list
