Source code online books for professionals by professionals

BUt Where IS the reDUCtION?
Finding a useful reduction is often a crucial step in solving an algorithmic problem. If you don’t know where to b 
egin, ask yourself, where is the reduction?
however, it may not be entirely clear how the ideas in this section jibe with the picture of a reduction presented 
in Figure 
4-1
. as explained, a reduction transforms instances from problem a to instances of problem B and then 
transforms the output of B to valid output for a. But in induction and reduction, we’ve only reduced the problem 
size. Where is the reduction, really?
oh, it’s there—it’s just that we’re reducing from a to a. there is some transformation going on, though. the reduction 
makes sure the instances we’re reducing to are smaller than the original (which is what makes the induction work), 
and when transforming the output, we increase the size again.
these are two major variations of reductions: reducing to a different problem and reducing to a shrunken version 
of the same. If you think of the subproblems as vertices and the reductions as edges, you get the subproblem 
graph discussed in Chapter 2, a concept I’ll revisit several times. (It’s especially important in Chapter 8.)
Designing with Induction (and Recursion)
In this section, I’ll walk you through the design of algorithmic solutions to three problems. The problem I’m building 
up to, topological sorting, is one that occurs quite a bit in practice and that you may very well need to implement 
yourself one day, if your software manages any kind of dependencies. The first two problems are perhaps less useful, 
but great fun, and they’re good illustrations of induction (and recursion).

---

Chapter 4 
■
 InduCtIon and reCursIon ... and reduCtIon 
76
Finding a Maximum Permutation
Eight persons with very particular tastes have bought tickets to the movies. Some of them are happy with their seats, 
but most of them are not, and after standing in line in Chapter 3, they’re getting a bit grumpy. Let’s say each of them 
has a favorite seat, and you want to find a way to let them switch seats to make as many people as possible happy with 
the result (ignoring other audience members, who may eventually get a bit tired by the antics of our moviegoers). 
However, because they are all rather grumpy, all of them refuse to move to another seat if they can’t get their favorite.
This is a form of matching problem. You’ll encounter a few other of those in Chapter 10. We can model the 
problem (instance) as a graph, like the one in Figure 
4-4
. The edges point from where people are currently sitting to 
where they want to sit. (This graph is a bit unusual in that the nodes don’t have unique labels; each person, or seat,  
is represented twice.)