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

[Brad Reisfeld]

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

-----Original Message-----
From: Danny Yoo [mailto:dyoo@hkn.eecs.berkeley.edu]
Sent: Friday, April 05, 2002 1:18 PM
To: Kirby Urner
Cc: Brad Reisfeld; tutor@python.org
Subject: Re: [Tutor] combining tuples in a list [NP complete reduction]


On Fri, 5 Apr 2002, Kirby Urner wrote:

> At 09:58 AM 4/5/2002 -0700, Brad Reisfeld wrote:
>
> >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.
>
> Some use of the dictionary data structure, keying off
> first and last letters of your tuples, would help you
> find the splice points.


But his question is very very hard, deceptively so.  It's the traveling
salesman problem, a problem that haunts the dim nightmares of Computer
Science students everywhere.


The "traveling salesman problem" can be paraphrased as: given a list of
cities and a list of the roads between the cities, find the shortest route
along the roads that passes through all of the cities.


Imagine that we have a bunch of cities:

###
cities = ['c', 'l', 'd', 'f', 'i', 'x', 'a', 'g', 'r', 'd']
###

and a bunch of roads that can connect these cities together:

###
roads = [('c', 'l'),
         ('d', 'f'),
         ('c', 'i'),
	 ('f', 'x'),
         ('a', 'c'),
         ('g', 'i'),
         ('r', 'd')]
###


But suddenly, this traveling salesman instance looks suspiciously like
Brad's tuple-connected problem...

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

So any "fast" solution to the tuple-connecting problem will solve the
traveling salesman problem.