Donald E. Knuth - Art of Computer Programming, Volume 4A, The: Combinatorial Algorithms, Part 1

To put all the good stuff into one book is patently impossible,
and attempting even to be reasonably comprehensive
about certain aspects of the subject is likely to lead to runaway growth.

GERALD B. FOLLAND, Editors Corner (2005)

The title of Volume 4 is Combinatorial Algorithms, and when I proposed it I was strongly inclined to add a subtitle: The Kind of Programming I Like Best. My editors have decided to tone down such exuberance, but the fact remains that programs with a combinatorial flavor have always been my favorites.

On the other hand Ive often been surprised to find that, in many peoples minds, the word combinatorial is linked with computational difficulty. Indeed, Samuel Johnson, in his famous dictionary of the English language (1755), said that the corresponding noun is now generally used in an ill sense. Colleagues tell me tales of woe, in which they report that the combinatorics of the situation defeated us. Why is it that, for me, combinatorics arouses feelings of pure pleasure, yet for many others it evokes pure panic?

Its true that combinatorial problems are often associated with humongously large numbers. Johnsons dictionary entry also included a quote from Ephraim Chambers, who had stated that the total number of words of length 24 or less, in a 24-letter alphabet, is 1,391,724,288,887,252,999,425,128,493,402,200. The corresponding number when we replace 24 by 10 in Chamberss statement is 11,111,111,110; and its only 3905 when reduce the parameter to 5. Thus a combinatorial explosion certainly does occur as the size of the problem grows from 5 to 10 to 24 and beyond.

Computing machines have become tremendously more powerful throughout my life. As I write these words, I know that they are being processed by a laptop whose speed is more than 100,000 times faster than the trusty IBM Type 650 computer to which Ive dedicated these books. My current machines memory capacity is also more than 100,000 times greater. Tomorrows computers will be even faster and more capacious. But these amazing advances have not diminished peoples craving for answers to combinatorial questions; quite the contrary. Our once-unimaginable ability to compute so rapidly has raised our expectations, and whetted our appetite for more because, in fact, the size of a combinatorial problem can increase more than 100,000-fold when n simply increases by 1.

Combinatorial algorithms can be defined informally as techniques for the high-speed manipulation of combinatorial objects such as permutations or graphs. We typically try to find patterns or arrangements that are the best possible ways to satisfy certain constraints. The number of such problems is vast, and the art of writing such programs is especially important and appealing because a single good idea can save years or even centuries of computer time.

Indeed, the fact that good algorithms for combinatorial problems can have a terrific payoff has led to terrific advances in the state of the art. Many problems that once were thought to be intractable can now be polished off with ease, and many algorithms that once were known to be good have now become better. Starting about 1970, computer scientists began to experience a phenomenon that we called Floyds Lemma: Problems that seemed to need