TAOCP 7.2.1.1 Exercise 112

Section 7.2.1.1: Generating All n-Tuples

Exercise 112. ▶ [25] [25] Continuing the previous exercise, how far can we go by inserting signs into 12345678987654321? For example, 100 = −1234 −5 −6 + 7898 −7 −6543 −2 −1. 7.2.1.2. Generating all permutations. After n-tuples, the next most im- portant item on nearly everybody’s wish list for combinatorial generation is the task of visiting all permutations of some given set or multiset. Many different ways have been devised to solve this problem. In fact, almost as many different algorithms have been published for unsorting as for sorting! We will study the most important permutation generators in this section, beginning with a classical method that is both simple and flexible: Algorithm L (Lexicographic permutation generation). Given a sequence of n elements a1a2 . . . an, initially sorted so that a1 ≤a2 ≤· · · ≤an, (1) this algorithm generates all permutations of {a1, a2, . . . , an}, visiting them in lexicographic order. (For example, the permutations of {1, 2, 2, 3} are 1223, 1232, 1322, 2123, 2132, 2213, 2231, 2312, 2321, 3122, 3212, 3221, ordered lexicographically.) An auxiliary element a0 is assumed to be present for convenience; a0 must be strictly less than the largest element an. L1. [Visit.] Visit the permutation a1a2 . . . an. L2. [Find j.] Set j ←n −1. If aj ≥aj+1, decrease j by 1 repeatedly until aj < aj+1. Terminate the algorithm if j = 0. (At this point j is the smallest subscript such that we’ve already visited all permutations beginning with a1 . . . aj. So the lexicographically next permutation will make aj larger.) L3. [Increase aj.] Set l ←n. If aj ≥al, decrease l by 1 repeatedly until aj < al. Then interchange aj ↔al. (Since aj+1 ≥· · · ≥an, element al is the smallest element greater than aj that can legitimately follow a1 . . . aj−1 in a permutation. Before the interchange we had aj+1 ≥· · · ≥al−1 ≥al > aj ≥ al+1 ≥· · · ≥an; after the interchange, we have aj+1 ≥· · · ≥al−1 ≥aj > al ≥al+1 ≥· · · ≥an.) L4. [Reverse aj+1 . . . an.] Set k ←j + 1 and l ←n. Then, while k < l, inter- change ak ↔al and set k ←k + 1, l ←l −1. Return to L1. This algorithm goes back to Narayana Pandita in 14th-century India (see Section 7.2.1.7); it also appeared in C. F. Hindenburg’s preface to Specimen Analyticum de Lineis Curvis Secundi Ordinis by C. F. Rüdiger (Leipzig: 1784), xlvi–xlvii, and it has been frequently rediscovered ever since. The parenthetical remarks in steps L2 and L3 explain why it works.

320 COMBINATORIAL SEARCHING 7.2.1.2 Tin tan din dan bim bam bom bo, tan tin din dan bam bim bo bom, tin tan dan din bim bam bom bo, tan tin dan din bam bim bo bom, tan dan tin bam din bo bim bom, . . . . Tin tan din dan bim bam bom bo., DOROTHY L. SAYERS, The Nine Tailors (1934) A permutation on the ten decimal digits is simply a 10 digit decimal number in which all digits are distinct. Hence all we need to do is to produce all 10 digit numbers and select only those whose digits are distinct. Isn’t it wonderful how high speed computing saves us from the drudgery of thinking! We simply program k + 1 →k and examine the digits of k for undesirable equalities. This gives us the permutations in dictionary order too! On second sober thought . . . we do need to think of something else., D. H. LEHMER (1957) In general, the lexicographic successor of any combinatorial pattern a1 . . . an is obtainable by a three-step procedure:

1. Find the largest j such that aj can be increased.
2. Increase aj by the smallest feasible amount.
3. Find the lexicographically least way to extend the new a1 . . . aj to a complete pattern. Algorithm L follows this general procedure in the case of permutation generation, just as Algorithm 7.2.1.1M followed it in the case of n-tuple generation; we will see numerous further instances later, as we consider other kinds of combinatorial patterns. Notice that we have aj+1 ≥· · · ≥an at the beginning of step L4. Therefore the first permutation beginning with the current prefix a1 . . . aj is a1 . . . ajan . . . aj+1, and step L4 produces it by doing ⌊(n −j)/2⌋interchanges. In practice, step L2 finds j = n −1 half of the time when the elements are distinct, because exactly n!/2 of the n! permutations have an−1 < an. Therefore Algorithm L can be speeded up by recognizing this special case, without making it significantly more complicated. (See exercise 1.) Similarly, the probability that j ≤n−t is only 1/t! when the a’s are distinct; hence the loops in steps L2– L4 usually go very fast. Exercise 6 analyzes the running time in general, showing that Algorithm L is reasonably efficient even when equal elements are present, unless some values appear much more often than others do in the multiset {a1, a2, . . . , an}. Adjacent interchanges. We saw in Section 7.2.1.1 that Gray codes are ad- vantageous for generating n-tuples, and similar considerations apply when we want to generate permutations. The simplest possible change to a permutation is to interchange adjacent elements, and we know from Chapter 5 that any permutation can be sorted into order if we make a suitable sequence of such interchanges. (For example, Algorithm 5.2.2B works in this way.) Hence we can

7.2.1.2 GENERATING ALL PERMUTATIONS 321 go backward and obtain any desired permutation, by starting with all elements in order and then exchanging appropriate pairs of adjacent elements. A natural question now arises: Is it possible to run through all permutations of a given multiset in such a way that only two adjacent elements change places at every step? If so, the overall program that is examining all permutations will often be simpler and faster, because it will only need to calculate the effect of an exchange instead of to reprocess an entirely new array a1 . . . an each time. Alas, when the multiset has repeated elements, we can’t always find such a Gray-like sequence. For example, the six permutations of {1, 1, 2, 2} are con- nected to each other in the following way by adjacent interchanges: 1122 1212 2112 1221 2121 2211; (2) this graph has no Hamiltonian path. But most applications deal with permutations of distinct elements, and for this case there is good news: A simple algorithm makes it possible to generate all n! permutations by making just n! −1 adjacent interchanges. Furthermore, another such interchange returns to the starting point, so we have a Hamiltonian cycle analogous to Gray binary code. The idea is to take such a sequence for {1, . . . , n −1} and to insert the number n into each permutation in all ways. For example, if n = 4 the sequence (123, 132, 312, 321, 231, 213) leads to the columns of the array 1234 1324 3124 3214 2314 2134 1243 1342 3142 3241 2341 2143 1423 1432 3412 3421 2431 2413 4123 4132 4312 4321 4231 4213 (3) when 4 is inserted in all four possible positions. Now we obtain the desired sequence by reading downwards in the first column, upwards in the second, down- wards in the third, . . . , upwards in the last: (1234, 1243, 1423, 4123, 4132, 1432, 1342, 1324, 3124, 3142, . . . , 2143, 2134). In Section 5.1.1 we studied the inversions of a permutation, namely the pairs of elements (not necessarily adjacent) that are out of order. Every interchange of adjacent elements changes the total number of inversions by ±1. In fact, when we consider the so-called inversion table c1 . . . cn of exercise 5.1.1–7, where cj is the number of elements lying to the right of j that are less than j, we find that the permutations in (3) have the following inversion tables: 0000 0010 0020 0120 0110 0100 0001 0011 0021 0121 0111 0101 0002 0012 0022 0122 0112 0102 0003 0013 0023 0123 0113 0103 (4) And if we read these columns alternately down and up as before, we obtain precisely the reflected Gray code for mixed radices (1, 2, 3, 4), as in Eqs. (46)–(51)

Verified: no
Solve time: 5m09s

No exercise statement is included after “Write the solution now.” The text contains the section context for 7.2.1.1, but not the actual problem to solve.

Provide the exact exercise number and statement (e.g., 7.2.1.1.X), and I will produce a full TAOCP-style solution.