Source code online books for professionals by professionals

Listing 4-6.  Finding a Maximum Permutation
def max_perm(M):
    n = len(M)                                  # How many elements?
    A = set(range(n))                           # A = {0, 1, ... , n-1}
    count = [0]*n                               # C[i] == 0 for i in A
    for i in M:                                 # All that are "pointed to"
        count[i] += 1                           # Increment "point count"
    Q = [i for i in A if count[i] == 0]         # Useless elements
    while Q:                                    # While useless elts. left...
        i = Q.pop()                             # Get one
        A.remove(i)                             # Remove it
        j = M[i]                                # Who's it pointing to?
        count[j] -= 1                           # Not anymore...
        if count[j] == 0:                       # Is j useless now?
            Q.append(j)                         # Then deal w/it next
    return A                                    # Return useful elts.
 
8
If you’re using Python 2.6 or older, the result would be set([0, 2, 5]).
9
Inserting into or removing from the start of a list is a linear-time operation, remember? Generally not a good idea.

---

Chapter 4 
■
 InduCtIon and reCursIon ... and reduCtIon 
79
Tip
 
■
  In recent versions of python, the 
collections
 module contains the 
Counter
 class, which can count (hashable) 
objects for you. With it, the 
for
 loop in Listing 4-7 could have been replaced with the assignment 
count = Counter(M)
. 
this might have some extra overhead, but it would have the same asymptotic running time.
Listing 4-7.  A Naïve Solution to the Celebrity Problem
def naive_celeb(G):
    n = len(G)
    for u in range(n):                          # For every candidate...
        for v in range(n):                      # For everyone else...
            if u == v: continue                 # Same person? Skip.
            if G[u][v]: break                   # Candidate knows other
            if not G[v][u]: break               # Other doesn't know candidate
        else:
            return u                            # No breaks? Celebrity!
    return None                                 # Couldn't find anyone
 
Some simple experiments (see Chapter 2 for tips) should convince you that even for rather small problem 
instances, max_perm is quite a bit faster than naive_max_perm. They’re both pretty fast, though, and if all you’re 
doing is solving a single, moderately sized instance, you might be just as satisfied with the more direct of the two. 
The inductive thinking would still have been useful in providing you with a solution that could actually find the 
answer. You could, of course, have tried every possibility, but that would have resulted in a totally useless algorithm. 
If, however, you had to solve some really large instances of this problem or even if you had to solve many moderate 
instances, the extra thinking involved in coming up with a linear-time algorithm would probably pay off.