Chapter 9

Combinatorial Search

Permutations

9.1. A derangement is a permutation [math]\displaystyle{ p }[/math] of [math]\displaystyle{ {1, . . . , n} }[/math] such that no item is in its proper position, that is, [math]\displaystyle{ p_i 6= i }[/math] for all [math]\displaystyle{ 1 \leq i \leq n }[/math]. Write an efficient backtracking program with pruning that constructs all the derangements of [math]\displaystyle{ n }[/math] items.

Soluiton

9.2. Multisets are allowed to have repeated elements. A multiset of n items may thus have fewer than [math]\displaystyle{ n! }[/math] 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 [math]\displaystyle{ n }[/math], find all permutations of the [math]\displaystyle{ 2n }[/math] elements of the multiset [math]\displaystyle{ S = {1, 1, 2, 2, 3, 3, . . . , n, n} }[/math] such that for each integer from 1 to [math]\displaystyle{ n }[/math] the number of intervening elements between its two appearances is equal to value of the element. For example, when [math]\displaystyle{ n = 3 }[/math] the two possible solutions are [3, 1, 2, 1, 3, 2] and [2, 3, 1, 2, 1, 3].

Solution

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 [math]\displaystyle{ {1, 2, 3, ..., n} }[/math] contains a total of [math]\displaystyle{ n! }[/math] distinct permutations. By listing and labeling all of the permutations in ascending lexicographic order, we get the following sequence for [math]\displaystyle{ n = 3 }[/math]:

[math]\displaystyle{ [123, 132, 213, 231, 312, 321] }[/math]

Give an efficient algorithm that returns the [math]\displaystyle{ k }[/math]th of [math]\displaystyle{ n! }[/math] permutations in this see quence, for inputs [math]\displaystyle{ n }[/math] and [math]\displaystyle{ k }[/math]. For efficiency it should not construct the first [math]\displaystyle{ k - 1\lt /math permutations in the process. [[9.5|Solution]] ===Backtracking=== :9.6. Generate all structurally distinct binary search trees that store values \lt math\gt 1 . . . n }[/math], for a given value of [math]\displaystyle{ n }[/math].

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

Solution

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

9.9. Given a specified total t and a multiset [math]\displaystyle{ S }[/math] of [math]\displaystyle{ n }[/math] integers, find all distinct subsets from [math]\displaystyle{ S }[/math] whose elements add up to [math]\displaystyle{ t }[/math]. For example, if [math]\displaystyle{ t = 4 }[/math] and [math]\displaystyle{ S = {4, 3, 2, 2, 1, 1} }[/math], then there are four different sums that equal [math]\displaystyle{ t: 4, 3 + 1, 2 + 2 }[/math], and [math]\displaystyle{ 2 + 1 + 1 }[/math]. A number can be used within a sum up to the number of times it appears in [math]\displaystyle{ S }[/math], and a single number counts as a sum.

Solution

9.10. Given a specified total [math]\displaystyle{ t }[/math] and a multiset [math]\displaystyle{ S }[/math] of [math]\displaystyle{ n }[/math] integers, find all distinct subsets from [math]\displaystyle{ S }[/math] whose elements add up to [math]\displaystyle{ t }[/math]. For example, if [math]\displaystyle{ t = 4 }[/math] and [math]\displaystyle{ S = {4, 3, 2, 2, 1, 1} }[/math], then there are four different sums that equal [math]\displaystyle{ t: 4, 3 + 1, 2 + 2 }[/math], and [math]\displaystyle{ 2 + 1 + 1 }[/math]. A number can be used within a sum up to the number of times it appears in [math]\displaystyle{ S }[/math], and a single number counts as a sum.

9.11. A team assignment of [math]\displaystyle{ n = 2k }[/math] players is a partitioning of them into two teams with exactly [math]\displaystyle{ k }[/math] people per team. For example, if the players are named [math]\displaystyle{ {A, B, C, D} }[/math], there are three distinct ways to partition them into two equal teams: [math]\displaystyle{ {{A, B}, {C, D}}, {{A, C}, {B, D}}, and {{A, D}, {B, C}} }[/math].

(a) List the 10 possible team assignments for [math]\displaystyle{ n = 6 }[/math] players.

(b) Give an efficient back-tracking algorithm to construct all possible team assignments. Be sure to avoid repeating any solution.

Solution

9.12. Given an alphabet [math]\displaystyle{ \Sigma }[/math], a set of forbidden strings [math]\displaystyle{ S }[/math], and a target length [math]\displaystyle{ n }[/math], give an algorithm to construct a string of length [math]\displaystyle{ n }[/math] on [math]\displaystyle{ \Sigma }[/math] without any element of [math]\displaystyle{ S }[/math] as a substring. For [math]\displaystyle{ \Sigma = {0, 1}, S = {01, 10}\lt math\gt , and \lt math\gt n = 4 }[/math], the two possible solutions are 0000 and 1111. For [math]\displaystyle{ S = {0, 11} }[/math] and [math]\displaystyle{ n = 4 }[/math], no such string exists.

9.13. In the [math]\displaystyle{ k }[/math]-partition problem, we need to partition a multiset of positive integers into [math]\displaystyle{ k }[/math] disjoint subsets that have equal sum. Design and implement an algorithm for solving the [math]\displaystyle{ k }[/math]-partition problem.

Solution

9.14. You are given a weighted directed graph [math]\displaystyle{ G }[/math] with [math]\displaystyle{ n }[/math] vertices and [math]\displaystyle{ m }[/math] 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 [math]\displaystyle{ G }[/math] of minimum mean weight.

9.15. In the turnpike reconstruction problem, you are given a multiset [math]\displaystyle{ D }[/math] of [math]\displaystyle{ n(n - 1)/2 }[/math] distances. The problem is to place [math]\displaystyle{ n }[/math] points on the line such that their pairwise distances are [math]\displaystyle{ D }[/math]. For example, the distances [math]\displaystyle{ D = {1, 2, 3, 4, 5, 6} }[/math] 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.

Solution

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 [math]\displaystyle{ n * n }[/math] chessboard can make where the knight visits every square only once.

Solution

9.18. A Boggle board is an [math]\displaystyle{ n * m }[/math] 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:

[math]\displaystyle{ \begin{matrix} e & t & h & t\\ n & d & t & i\\ a & i & h & n\\ r & h & u & b \end{matrix} }[/math]

contains words like tide, dent, raid, and hide. Design an algorithm to construct the most words for a given board [math]\displaystyle{ B }[/math] consistent with a dictionary [math]\displaystyle{ D }[/math].

9.19. A Babbage square is a grid of words that reads the same across as it does down. Given a [math]\displaystyle{ k }[/math]-letter word [math]\displaystyle{ w }[/math] and a dictionary of [math]\displaystyle{ n }[/math] words, find all Babbage squares starting with that word. For example, two squares for the word hair are:

[math]\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} }[/math]

Solution

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

9.21

9.22

9.23

9.24

9.25

9.26

9.27

Interview Problems

9.28

9.27

9.28

9.29

9.30

9.31

9.32

9.33

Back to Chapter List