Source code online books for professionals by professionals

Listing 4-5.  A Naïve Implementation of the Recursive Algorithm Idea for Finding a Maximum Permutation
def naive_max_perm(M, A=None):
    if A is None:                               # The elt. set not supplied?
        A = set(range(len(M)))                  # A = {0, 1, ... , n-1}
    if len(A) == 1: return A                    # Base case -- single-elt. A
    B = set(M[i] for i in A)                    # The "pointed to" elements
    C = A - B                                   # "Not pointed to" elements
    if C:                                       # Any useless elements?
        A.remove(C.pop())                       # Remove one of them
        return naive_max_perm(M, A)             # Solve remaining problem
    return A                                    # All useful -- return all
 

---

Chapter 4 
■
 InduCtIon and reCursIon ... and reduCtIon 
78
The function naive_max_perm receives a set of remaining people (A) and creates a set of seats that are pointed  
to (B). If it finds an element in A that is not in B, it removes the element and solves the remaining problem recursively. 
Let’s use the implementation on our example, M.
8
 
>>> naive_max_perm(M)
{0, 2, 5}
 
So, a, c, and f can take part in the permutation. The others will have to sit in nonfavorite seats.
The implementation isn’t too bad. The handy set type lets us manipulate sets with ready-made high-level operations, 
rather than having to implement them ourselves. There are some problems, though. For one thing, we might want an 
iterative solution. This is easily remedied—the recursion can quite simply be replaced by a loop (like we did for insertion 
sort and selection sort). A worse problem, though, is that the algorithm is quadratic! (Exercise 4-10 asks you to show this.)
The most wasteful operation is the repeated creation of the set B. If we could just keep track of which chairs are 
no longer pointed to, we could eliminate this operation entirely. One way of doing this would be to keep a count for 
each element. We could decrement the count for chair x when a person pointing to x is eliminated, and if x ever got a 
count of zero, both person and chair x would be out of the game.
Tip
 
■
  this idea of reference counting can be useful in general. It is, for example, a basic component in many systems 
for garbage collection (a form of memory management that automatically deallocates objects that are no longer useful). 
You’ll see this technique again in the discussion of topological sorting.
There may be more than one element to be eliminated at any one time, but we can just put any new ones we 
come across into a “to-do” list and deal with them later. If we needed to make sure the elements were eliminated in 
the order in which we discover that they’re no longer useful, we would need to use a first-in, first-out queue such as 
the deque class (discussed in Chapter 5).
9
 We don’t really care, so we could use a set, for example, but just appending 
to and popping from a list will probably give us quite a bit less overhead. But feel free to experiment, of course. You 
can find an implementation of the iterative, linear-time version of the algorithm in Listing 4-6.