exercise: partition a list by equivalence

[John Lenton]

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 (john at grulic.org.ar) -- Random fortune:
Todo bicho que camina va a parar cuando se canse.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 196 bytes
Desc: Digital signature
URL: <http://mail.python.org/pipermail/python-list/attachments/20050219/e73ba576/attachment.sig>