[Tutor] combining tuples in a list

[Lloyd Hugh Allen]

Brad Reisfeld wrote:
> 
> Hi,
> I am faced with the problem of 'combining' tuples in a list in such a way
> that any tuple whose last element matches the first element of another tuple
> must be combined (eliminating the duplicate element). My aim is to end up
> with a list of these resulting tuples.
> 
> In practice, I have a list containing a very large number of tuples (each of
> which has three items). A short example illustrating this is
> 
> inlist =
> [('c','p','l'),
> ('d','e','f'),
> ('c','h','i'),
> ('f','w','x'),
> ('a','b','c'),
> ('g','h','i'),
> ('r','z','d')]
> 
> For this case we see that the last element in the fifth tuple, 'c', matches
> the first element in the third tuple. Combining these (and eliminating the
> duplicate match) gives ('a','b','c') '+' ('c','h','i') =>
> ('a','b','c','h','i')
> 
> Following this procedure exhaustively on the list above would yield the
> desired result (order of tuples in the final list doesn't matter):
> 
> outlist =
> [('a','b','c','h','i'),
> ('r','z','d','e','f','w','x'),
> ('g','h','i'),
> ('a','b','c','p','l')]
> 
> Currently, I am carrying out this procedure in a seemingly very inefficient
> way by going through the list of tuples multiple times for each tuple I am
> building up. I'm sure there must be a better way.
> 
> Any suggestions are appreciated.
> 
> Thanks.
> 
> -Brad
> 
> _______________________________________________
> Tutor maillist  -  Tutor@python.org
> http://mail.python.org/mailman/listinfo/tutor

Here's an ugly way--the idea is that it runs through the list twice
(once forwards, then once through the output the other direction), and
hopefully gets everything that way. I'm uncomfortable with the repeated
output that is created from the (abc)(cpl)(chi), but that seems to be
what you want. The problem is that (aba)(aca) should, following these
rules, create an infinite loop (I'm assuming that an item should not
join to itself).

Because what we want the tuples to do to each other is extremely similar
to tuple concatenation, I thought it would be a good chance to use class
inheritance; __mul__ is overwritten instead of __add__ because the
procedure refers to the old __add__, if that makes any sense. That whole
"don't use the word in its own definition" (usually) thing.

###
class concatuple(tuple):
    def __mul__(self, other):
        """concatenates two tuples together, dropping the common
element.

        Ugly stuff happened when I tried to use __add__ to do this (inf
loop;
        sorry for the kludge)."""
#        print self
#        print other
        if self[-1] == other[0]:
            return self + other[1:]
        else:
            raise ValueError

def cyclelist(inlist):
    outlist = []
    while inlist:
        first = inlist[0]
    #    print first
        for second in inlist[1:]:
            if first[-1] == second[0]:
                inlist.append(first*second)
                try:
                    inlist.remove(first)
                except:
                    print "First arg tried to be removed twice"
                try:
                    inlist.remove(second)
                except:
                    print "Second arg tried to be removed twice"

        if first == inlist[0]:  #no matches found
            outlist.append(first)
            inlist.remove(first)
    return outlist

        
if __name__ == "__main__":
    inlist = map(concatuple, [('c','p','l'),
              ('d','e','f'),
              ('c','h','i'),
              ('f','w','x'),
              ('a','b','c'),
              ('g','h','i'),
              ('r','z','d')])
    newin = cyclelist(inlist)
#    print newin
    newin.reverse()
#    print newin
    outlist = cyclelist(newin)
    print outlist