[Tutor] combining tuples in a list [NP complete reduction]

[Kirby Urner]

At 01:43 PM 4/5/2002 -0700, Brad Reisfeld wrote:
>I agree that is seems like a hard problem (although this is
>probably because my brain is a bit muddled), but I don't
>believe that this is a restatement of the traveling salesman
>problem.
>
>The problem seems to be one of enumeration (since the 'splicing'
>dictates the paths), rather than one of optimization (to find
>the paths).
>
>-Brad

I would agree that it's a somewhat different problem.

Here's a stab at a solution.  Somewhat complicated, but
uses dictionaries and is fairly fast.  If you check this
out on a few examples, and the results conform to your
expectations, then I can elucidate the algorithm more.
If it fails to meet your expectation, show me where it
breaks down (provide example inlist, output) and maybe
I can fix it for ya.

    def mkdict(thelist):
         """
         File all tuples by first letter, allowing
         multiple tuples per key if necessary
         """
         tupdict = {}
         for t in thelist:
             tupdict[t[0]] = tupdict.get(t[0],[]) + [t]
         return tupdict

    def splice(thelist):
         tupledict = {}   # keeps all current tuples
         for t in thelist:
             tupledict[t] = 1
         thedict = mkdict(tupledict.keys())  # 1st letter index
         for t in thelist:
             last = t[-1]
             # only process tuple if (a) still current and
             # (b) its last letter matches another's first
             if tupledict.get(t,0) and thedict.get(last,0):
                 for t2 in thedict[last]:
                     newtuple = t + t2[1:]   # build new tuple
                     tupledict[newtuple] = 1 # file in current
                     del tupledict[t2] # get rid of used tuple
                 del tupledict[t]      # get rid of used tuple
                 thedict = mkdict(tupledict.keys()) # rebuild index
         return tupledict.keys()  # list unprocessed + new tuples

  >>> inlist
  [('c', 'p', 'l'), ('d', 'e', 'f'), ('c', 'h', 'i'),
  ('f', 'w', 'x'), ('a', 'b', 'c'), ('g', 'h', 'i'), ('r', 'z', 'd')]
  >>> splice(inlist)
  [('g', 'h', 'i'), ('r', 'z', 'd', 'e', 'f', 'w', 'x'),
  ('a', 'b', 'c', 'p', 'l'), ('a', 'b', 'c', 'h', 'i')]

Kirby