Introduction

The Traveling Salesman Problem asks for the cheapest tour that visits every city exactly once and returns to the start. One simple but important reduction comes from circular permutations: because a tour is a cycle, rotating the same route does not create a new solution.

Fix a Starting City to Remove Rotational Duplicates

If you list all tours naively, the same cycle appears many times with different starting positions. For example, these tours represent the same cycle:

• 'A -> B -> C -> D -> A'
• 'B -> C -> D -> A -> B'
• 'C -> D -> A -> B -> C'

That is circular symmetry. So instead of examining all n! orderings, you can fix one city as the starting point and only permute the remaining n - 1 cities. The search space drops to (n - 1)!.

That does not solve TSP, but it removes a large amount of duplicate work immediately.

Brute Force Example with a Fixed Start

Here is a small Python example that anchors city 0 and enumerates only the remaining permutations.

1import itertools
2
3
4dist = [
5    [0, 10, 15, 20],
6    [10, 0, 35, 25],
7    [15, 35, 0, 30],
8    [20, 25, 30, 0],
9]
10
11
12def tour_cost(tour):
13    total = 0
14    for i in range(len(tour) - 1):
15        total += dist[tour[i]][tour[i + 1]]
16    total += dist[tour[-1]][tour[0]]
17    return total
18
19
20start = 0
21best_tour = None
22best_cost = float("inf")
23
24for perm in itertools.permutations(range(1, len(dist))):
25    tour = (start,) + perm
26    cost = tour_cost(tour)
27    if cost < best_cost:
28        best_cost = cost
29        best_tour = tour
30
31print(best_tour, best_cost)

This is the standard brute-force reduction for a cyclic tour problem. You are not changing the mathematics of the optimal tour. You are only eliminating repeated representations of the same cycle.

Symmetric TSP Lets You Reduce Further

If the distance matrix is symmetric, meaning travel cost from A to B equals travel cost from B to A, then reversing a tour also gives the same total cost. After fixing one starting city, you can divide the count by 2 again and consider only one direction of each cycle.

That means the number of distinct tours for symmetric TSP becomes:

• '(n - 1)! after fixing the start'
• '(n - 1)! / 2 after also identifying reversed tours as equivalent'

This matters a lot for brute-force search, because every factor removed from factorial growth is valuable.

What Circular Permutations Do Not Change

Circular permutations reduce duplicate enumeration, but they do not change the fact that exact TSP remains exponential in the general case. The reduction helps:

• brute-force search
• branch-and-bound implementations
• dynamic programming setups that need a canonical starting city

It does not make large TSP instances easy by itself.

So the right way to think about it is not "circular permutations solve TSP," but "circular permutations remove symmetry that would otherwise waste computation."

Common Pitfalls

• Saying the problem shrinks from n! to polynomial time. It does not.
• Forgetting that reverse-tour equivalence only applies naturally to symmetric TSP.
• Double-counting tours by changing the starting city even after treating the route as a cycle.
• Applying the symmetry reduction incorrectly when the route has fixed start or end constraints that break circular equivalence.

Summary

• TSP tours are cyclic, so rotations of the same route are equivalent.
• Fixing one starting city reduces brute-force enumeration from n! to (n - 1)!.
• In symmetric TSP, reversing a route is also equivalent, reducing the count further to (n - 1)! / 2.
• This removes duplicate work but does not change the exponential nature of exact TSP.
• Circular permutation reduction is a symmetry optimization, not a complete solution method.