title: How to implement a dynamic programming algorithms to TSP in Python?
body: <p>I want to solve the TSP problem using a dynamic programming algorithm in Python.The problem is:</p>
  
  <ul>
  <li>Input: cities represented as a list of points. For example, [(1,2), (0.3, 4.5), (9, 3)...]. The distance between cities is defined as the Euclidean distance.</li>
  <li>Output: the minimum cost of a traveling salesman tour for this instance, rounded down to the nearest integer.</li>
  </ul>
  
  <p>And the pseudo-code is:</p>
  
  <pre><code>Let A = 2-D array, indexed by subsets of {1, 2, ,3, ..., n} that contains 1 and destinations j belongs to {1, 2, 3,...n}
  1. Base case:
  2.          if S = {0}, then A[S, 1] = 0;
  3.          else, A[S, 1] = Infinity.
  4.for m = 2, 3, ..., n:   // m = subproblem size
  5.    for each subset of {1, 2,...,n} of size m that contains 1:
  6.        for each j belongs to S and j != 1:
  7.            A[S, j] = the least value of A[S-{j},k]+the distance of k and j for every k belongs to S that doesn't equal to j
  8.Return the least value of A[{1,2..n},j]+the distance between j and 1 for every j = 2, 3,...n.
  </code></pre>
  
  <p>My confusions are:</p>
  
  <p>How to index a list using subset, that is how to implement line 5 in the pseudo-code efficiently.</p>