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 }[/math] permutations in the process.

Solution

Backtracking

9.6. Generate all structurally distinct binary search trees that store values [math]\displaystyle{ 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

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

Solution

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

Solution

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

Solution

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

Solution

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 [math]\displaystyle{ k }[/math]-element subsets of [math]\displaystyle{ n }[/math] items.

Solution

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.

Solution

9.32. You start with an empty room and a group of [math]\displaystyle{ n }[/math] people waiting outside. At each step, you may either admit one person into the room, or let one out. Can you arrange a sequence of [math]\displaystyle{ 2n }[/math] 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?

Solution

Back to Chapter List