On Fri, Feb 18, 2005 at 09:57:59PM -0800, John Machin wrote: > > > > 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. > > How so? There is no connection between is/== and mutability. Let me > amplify: The point about 'is' is a good one, and aids your redemption > after your failure to have adequate guards caused your algorithm not to > work.
hey, it worked for all the test cases provided by the customer! :) and
then some; I hadn't thought of checking for cycles nor repetetitions.
>[snip]
>
> You are confusing mutability of lists (without which they would be
> called tuples!) with my point that the 'res' list was having its
> contents fiddled with implicitly through other "pointers".
umm... nope, see, well, hair-splitting and all that, there is this
list that holds the partitions; the partitions are lists of
elements. There is a reverse mapping that, for each element, holds the
partition that element is in. So basically you go down the list of
pairings, modifying the partitions as you go. I'm certain if I had
commented the function appropriately, we wouldn't be having this
discussion :)
Let me see if I can remedy that:
def merge(pairings):
"""
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.)
"""
# the list of partitions, or partitioned list.
# (each partition is a list of elements)
res = []
# reverse mapping (element -> partition it is in)
rev = {}
for pairing in pairings:
first, second = pairing
has_first = first in rev
has_second = second in rev
if has_first and has_second:
# both elements already in a partition...
if rev[first] is rev[second]:
# both elements in same partition, nothing to do
continue
# joining the two partitions:
# - grow one partition with the other one
rev[first].extend(rev[second])
# - clear the other one
rev[second][:] = []
# update reverse mapping
rev[second] = rev[first]
elif has_first:
# partition already exists, just add an element to it
rev[first].append(second)
# update reverse mapping
rev[second] = rev[first]
elif has_second:
# ditto
rev[second].append(first)
rev[first] = rev[second]
else:
# create partition from scratch
if first == second:
new = [first]
else:
new = [first, second]
# add it to list of partitions
res.append(new)
# update reverse mapping
rev[first] = rev[second] = new
# remove empty partitions
return filter(None, res)
hrmph, I should hit the sack. Sorry if this is still ugly, I'm too
tired to tell.
--
John Lenton ([EMAIL PROTECTED]) -- Random fortune:
Todo bicho que camina va a parar cuando se canse.
signature.asc
Description: Digital signature
-- http://mail.python.org/mailman/listinfo/python-list
