in Algorithm Design Manual - Solutions, Doing Books

The Algorithm Design Manual: Chapter 7

7-1. A derangement is a permutation p of {1, . . . , n} such that no item is in its proper position, i.e. pi ̸= i for all 1 ≤ i ≤ n. Write an efficient backtracking program with pruning that constructs all the derangements of n items.

Solution

def testSolution(lst, nmax):
    for i, x in enumerate(lst):
        if lst[i] == (i + 1 + (nmax - len(lst))): # starts with 1
            return False
    return True


def genPermutation(lst, n, nmax):
    if n == 2:
        for i, x in enumerate(lst):
            yield [lst[i]] + lst[0:i] + lst[i + 1:]
    else:
        for i, x in enumerate(lst):
            for x in genPermutation(lst[0:i] + lst[i + 1:], n - 1, nmax):
                testCandidate = [lst[i]] + x
                if testSolution(testCandidate, nmax):
                    yield testCandidate
 

for x in genPermutation([1,2,3,4], 4, 4):
    print x

 

7-4. Anagrams are rearrangements of the letters of a word or phrase into a different word or phrase. Sometimes the results are quite striking. For example, “MANY VOTED BUSH RETIRED” is an anagram of “TUESDAY NOVEMBER THIRD,” which correctly predicted the result of the 1992 U.S. presidential election. Design and implement an algorithm for finding anagrams using combinatorial search and a dictionary.

Solution

def checkWord(reference, possible):
    tmp = reference[:]
    
    for c in possible:  # enough characters
        if c not in reference:
            return False
        else:
            try:
                tmp.remove(c)
            except:
                return False
    if tmp == []:
        return True
    else: 
        return tmp

def genAnagram(anagram, possibleWords):
    for word in possibleWords:
        x = checkWord(anagram, word)
        if x == True:
            yield [word]
        elif x:
            for y in genAnagram(x, possibleWords):
                yield [word] + [' '] + y


dictionary = open("/usr/share/dict/words").readlines()
anagram = "MANY VOTED BUSH RETIRED"
possibleWords = []

for word in dictionary:
    word = word.upper().strip()
    if len(word) < 4: 
        continue   

    tmp = list("".join(anagram.split()))
    skip = False
    for c in word:
        if c not in anagram:
            skip = True
            continue
        else:
            try:
                tmp.remove(c)
            except:
                skip = True
                continue
    if skip:
        continue
    else:
        possibleWords.append(word)

anagram = [x for x in anagram.strip() if x != ' ']
for x in genAnagram(anagram, possibleWords):
    print "".join(x)

7-8. Design and implement an algorithm for solving the maximum satisfiability prob- lem discussed in Section 14.10 (page 472).

Solution

from random import choice

def genSAT(f, n):
    if n == 0:
        yield []
    else:
        for v in [False, True]:
            for x in genSAT(f, n - 1):
                yield [v] + x

def solveSAT(f, n):
    for y in genSAT(f, n):
        if f(y):
            yield y

def solveSATHeur(f, n):
    for i in xrange(0, 2 ** n):
        y = [choice([False, True]) for i in range(n)]
        if f(y):
            return y

f = lambda (x1, x2, x3): (x1 and x2) or (x3 and not(x1))
print [x for x in solveSAT(f, 3)]

print solveSATHeur(f, 3)

 

7-14. Write a function to find all permutations of the letters in a particular string.
Solution Basically like in 7-1.

7-16. An anagram is a rearrangement of the letters in a given string into a sequence of dictionary words, like Steven Skiena into Vainest Knees. Propose an algorithm to construct all the anagrams of a given string.
Solution See 7-4.

7-19. Use a random number generator (rng04) that generates numbers from {0, 1, 2, 3, 4} with equal probability to write a random number generator that generates numbers from 0 to 7 (rng07) with equal probability. What are expected number of calls to rng04 per call of rng07?

Solution One basic idea is to use two events with equal probability eight times and count one of these events and use this as our number. E.g. we take 0, 1 from rng04 and encode it as zero and take 2, 3 from rng04 and encode it as one. Now zero and one happen with equal probability. We now generate enough numbers and count the ones which will be the number in rng07.
How many calls do we need? Let’s first analyze our encoded variable.

Prob                             #Calls
4/5                                 1
1/5 * 4/5                           2
(1/5)^2 * (4/5)                     3
(1/5)^3 * (4/5)                     4
...
(1/5)^k * (4/5)                     k + 1

That is, we need \lim_{n \rightarrow \infty} sum_{k=0}^{n} (\frac{1}{5})^k (k + 1) = \frac{25}{16} calls. Therefore we need \frac{25}{16} \cdot 8 = 12.5 calls for our rng07.

Leave a Reply for tst Cancel Reply

Write a Comment

Comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.