# Chapter 9

Jump to navigation
Jump to search

## Contents

# Combinatorial Search

### Permutations

- 9.1. A
*derangement*is a permutation**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle p}**of**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {1, . . . , n}}**such that no item is in its proper position, that is,**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle p_i 6= i}**for all**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 1 \leq i \leq n}**. Write an efficient backtracking program with pruning that constructs all the derangements of**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle n}**items.

- 9.2.
*Multisets*are allowed to have repeated elements. A multiset of n items may thus have fewer than**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle n!}**distinct permutations. For example, {1, 1, 2, 2} has only six distinct permutations: [1, 1, 2, 2], [1, 2, 1, 2], [1, 2, 2, 1], [2, 1, 1, 2], [2, 1, 2, 1], and [2, 2, 1, 1]. Design and implement an efficient algorithm for constructing all permutations of a multiset.

- 9.3. For a given a positive integer
**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle n}**, find all permutations of the**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 2n}**elements of the multiset**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle S = {1, 1, 2, 2, 3, 3, . . . , n, n}}**such that for each integer from 1 to**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle n}**the number of intervening elements between its two appearances is equal to value of the element. For example, when**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle n = 3}**the two possible solutions are [3, 1, 2, 1, 3, 2] and [2, 3, 1, 2, 1, 3].

- 9.4. Design and implement an algorithm for testing whether two graphs are isomorphic. The graph isomorphism problem is discussed in Section 19.9 (page 610). With proper pruning, graphs on hundreds of vertices can be tested in a reasonable time.

- 9.5. The set
**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {1, 2, 3, ..., n}}**contains a total of**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle n!}**distinct permutations. By listing and labeling all of the permutations in ascending lexicographic order, we get the following sequence for**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle n = 3}**:

**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle [123, 132, 213, 231, 312, 321]}**

- Give an efficient algorithm that returns the
**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle k}**th of**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle n!}**permutations in this see quence, for inputs**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle k}**. For efficiency it should not construct the first**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle k - 1}**permutations in the process.

### Backtracking

- 9.6. Generate all structurally distinct binary search trees that store values
**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 1 . . . n}**, for a given value of

- 9.7. Implement an algorithm to print all valid (meaning properly opened and closed) sequences of n pairs of parentheses.

- 9.8. Generate all possible topological orderings of a given DAG.

- 9.9. Given a specified total t and a multiset
**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle S}**of**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle S}**whose elements add up to**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle t}**. For example, if**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle t = 4}**and**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle S = {4, 3, 2, 2, 1, 1}}**, then there are four different sums that equal**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle t: 4, 3 + 1, 2 + 2}**, and**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 2 + 1 + 1}**. A number can be used within a sum up to the number of times it appears in**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle S}**, and a single number counts as a sum.

- 9.10. Given a specified total
**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle t}**and a multiset**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle t}**. For example, if**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle t = 4}**and**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle S = {4, 3, 2, 2, 1, 1}}**, then there are four different sums that equal**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle t: 4, 3 + 1, 2 + 2}**, and**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 2 + 1 + 1}**. A number can be used within a sum up to the number of times it appears in

- 9.11. A team assignment of
**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle n = 2k}**players is a partitioning of them into two teams with exactly**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle k}**people per team. For example, if the players are named**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {A, B, C, D}}**, there are three distinct ways to partition them into two equal teams:**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {{A, B}, {C, D}}, {{A, C}, {B, D}}, and {{A, D}, {B, C}}}**. - (a) List the 10 possible team assignments for
**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle n = 6}**players. - (b) Give an efficient back-tracking algorithm to construct all possible team assignments. Be sure to avoid repeating any solution.

- 9.12. Given an alphabet
**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \Sigma}**, a set of forbidden strings**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \Sigma}**without any element of**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \Sigma = {0, 1}, S = {01, 10}<math>, and <math>n = 4}**, the two possible solutions are 0000 and 1111. For**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle S = {0, 11}}**and**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle n = 4}**, no such string exists.

- 9.13. In the

- 9.14. You are given a weighted directed graph
**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle G}**with**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle m}**edges. The mean weight of a cycle is the sum of its edge weights divided by the number of its edges. Find a cycle in**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle G}**of minimum mean weight.

- 9.15. In the turnpike reconstruction problem, you are given a multiset
**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle D}**of**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle n(n - 1)/2}**distances. The problem is to place**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle D}**. For example, the distances**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle D = {1, 2, 3, 4, 5, 6}}**can be obtained by placing the second point 1 unit from the first, the third point 3 from the second, and the fourth point 2 from the third. Design and implement an efficient algorithm to find all solutions to the turnpike reconstruction problem. Exploit additive constraints when possible to accelerate the search. With proper pruning, problems with hundreds of points can be solved in reasonable time.

### Games and Puzzles

- 9.16. 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 US presidential election. Design and implement an algorithm for finding anagrams using combinatorial search and a dictionary.

- 9.17. Construct all sequences of moves that a knight on an
**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle n * n}**chessboard can make where the knight visits every square only once.

- 9.18. A Boggle board is an
**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle n * m}**grid of characters. For a given board, we seek to find all possible words that can be formed by a sequence of adjacent characters on the board, without repetition. For example, the board:

**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \begin{matrix} e & t & h & t\\ n & d & t & i\\ a & i & h & n\\ r & h & u & b \end{matrix}}**

- contains words like tide, dent, raid, and hide. Design an algorithm to construct the most words for a given board
**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle B}**consistent with a dictionary**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle D}**.

- 9.19. A Babbage square is a grid of words that reads the same across as it does down. Given a
**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle w}**and a dictionary of

**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \begin{vmatrix} h & a & i & r\\ a & i & d & e\\ i & d & l & e\\ r & e & e & f \end{vmatrix}\begin{vmatrix} h & a & i & r\\ a & l & t & o\\ i & t & e & m\\ r & o & m & b \end{vmatrix} }**

- 9.20. Show that you can solve any given Sudoku puzzle by finding the minimum vertex coloring of a specific, appropriately constructed 9 × 9 + 9 vertex graph.

### Combinatorial Optimization

For problems 9-21 to 9-27, implement a combinatorial search program to solve it for small instances. How well does your program perform in practice?

- 9.21. Design and implement an algorithm for solving the bandwidth minimization problem discussed in Section 16.2 (page 470).

- 9.22. Design and implement an algorithm for solving the maximum satisfiability problem discussed in Section 17.10 (page 537).

- 9.23. Design and implement an algorithm for solving the maximum clique problem discussed in Section 19.1 (page 586).

- 9.24. Design and implement an algorithm for solving the minimum vertex coloring problem discussed in Section 19.7 (page 604).

- 9.25. Design and implement an algorithm for solving the minimum edge coloring problem discussed in Section 19.8 (page 608).

- 9.26. Design and implement an algorithm for solving the minimum feedback vertex set problem discussed in Section 19.11 (page 618).

- 9.27. Design and implement an algorithm for solving the set cover problem discussed in Section 21.1 (page 678).

### Interview Problems

- 9.28. Write a function to find all permutations of the letters in a given string.

- 9.29. Implement an efficient algorithm for listing all

- 9.30. 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.

- 9.31. Telephone keypads have letters on each numerical key. Write a program that generates all possible words resulting from translating a given digit sequence (e.g. 145345) into letters.

- 9.32. You start with an empty room and a group of
**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 2n}**steps, so that every possible combination of people is achieved exactly once?

- 9.33. 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 is the expected number of calls to rng04 per call of rng07?

Back to Chapter List