Source code online books for professionals by professionals

Figure 4-4.  A mapping from the set {a ... h} to itself
Note
 
■
  this is an example of what’s called a bipartite graph, which means that the nodes can be partitioned into two 
sets, where all the edges are between the sets (and none of them inside either). In other words, you could color the nodes 
using only two colors so that no neighbors had the same color.
Before we try to design an algorithm, we need to formalize the problem. Truly understanding the problem is 
always a crucial first step in solving it. In this case, we want to let as many people as possible get the seat they’re 
“pointing to.” The others will need to remain seated. Another way of viewing this is that we’re looking for a subset of 
the people (or of the pointing fingers) that forms a one-to-one mapping, or permutation. This means that no one in the 
set points outside it, and each seat (in the set) is pointed to exactly once. That way, everyone in the permutation is free 
to permute—or switch seats—according to their wishes. We want to find a permutation that is as large as possible  
(to reduce the number of people that fall outside it and have their wishes denied).
Once again, our first step is to ask, where is the reduction? How can we reduce the problem to a smaller one? 
What subproblem can we delegate (recursively) or assume (inductively) to be solved already? Let’s go with simple 
(weak) induction and see whether we can shrink the problem from n to n–1. Here, n is the number of people (or 
seats), that is, n = 8 for Figure 
4-4
. The inductive assumption follows from our general approach. We simply assume 
that we can solve the problem (that is, find a maximum subset that forms a permutation) for n–1 people. The only 
thing that requires any creative problem solving is safely removing a single person so that the remaining subproblem 
is one that we can build on (that is, one that is part of a total solution).
If each person points to a different seat, the entire set forms a permutation, which must certainly be as big as 
it can be—no need to remove anyone because we’re already done. The base case is also trivial. For n = 1, there is 
nowhere to move. So, let’s say that n > 1 and that at least two persons are pointing to the same seat (the only way the 
permutation can be broken). Take a and b in Figure 
4-4
, for example. They’re both pointing to c, and we can safely say 

---

Chapter 4 
■
 InduCtIon and reCursIon ... and reduCtIon 
77
that one of them must be eliminated. However, which one we choose is crucial. Say, for example, we choose to remove 
a (both the person and the seat). We then notice that c is pointing to a, which means that c must also be eliminated. 
Finally, b points to c and must be eliminated as well—meaning that we could have simply eliminated b to begin with, 
keeping a and c (who just want to trade seats with each other).
When looking for inductive steps like this, it can often be a good idea to look for something that stands out. 
What, for example, about a seat that no one wants to sit in (that is, a node in the lower row in Figure 
4-4
 that has 
no in-edges)? In a valid solution (a permutation), at most one person (element) can be placed in (mapped to) any 
given seat (position). That means there’s no room for empty seats, because at least two people will then be trying to 
sit in the same seat. In other words, it is not only OK to remove an empty seat (and the corresponding person); it’s 
actually necessary. For example, in Figure 
4-4
, the nodes marked b cannot be part of any permutation, certainly not 
one of maximum size. Therefore, we can eliminate b, and what remains is a smaller instance (with n = 7) of the same 
problem , and, by the magic of induction, we’re done!
Or are we? We always need to make certain we’ve covered every eventuality. Can we be sure that there will always 
be an empty seat to eliminate, if needed? Indeed we can. Without empty seats, the n persons must collectively point to 
all the n seats, meaning that they all point to different seats, so we already have a permutation.
It’s time to translate the inductive/recursive algorithm idea into an actual implementation. An early decision 
is always how to represent the objects in the problem instances. In this case, we might think in terms of a graph or 
perhaps a function that maps between the objects. However, in essence, a mapping like this is just a position (0...n–1) 
associated with each element (also 0...n–1), and we can implement this using a simple list. For example, the example 
in Figure 
4-4
 (if a = 0, b = 1, ...) can be represented as follows:
 
>>> M = [2, 2, 0, 5, 3, 5, 7, 4]
>>> M[2] # c is mapped to a
0 
Tip
 
■
  When possible, try to use a representation that is as specific to your problem as possible. More general  
representations can lead to more bookkeeping and complicated code; if you use a representation that implicitly embodies 
some of the constraints of the problem, both finding and implementing a solution can be much easier.
We can now implement the recursive algorithm idea directly if we want, with some brute-force code for finding 
the element to eliminate. It won’t be very efficient, but an inefficient implementation can sometimes be an instructive 
place to start. See Listing 4-5 for a relatively direct implementation.