This multivolume work on the analysis of algorithms has long been recognized as the definitive description of classical computer science. The three complete volumes published to date already comprise a unique and invaluable resource in programming theory and practice. Countless readers have spoken about the profound personal influence of Knuth's writings. Scientists have marveled at the beauty and elegance of his analysis, while practicing programmers have successfully applied his "cookbook" solutions to their day-to-day problems. All have admired Knuth for the breadth, clarity, accuracy, and good humor found in his books.To begin the fourth and later volumes of the set, and to update parts of the existing three, Knuth has created a series of small books called fascicles, which will be published t regular intervals. Each fascicle will encompass a section or more of wholly new or evised material. Ultimately, the content of these fascicles will be rolled up into the comprehensive, final versions of each volume, and the enormous undertaking that began in 1962 will be complete. Volume 4, Fascicle 2This fascicle inaugurates the eagerly awaited publication of Knuth's The Art of Computer Programming, Volume 4: Combinatorial Algorithms. Part of what will be a long chapter on combinatorial searching, the fascicle begins his treatment of how to generate all possibilities. Specifically, it discusses the generation of all n-tuples, then extends those ideas to all permutations. Such algorithms provide a natural motivation by means of which many of the key ideas of combinatorial mathematics can be introduced and explored. In this and other fascicles of Volume 4, Knuth illuminates important theories by discussing related games and puzzles. Even serious programming can be fun.

Donald E. Knuth is known throughout the world for his pioneering work on algorithms and programming techniques, for his invention of the T[subscript E]X and METAFONT systems for computer typesetting, and for his prolific and influential writing

fas_ci_cle /fas_ ek el / n . . . 1: a small bundle . . . an inflorescence consisting of a compacted cyme less capitate than a glomerule. . . 2: one of the divisions of a book published in parts --P. B. Gove,Webster's Third New International Dictionary(1961) This is the first of a series of updates that I plan to make available at regular intervals as I continue working toward the ultimate editions ofThe Art of Computer Programming. I was inspired to prepare fascicles like this by the example of Charles Dickens, who issued his novels in serial form; he published a dozen installments ofOliver Twistbefore having any idea what would become of Bill Sikes! I was thinking also of James Murray, who began to publish 350-page portions of theOxford English Dictionaryin 1884, finishing the letter B in 1888 and the letter C in 1895. (Murray died in 1915 while working on the letter T; my task is, fortunately, much simpler than his.) Unlike Dickens and Murray, I have computers to help me edit the material, so that I can easily make changes before putting everything together in its final form. Although I'm trying my best to write comprehensive accounts that need no further revision, I know that every page brings me hundreds of opportunities to make mistakes and to miss important ideas. My files are bursting with notes about beautiful algorithms that have been discovered, but computer science has grown to the point where I cannot hope to be an authority on all the material I wish to cover. Therefore I need extensive feedback from readers before I can finalize the official volumes. In other words, I think these fascicles will contain a lot of Good Stuff, and I'm excited about the opportunity to present everything I write to whoever wants to read it, but I also expect that beta-testers like you can help me make it Way Better. As usual, I will gratefully pay a reward of $2.56 to the first person who reports anything that is technically, historically, typographically, or politically incorrect. Charles Dickens usually published his work once a month, sometimes once a week; James Murray tended to finish a 350-page installment about once every 18 months. My goal, God willing, is to produce two 128-page fascicles per year.Most of the fascicles will represent new material destined for Volumes 4 and higher; but sometimes I will be presenting amendments to one or more of the earlier volumes. For example, Volume 4 will need to refer to topics that belong in Volume 3, but weren't invented when Volume 3 first came out. With luck, the entire work will make sense eventually. Fascicle Number One is about MMIX, the long-promised replacement for MIX. Thirty-seven years have passed since the MIX computer was designed, and computer architecture has been converging during those years towards a rather different style of machine. Therefore I decided in 1990 to replace MIX with a new computer that would contain even less saturated fat than its predecessor. Exercise 1.3.1-25 in the first three editions of Volume 1 spoke of an extended MIX called MixMaster, which was upward compatible with the old version. But MixMaster itself has long been hopelessly obsolete. It allowed for several gigabytes of memory, but one couldn't even use it with ASCII code to print lowercase letters. And ouch, its standard conventions for calling subroutines were irrevocably based on self-modifying instructions! Decimal arithmetic and self-modifying code were popular in 1962, but they sure have disappeared quickly as machines have gotten bigger and faster. Fortunately the modern RISC architecture has a very appealing structure, so I've had a chance to design a new computer that is not only up to date but also fun. Many readers are no doubt thinking, "Why does Knuth replace MIX by another machine instead of just sticking to a high-level programming language? Hardly anybody uses assemblers these days." Such peop