title: Travelling Salesman - How to find permutations that are not equivalent
body: <p>We are trying to optimize our brute force method for TSP. It currently runs at (n-1)! but we can reduce it to (n-1)!/2 by ignoring paths which are equivalent.</p>
  
  <p>What we can't figure out is how to stop going down branches that will lead to an equivalent path as our recursive function develops the path from start to finish.</p>
  
  <p>e.g. let A be the start and end node and let G be a graph with 4 nodes, A,B,C,D. The intermediate path B->C->D is the same as C->D->B and D->B->C</p>
  
  <p>Our current solution is:</p>
  
  <pre><code>private static int minPathFast(int[][] graph, String sequence, int[] nodesLeft, int start) {
      int min;
      if (nodesLeft.length == 0)
      {
          return 0;
      }
      if (nodesLeft.length == 1) {
          probes++;
          return calcDist(graph, sequence + " " + nodesLeft[0], start);
      } else {
          min = minPath(graph, sequence + " " + nodesLeft[0], remove(nodesLeft, nodesLeft[0]), start);
          for (int i = 1; i &lt; nodesLeft.length; i++) {
  
              int[] newNodesLeft = remove(nodesLeft, nodesLeft[i]);
  
              int minPath = minPath(graph, sequence + " " + nodesLeft[i], newNodesLeft, start);
              if (minPath &lt; min)
              {
                  min = minPath;
              }
  
          }
      }
      return min;
  }
  </code></pre>