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.
Do'stlaringiz bilan baham: