Chapter 10 exercises: use complete set of permutations directly

[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

[webartifex]

Thanks for your great contribution, Paolo @plammens.

Sometimes, when I create these exercises iteratively over a couple of days, I tend to lose the "big picture."

Your remarks about not referring to the problem as a TSP is correct. Even though I would tend to leave the term in as a comparison as most non-CS people probably can relate to it and have no idea of what a Hamiltonian path is.

Your code stub is great. One could probably adapt it to not materialize one big dictionary though. But only keep track of the best so far in a generator expression or so. What do you think?

I will merge it in in the next run of the course in two weeks.

May I ask something: You seem "overqualified" for this course already :) What made you work through the materials? If you had prior knowledge, what new ideas did you learn? Just curious to find out in case I make a version of the course for people coming from another language.

Cheers, Alex

[plammens]

Your remarks about not referring to the problem as a TSP is correct. Even though I would tend to leave the term in as a comparison as most non-CS people probably can relate to it and have no idea of what a Hamiltonian path is.

You're right, maybe talking about a "minimal Hamiltonian path problem" in this context does sound a bit pedantic. I see two options:

• Keep it as it was before (but "fixing" the explanation about the number of routes in the original problem, mentioning how solutions to the TSP problem relate to solutions to the original problem)
• Maintaining the "minimal Hamiltonian path" as the central "way to view" the problem (perhaps giving it a friendlier name, or omitting the phrase altogether), but mentioning its interpretation as a TSP in the "Route Optimization" section

What would you prefer?

Your code stub is great. One could probably adapt it to not materialize one big dictionary though. But only keep track of the best so far in a generator expression or so. What do you think?

Totally right, hadn't thought about memory. We could get the minimal route in one call of min on a single generator expression:

        best_route, _ = min(((route, ...) for route in
                             ((..., *perm, ...) for perm in ...)),
                            key=lambda x: ...)

but maybe it's a bit too messy? My eyes hurt from so many parentheses :-) And also it seems less clear as to what the student should fill in in each blank.

Since generator expressions are part of your syllabus, maybe we could split it up into several generators:

        # Generator of routes from start to end
        routes = ((..., *permutation, ...) for permutation in ...)

        # Generator of pairs of (route, cost of route)
        route_cost_pairs = ((route, ...) for route in routes)

        # Select the best route/cost pair (based on cost)
        best_route, _ = min(route_cost_pairs, key=lambda x: ...)

May I ask something: You seem "overqualified" for this course already :) What made you work through the materials? If you had prior knowledge, what new ideas did you learn? Just curious to find out in case I make a version of the course for people coming from another language.

I was helping someone who was working through this course. I only looked at the exercises in chapters 9 and 10, but judging only from that it looks great! And I did learn something new: I had no idea of the existence of a pretty-print function in the standard library! There's always something to learn. 🙂

[webartifex]

You're right, maybe talking about a "minimal Hamiltonian path problem" in this context does sound a bit pedantic. I see two options:

* Keep it as it was before (but "fixing" the explanation about the number of routes in the original problem, mentioning how solutions to the TSP problem relate to solutions to the original problem)

* Maintaining the "minimal Hamiltonian path" as the central "way to view" the problem (perhaps giving it a friendlier name, or omitting the phrase altogether), but mentioning its interpretation as a TSP in the "Route Optimization" section

What would you prefer?

I would suggest a mixture: reframing the problem as a "minimal Hamiltonian path" problem and mentioning the TSP as a "relative"

        # Generator of routes from start to end
        routes = ((..., *permutation, ...) for permutation in ...)

        # Generator of pairs of (route, cost of route)
        route_cost_pairs = ((route, ...) for route in routes)

        # Select the best route/cost pair (based on cost)
        best_route, _ = min(route_cost_pairs, key=lambda x: ...)

This would be the best solution. Then, students review the idea of generator expressions.

I was helping someone who was working through this course. I only looked at the exercises in chapters 9 and 10, but judging only from that it looks great! And I did learn something new: I had no idea of the existence of a pretty-print function in the standard library! There's always something to learn. slightly_smiling_face

Ask your friend to list section of the book that are hard to understand. Maybe, we can re-write them in a clearer way.

Thanks for all your efforts.

[plammens]

I've made the changes.

Regarding mentioning the TSP, I only added a "generic" mention that TSP is closely related to this problem. That's because now that I thought of it, the TSP reformulation I mentioned above isn't correct either: the distances to any intermediate node are different from the start node vs from the end node, and merging the two into one "dummy" node in the TSP won't reflect this. Unless we make a TSP on a directed graph, but then I think adding an explanation for that is more detrimental than beneficial.

[plammens]

Hi @webartifex, any reasons for closure? I did spend a fair amount of time on this.