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>k - 1</math permutations in the process.

Solution