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 calls. Therefore we need
calls for our rng07.
Hi. Could you please explain 7-2 to me?
Hey, there’s a nice algorithm for this problem using lexicographical ordering: http://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order – you may want to take a look at it.