exercise: partition a list by equivalence

[John Machin]

On 20 Feb 2005 03:31:33 -0800, bearophileHUGS at lycos.com wrote:

>John Machin:

>>FWIW, my offering is attached. <
>
>I'm sorry, I don't see the attach... (just the different title).
>

Here it is. I'll reply to the rest tomorrow. It's way past sleep-time
here.

!
!class _Stopper:
!    pass
!
!def merge_JM(pairings):
!    parent = {} 
!    link = {} 
!    size = {}
!    # 1. x not in parent => x is unknown
!    # 2. parent[x] -> root of cluster containing x
!    # 3. As a consequence of (2), parent[root] is root
!    # 4. link[x] chains the members of the cluster; 1st is root, 2nd
is link[root], ...
!    # 5. link[last_member] is _stopper
!    # 6. size[root] is the number of members of the cluster
!    parentget = parent.get
!    _stopper = _Stopper()
!    for inxa, inxb in pairings:
!        roota = parentget(inxa, _stopper)
!        rootb = parentget(inxb, _stopper)
!        if roota is not _stopper:
!            if rootb is not _stopper:
!                if roota is rootb:
!                    continue
!                if size[rootb] > size[roota]:
!                    newroot = rootb
!                    joiner = roota
!                else:
!                    newroot = roota
!                    joiner = rootb
!                size[newroot] += size[joiner]
!                del size[joiner]
!                parent[joiner] = newroot
!                tail = joiner
!                while link[tail] is not _stopper:
!                    tail = link[tail]
!                    parent[tail] = newroot
!                link[tail] = link[newroot]
!                link[newroot] = joiner
!            else:
!                size[roota] += 1
!                parent[inxb] = roota
!                link[inxb] = link[roota]
!                link[roota] = inxb
!        else:
!            if rootb is not _stopper:
!                size[rootb] += 1
!                parent[inxa] = rootb
!                link[inxa] = link[rootb]
!                link[rootb] = inxa
!            elif inxa is inxb:
!                parent[inxa] = inxa
!                link[inxa] = _stopper
!                size[inxa] = 1
!            else:
!                parent[inxa] = inxa
!                parent[inxb] = inxa
!                link[inxa] = inxb
!                link[inxb] = _stopper
!                size[inxa] = 2
!    olist = []
!    for root in size.iterkeys():
!        family = [root]
!        cousin = link[root]
!        while cousin is not _stopper:
!            family.append(cousin)
!            cousin = link[cousin]
!        olist.append(family)
!    return olist
!