×

The art of computer programming. Vol. 4, Fasc. 0–4. Fasc. 0: Introduction to combinatorial algorithms and Boolean functions. Fasc. 1: Bitwise tricks & techniques, binary decision diagrams. Fasc. 2: Generating all tuples and permutations. Fasc. 3: Generating all combinations and partitions. Fasc. 4: Generating all trees. History of combinatorial generation. Fascicle 0: 3rd printing 2009; Fascicle 1: 1st printing 2009; Fascicle 2: 2nd printing 2009; Fascicle 3: 2nd printing 2009; Fascicle 4: 3rd printing 2009. (English) Zbl 1178.68372

Upper Saddle River, NJ: Addison-Wesley (ISBN 978-0-3216-3713-0/pbk/set; 978-0-321-53496-5/Fasc. 0; 978-0-321-58050-4/Fasc. 1; 978-0-201-85393-3/Fasc. 2; 978-0-201-85394-0/Fasc. 3; 978-0-321-33570-8/Fasc. 4). Fasc. 0, xii, 216 p.; Fasc. 1, viii, 260 p.; Fasc. 2, v, 129 p.; Fasc. 3, iv, 150 p.; Fasc. 4, vi, 120 p. (2009).
Donald E. Knuth started an effort to write a book on compilers in 1962, but soon realized that its scope would have to be much wider. This led to Fundamental Algorithms, the first volume of The Art of Computer Programming, as published in 1968. Volume 2 on Seminumerical Algorithms and Volume 3 on Searching and Sorting followed in 1969 and 1973, respectively. All of them have been revised since, with the current versions published in the later 1990’s.
I believe most of the computer scientists will agree that this collection of three volumes provides “a definitive description of classical computer science”, as Addison-Wesley, its publisher, claims. Indeed, many of us have been growing up professionally with the nutrition as provided by these books, and we are certainly looking forward to seeing continuous efforts made towards completing this ambitious project, which is supposed to contain seven volumes [see D. E. Knuth’s website, The Art of Computer Programming (TAOCP), available at http://www-cs-faculty.stanford.edu/~knuth/taocp.html].
The subject of Volume 4 is combinatorial algorithms, which deal with structured objects, thus often difficult to design, construct and analyze. On the other hand, most of the algorithms that we have to apply to real applications, e.g., graph algorithms, fall into this category, thus the need. Since the author feels that “the task of completing Volume 4 will take many years” and he “can’t wait for people to begin reading what” he has “written so far and provide valuable feedback”, Knuth has made available some segments of Volume 4, referred to as fascicles, initially online at the web page devoted to these books [loc. cit.], which were then published by Addison-Wesley between 2005 and 2009.
This collection of five fascicles, containing more than 870 pages, constitutes Section 7.1 and Section 7.2.1, part of Chapter 7 on Combinatorial Searching. This is the subject of our review, a task similar to writing a review for the Bible.
After introducing a rich set of exemplary combinatorial structures, Knuth focuses on the combinatorial structure generation problem in Section 7.2.1. To let readers better understand his intention, he makes a distinction among several related tasks at the very beginning of the subject [see p.1 of Fascicle 2]. For example, by “enumerating” all the permutations of 1, 2, and 3, he means the number 6, i.e., the number of all the permutations for these three symbols; by “listing” these permutations, he means the task of making such a list, i.e., \(123, 132, 213, 231, 312,\) and \(321\). On the other hand, by “generating” all the permutations of these three numbers”, he means “to have them present momentarily in some data structure, so that a program can examine each permutation one at a time.”
The above enumeration problem has been thoroughly investigated in the literature, such as [R. Stanley, Enumerative combinatorics. Vol. 1. 2nd ed. Cambridge Studies in Advanced Mathematics. 49. Cambridge: Cambridge University Press (1997; Zbl 0889.05001)], [P. Flajolet and R. Sedgewick, Analytic combinatorics. Cambridge: Cambridge University Press (2009; Zbl 1165.05001)], while the listing problem is clearly subsumed by the generating problem. On the other hand, although this generating problem has been discussed in some of the applied combinatoric studies, e.g., [A. Tucker, Applied combinatorics. 5th ed. Hoboken, NJ: Wiley (2007)], it gets an encyclopedic treatment in this set of fascicles, where Knuth studies the generation of all the tuples, permutations, combinations, integer partitions, set partitions and trees, with the focus being placed on methods, i.e., algorithms, models and certainly mathematical ideas behind the scene, lots of them.
We do need such a generating mechanism often. For example, when looking for the number of all the shortest paths between two nodes in an arrangement graph [K. Day and A. Tripathi, “Arrangement graphs: a class of generalized star graphs”, Inf. Process. Lett. 42, No. 5, 235–241 (1992; Zbl 0772.68005)], I have a need to construct all the partitions of some \(g\) cycles in \(n-k\) classes \(T_1, \dots, T_{n-k},\) by
1)
forming a tuple \((t_1, t_2, \dots, t_{n-k})\) such that for all \(i \in [1, n-k], t_i \geq 0,\) and \(t_1+t_2+\cdots+t_{n-k}=g;\) and
2)
for any such a tuple \((t_1, t_2, \ldots, t_{n-k}),\) selecting \(t_1\) cycles out of a total of \(g_I\) cycles in \(g_I \choose t_1\) ways and place them in \(T_1,\) selecting \(t_2\) cycles out of the remaining \(g_I-t_1\) cycles in \(g_I-t_1 \choose t_2\) ways and place them in \(T_2,\) …, and finally selecting the remaining \(t_{n-k}\) cycles in exactly one way and place them in \(T_{n-k}\).

