View Larger Image	Donald E. Knuth Addison-Wesley, Paperback, Published February 2005, 127 pages, ISBN 0201853930
	List Price: $19.99 Our Price: $16.50 You Save: $3.49 (17% Off)
	Availability: Out-Of-Stock

People who purchase this book frequently purchase:

• The Art of Computer Programming, Volume 1, Fascicle 1: MMIX -- A RISC Computer for the New Millennium; Donald E. Knuth, $16.50, 17% Off!
• The Art of Computer Programming, Volume 4, Fascicle 3: Generating All Combinations and Partitions; Donald E. Knuth, $16.50, 17% Off!
• The Art of Computer Programming, Volumes 1-3 Boxed Set, 2nd Edition; Donald E. Knuth, $145.95, 23% Off!
• The Art of Computer Programming, Volume 4, Fascicle 4: Generating All Trees -- History of Combinatorial Generation; Donald E. Knuth, $15.95, 20% Off!

• Programming : Algorithms
• Programming Languages : Other Programming Languages

• Addison-Wesley

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 2

This 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.

Preface

I am grateful to all my friends, and record here and now my most especial appreciation to those friends who, after a decent interval, stopped asking me, "How's the book coming?"
--Peter J. Gomes, The Good Book (1996)

This booklet is Fascicle 2 of The Art of Computer Programming, Volume 4: Combinatorial Algorithms. As explained in the preface to Fascicle 1 of Volume 1, I'm circulating the material in this preliminary form because I know that the task of completing Volume 4 will take many years; I can't wait for people to begin reading what I've written so far and to provide valuable feedback.

There will also be a Fascicle 1 for Volume 4. But I've written Fascicle 2 first. Experienced programmers will understand that the initialization of a program usually can't be written properly until after the main body has been fleshed out.

To put the material in context, this fascicle contains Sections 7.2.1.1 and 7.2.1.2 of a long, long chapter on combinatorial searching. Chapter 7 will eventually fill three volumes (namely Volumes 4A, 4B, and 4C), assuming that I'm able to remain healthy. It will begin with a short review of graph theory, with emphasis on some highlights of significant graphs in The Stanford GraphBase, from which I will be drawing many examples. Then comes Section 7.1, which deals with bitwise manipulation and with algorithms relating to Boolean functions. Section 7.2 is about generating all possibilities, and it begins with Section 7.2.1: Generating Basic Combinatorial Patterns. That sets the stage for the main contents of the present booklet, namely Section 7.2.1.1 (where I get the ball rolling by dealing with the generation of n-tuples) and Section 7.2.1.2 (which extends the ideas to permutations). Then will come Section 7.2.1.3 (about combinations), Section 7.2.1.4 (about integer partitions), and Section 7.2.1.5 (about set partitions), all in Fascicle 3. Section 7.2.1.6 (about trees) and Section 7.2.1.7 (about the history of combinatorial generation) will comprise Fascicle 4. Section 7.2.2 will deal with backtracking in general. And so it will go on, if all goes well; an outline of the entire Chapter 7 as currently envisaged appears on the taocp webpage that is cited on page ii.

I had great pleasure writing this material, akin to the thrill of excitement that I felt when writing Volume 2 many years ago. As in Volume 2, where I found to my delight that the basic principles of elementary probability theory and number theory arose naturally in the study of algorithms for random number generation and arithmetic, I learned while preparing Section 7.2.1 that the basic principles of elementary combinatorics arise naturally and in a highly motivated way when we study algorithms for combinatorial generation. Thus, I found once again that a beautiful story was "out there" waiting to be told.

My original intention was to devote far less space to this topic. But when I saw how fundamental the ideas were for combinatorial studies in general, I knew that I could never be happy unless I covered the basics quite thoroughly. Therefore I've done my best to build a solid foundation of theoretical and practical ideas that will support many kinds of reliable superstructures.

The topic of combinatorial generation has not only given me a chance to discuss important mathematical theories, it also has led to other kinds of fun, because of its many connections to amusing games and puzzles. Good puzzles are great aids to education, and I intend to continue focusing on recreational topics throughout Volume 4.

The average boy who abhors square root or algebra finds delight in working puzzles which involve similar principles, and may be led into a course of study which would develop the mathematical and inventive bumps in a way to astonish the family phrenologist.
--Sam Loyd, The World of Puzzledom (1896)

I shall happily pay a finder's fee of $2.56 for each error in this fascicle when it is first reported to me, whether that error be typographical, technical, or historical. The same reward holds for items that I forgot to put in the index. And valuable suggestions for improvements to the text are worth 32 cents each. (Furthermore, if you find a better solution to an exercise, I'll actually reward you with immortal glory instead of mere money, by publishing your name in the eventual book:-)

