Chapter 10 exercises: use complete set of permutations directly

Created by: plammens

I believe there are a couple of problems with the explanation and proposed solution to the problem presented in the exercises for chapter 10; particularly in the "Route Optimization" section.

1. Quoted from the "Route Optimization" section:

   Let us find the cost minimal order of traveling from the arrival airport to the departure airport while visiting all the sights.

   This problem can be expressed as finding the shortest so-called Hamiltonian path from the start to end on the Map (i.e., a path that visits each intermediate node exactly once). With the "hack" of assuming the distance of traveling from the end to the start to be 0 and thereby effectively merging the two airports into a single node, the problem can be viewed as a so-called traveling salesman problem (TSP).

   The TSP is a hard problem to solve but also well studied in the literature. Assuming symmetric distances, a TSP with n nodes has \frac{(n-1)!}{2} possible routes. (n-1) because any node can be the start / end and divided by 2 as the problem is symmetric.

   You're considering only half of the Hamiltonian cycles as possible "routes" in the TSP because of symmetry (every Hamiltonian cycle and its "reverse" have the same cost). Then, according to this definition, for every possible route in that TSP, there are two possible routes in the original problem: the one that starts at start and traverses through the given route in normal order and ends at end, and the one that starts at start, traverses the given route in reverse order and ends at end—note that these two paths are distinct since they have, in general, different costs.

   Note that this is exactly what's happening in the proposed solution for Map.brute_force. https://github.com/webartifex/intro-to-python/blob/b363d1cd3a8bd14eac79f4c34a1a40fb07b354a9/10_classes_02_exercises.ipynb#L1411-L1412

   Thus, there are 2\cdot\frac{(n-1)!}{2} = (n-1)! possible paths in the original problem, where n is the number of sights plus one (the "dummy" node inserted for the reduction to a TSP). Ergo, there are math.factorial(len(sights)+ 1 - 1) paths whose cost is to be computed. This is, precisely, the number of permutations of sights.

   So there's no need to reduce the problem to a TSP; there's a much simpler explanation for the number of Hamiltonian paths between start and end. Every such path is a permutation of n elements, where n is the total number of nodes (including start and end), but with 2 of these elements being fixed (start and end); in total, there are (n - 2)! such paths. (Note that there's no "redundant" paths being counted here, since for every equivalence class of paths—where a path is equivalent to another if one is the reverse of the other—only one path will be in the aforementioned set: the path where start is at the beginning and end is at the end.) Indeed, we would get math.factorial((len(sights) + 2) - 2), ergo math.factorial(len(sights)).

2. Quoted from the same section:

   However, if we use permutations() as is, we try out redundant routes. For example, transferred to our case, the tuples (1, 2, 3) and (3, 2, 1) represent the same route as the distances are symmetric and the tourist could be going in either direction. To obtain the unique routes, we use an if-clause in a "hacky" way by only accepting routes where the first node has a smaller value than the last. Thus, we keep, for example, (1, 2, 3) and discard (3, 2, 1).

   What's the point of removing so-called "redundant" routes if then we end up checking every route and its reverse in Map.brute_force?

   https://github.com/webartifex/intro-to-python/blob/b363d1cd3a8bd14eac79f4c34a1a40fb07b354a9/10_classes_02_exercises.ipynb#L1411-L1412

   Quick example:

   import itertools
   
   nums = list(range(4))
   a = set(perm for perm in itertools.permutations(nums) if perm[0] < perm[-1])
   a.update(perm[::-1] for perm in list(a))
   b = set(itertools.permutations(nums))
   
   print(a == b)  # True

   This relates to point 1: the reverse of a permutation of inner nodes is not, in fact, redundant.

Proposed changes

1. Ditch the comparison to TSP; it's not useful, it complicates the explanation unnecessarily. Stick to viewing the problem as finding the minimal Hamiltonian path between two distinct nodes.
2. Don't filter out reversed permutations to add them back later; use the complete set of permutations of inner nodes directly

The stub for Map.brute_force becomes

    # answer to Q33
    def brute_force(self):
        """Calculate the shortest route by brute force.

        The route is plotted on the folium.Map.
        """
        # Make a dictionary of routes to route costs
        route_costs = {route: ... for route in
                       ((..., *perm, ...) for perm in ...)}

        # Select the best route (i.e. the one with the minimum cost)
        best_route, min_cost = min(route_costs.items(), key=lambda item: ...)

        # Plot the route on the map
        folium.PolyLine(
            [x.location for x in best_route],
            color="orange", weight=3, opacity=1
        ).add_to(self._map)

        return ...

with the solution being

    # answer to Q33
    def brute_force(self):
        """Calculate the shortest route by brute force.

        The route is plotted on the folium.Map.
        """
        # Make a dictionary of routes to route costs
        route_costs = {route: self.evaluate(route) for route in
                       ((self._start, *perm, self._end) for perm in itertools.permutations(self._places))}

        # Select the best route (i.e. the one with the minimum cost)
        best_route, min_cost = min(route_costs.items(), key=lambda item: item[1])

        # Plot the route on the map
        folium.PolyLine(
            [x.location for x in best_route],
            color="orange", weight=3, opacity=1
        ).add_to(self._map)

        return self