It is clear that Step 1 is indirectly involved with an integer partition generation problem [Algorithm H, p.38 of Fascicle 3], while Step 2 is directly involved with a combination generation problem [Algorithm L, p.4 in Fascicle 3]. In both cases, it is not enough to merely enumerate such partitions, but there is no need to explicitly list all such partitions, either. What we need here is to exhaustively come up with each and every such partition so that some succeeding construction(s) and/or operation(s) can be carried out. This is indeed what the “generating” operation is intended to do in this set of fascicles.
Since combinatorial algorithms are notoriously time-consuming, and a binary system can not only encode all the objects, but also potentially lead to a significant speed up of some of the combinatorial algorithms, Knuth discusses in detail the binary system in Section 7.1, including Boolean functions and their efficient evaluation, algorithms with heavy use of Boolean operations, i.e., bitwise operators such as those used in system programming, and binary decision diagrams, an efficient data structure to represent and manipulate Boolean functions.
This subsection ends with a historic review of combinatorial generation with an international scope.
Although we have to wait for many other interesting subjects to come out later, e.g., backtracking in Section 7.2.2, the shortest path problem in Section 7.3, graph and network algorithms in Sections 7.4 and 7.5, optimization-related discussion in Sections 7.7 to 7.9, and recursion in Section 8, let’s do enjoy what we have here in front of us, another typical “Knuth book”: technically correct, thoroughly researched, richly cited, elegantly written, and actually quite readable, if you make a serious effort.
By the way, if you have a good deal of time to spare, you can certainly try some of the exercises, 366 of them for just Section 7.1.1; and if you can’t figure out an answer for some of the problems (the problem as given in Exercise 133 of Section 7.1.1 takes an MIT Ph.D. thesis to solve), you can check out the answers. In fact, Knuth has provided an answer, either a hint, a reference, or a complete solution, to almost all of the exercises as contained in these fascicles, with Exercise 92 of Section 7.1.1 being one of the few exceptions. As a result, e.g., out of the 260 pages of Fascicle 1, the segment on Answers to Exercises takes 95 pages.
Again, I would whole-heartedly recommend this book to my colleagues who have some time to spare, and would like to get into one of the greatest minds in Computer Science.

MSC:

68R05 Combinatorics in computer science
68-02 Research exposition (monographs, survey articles) pertaining to computer science
05-02 Research exposition (monographs, survey articles) pertaining to combinatorics
05A05 Permutations, words, matrices
05A17 Combinatorial aspects of partitions of integers
05A18 Partitions of sets
05C05 Trees
05C30 Enumeration in graph theory
68Q25 Analysis of algorithms and problem complexity
68R15 Combinatorics on words
68W05 Nonnumerical algorithms