I wish to thank Yoichi Hariguchi for helping me to build and rebuild the computer on which this booklet was written. And I also want to thank Frank Ruskey for bravely foisting an early draft of this material on college students and for telling me about his classroom experiences.

Notations that are used here and not otherwise explained can be found in the Index to Notations at the end of Volumes 1, 2, or 3. Those indices point to the places where further information is available. Of course Volume 4 will some day contain its own Index to Notations.

Machine-language examples in all future editions of The Art of Computer Programming will be based on the MMIX computer, which is defined in Section 1.3.1' of Volume 1, Fascicle 1. Cross-references to Sections 1.3.1', 1.3.2', 1.4.1', 1.4.2', and 1.4.3' in the present booklet refer to that fascicle.Cross references to yet-unwritten material sometimes appear as '00' in the following pages; this impossible value is a placeholder for the actual numbers to be supplied later.

Happy reading!

D. E. K.

Stanford, California

December 2004

Table of Contents

Chapter 7 Combinatorial Searching

7.2. Generating All Possibilities

7.2.1. Generating Basic Combinatorial Patterns

7.2.1.1. Generating all n-tuples

7.2.1.2. Generating all permutations

Answers to Exercises

Index and Glossary

About the Author

Donald E. Knuth was born on January 10, 1938 in Milwaukee, Wisconsin. He studied mathematics as an undergraduate at Case Institute of Technology, where he also wrote software at the Computing Center. The Case faculty took the unprecedented step of awarding him a Master's degree together with the B.S. he received in 1960. After graduate studies at California Institute of Technology, he received a Ph.D. in Mathematics in 1963 and then remained on the mathematics faculty. Throughout this period he continued to be involved with software development, serving as consultant to Burroughs Corporation from 1960-1968 and as editor of Programming Languages for ACM publications from 1964-1967.

He joined Stanford University as Professor of Computer Science in 1968, and was appointed to Stanford's first endowed chair in computer science nine years later. As a university professor he introduced a variety of new courses into the curriculum, notably Data Structures and Concrete Mathematics. In 1993 he became Professor Emeritus of The Art of Computer Programming. He has supervised the dissertations of 28 students.

Knuth began in 1962 to prepare textbooks about programming techniques, and this work evolved into a projected seven-volume series entitled The Art of Computer Programming. Volumes 1-3 first appeared in 1968, 1969, and 1973. Having revised these three in 1997, he is now working full time on the remaining volumes. Approximately one million copies have already been printed, including translations into six languages. He took ten years off from this project to work on digital typography, developing the TeX system for document preparation and the METAFONT system for alphabet design. Noteworthy by-products of those activities were the WEB and CWEB languages for structured documentation, and the accompanying methodology of Literate Programming. TeX is now used to produce most of the world's scientific literature in physics and mathematics.

His research papers have been instrumental in establishing several subareas of computer science and software engineering: LR(k) parsing; attribute grammars; the Knuth-Bendix algorithm for axiomatic reasoning; empirical studies of user programs and profiles; analysis of algorithms. In general, his works have been directed towards the search for a proper balance between theory and practice.

Professor Knuth received the ACM Turing Award in 1974 and became a Fellow of the British Computer Society in 1980, an Honorary Member of the IEEE in 1982. He is a member of the American Academy of Arts and Sciences, the National Academy of Sciences, the National Academy of Engineering, and a foreign associate of l'Academie des Sciences (Paris) and Det Norske Videnskaps-Akademi (Oslo). He holds five patents and has published approximately 160 papers in addition to his 19 books. He received the Medal of Science from President Carter in 1979, the American Mathematical Society's Steele Prize for expository writing in 1986, the New York Academy of Sciences Award in 1987, the J.D. Warnier Prize for software methodology in 1989, the Adelsk&oumlld Medal from the Swedish Academy of Sciences in 1994, the Harvey Prize from the Technion in 1995, and the Kyoto Prize for advanced technology in 1996. He was a charter recipient of the IEEE Computer Pioneer Award in 1982, after having received the IEEE Computer Society's W. Wallace McDowell Award in 1980; he received the IEEE's John von Neumann Medal in 1995. He holds honorary doctorates from Oxford University, the University of Paris, St. Petersburg University, and more than a dozen colleges and universities in America.

Professor Knuth lives on the Stanford campus with his wife, Jill. They have two children, John and Jennifer. Music is his main avocation.

Forgot your password? FAQs Shipping Options Returns Your Orders Your Account