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

[Brian Beck]

Xah Lee wrote:
> 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]];

Not sure how efficient this is, but I decided to take advantage of the 
operations provided by sets:

def merge(pairs):
     pairs = set(tuple(sorted(p)) for p in pairings)
     merged = []
     # Each loop will result in a new, complete sublist in the result.
     while pairs:
         p = set(pairings.pop())
         remove = set([])
         for pair in pairs:
             pairSet = set(pair)
             if pairSet & p:
                 p |= pairSet
                 remove.add(pair)
         pairs -= remove
         merged.append(list(p))
     return merged

--
Brian Beck
Adventurer of the First Order