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

[Brian Beck]

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(sorted(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.pop()) # 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(list(subList))

     return merged

--
Brian Beck
Adventurer of the First Order