Programming Books C Java PHP Python Learn more Browse Programming Books
  • List Price: $19.99
  • Save: $5.30 (27%)
FREE Shipping on orders over $35.
Only 7 left in stock (more on the way).
Ships from and sold by
Gift-wrap available.
+ $3.99 shipping
Used: Good | Details
Sold by wmboothsbookssf
Condition: Used: Good
Comment: Used. Good book. Shows normal shelfware and clean pages. AA
Have one to sell? Sell on Amazon
Flip to back Flip to front
Listen Playing... Paused   You're listening to a sample of the Audible audio edition.
Learn more
See all 2 images

The Art of Computer Programming, Volume 4, Fascicle 3: Generating All Combinations and Partitions Paperback – August 5, 2005

See all formats and editions Hide other formats and editions
Amazon Price New from Used from
"Please retry"
$7.43 $3.65

Frequently Bought Together

The Art of Computer Programming, Volume 4,  Fascicle 3: Generating All Combinations and Partitions + The Art of Computer Programming, Volume 4, Fascicle 2: Generating All Tuples and Permutations + Art of Computer Programming, Volume 4, Fascicle 4: Generating All Trees--History of Combinatorial Generation
Price for all three: $48.09

Buy the selected items together

Shop the New Digital Design Bookstore
Check out the Digital Design Bookstore, a new hub for photographers, art directors, illustrators, web developers, and other creative individuals to find highly rated and highly relevant career resources. Shop books on web development and graphic design, or check out blog posts by authors and thought-leaders in the design industry. Shop now

Product Details

  • Paperback: 160 pages
  • Publisher: Addison-Wesley Professional; 1 edition (August 5, 2005)
  • Language: English
  • ISBN-10: 0201853949
  • ISBN-13: 978-0201853940
  • Product Dimensions: 6.4 x 0.4 x 9.5 inches
  • Shipping Weight: 11.2 ounces (View shipping rates and policies)
  • Average Customer Review: 4.8 out of 5 stars  See all reviews (4 customer reviews)
  • Amazon Best Sellers Rank: #1,602,445 in Books (See Top 100 in Books)

Editorial Reviews

About the Author

Donald E. Knuth is known throughout the world for his pioneering work on algorithms and programming techniques, for his invention of the Tex and Metafont systems for computer typesetting, and for his prolific and influential writing. Professor Emeritus of The Art of Computer Programming at Stanford University, he currently devotes full time to the completion of these fascicles and the seven volumes to which they belong.

Excerpt. © Reprinted by permission. All rights reserved.

In my preface to the first edition, I begged the reader not to draw attention to errors. I now wish I had not done so and am grateful to the few readers who ignored my request.

--Stuart Sutherland, The International Dictionary of Psychology (1996)

This booklet is Fascicle 3 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.

To put the material in context, this fascicle contains Sections,, and 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. Details about various useful ways to generate n-tuples appear in Section, and the generation of permutations is discussed in Section That sets the stage for the main contents of the present booklet, namely Section (which extends the ideas to combinations of n things taken t at a time); Section (about partitions of an integer); and Section (about partitions of a set). Then will come Section (about trees) and Section (about the history of combinatorial generation), in 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.

For example, in the present booklet we find many of the beautiful patterns formed by combinations, with and without repetition, and how they relate to famous theorems of extremal combinatorics. Then comes my chance to tell the extraordinary story of partitions; indeed, the theory of partitions is one of the nicest chapters in all of mathematics. And in Section, a little known triangle of numbers, discovered by C. S. Peirce, turns out to simplify and unify the study of set partitions, another vital topic. Along the way I've included expositions of two mathematical techniques of great importance in the analysis of algorithms: Poisson's summation formula, and the powerful saddle point method. There are games and puzzles too, as in the previous fascicles.

My original intention was to devote far less space to these subjects. 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.

I thank Frank Ruskey for bravely foisting an early draft of this material on college students and for telling me about his classroom experiences. Many other readers have also helped me to check the first drafts; I wish to thank especially George Clements and Svante Janson for their penetrating comments.

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¢ 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.)

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 described in Volume 1, Fascicle 1.

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

June 2005


More 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. Volume 4A appeared at the beginning of 2011. More than one million copies have already been printed, including translations into ten languages.

He took ten years off from that 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, and the National Academy of Engineering; he is also a foreign associate of l'Academie des Sciences (Paris), Det Norske Videnskaps-Akademi (Oslo), Bayerische Akademie der Wissenschaften (Munich), the Royal Society (London), and Rossiiskaya Akademia Nauk (Moscow). He holds five patents and has published approximately 160 papers in addition to his 28 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øld 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.

Customer Reviews

4.8 out of 5 stars
5 star
4 star
3 star
2 star
1 star
See all 4 customer reviews
Share your thoughts with other customers

Most Helpful Customer Reviews

5 of 6 people found the following review helpful By wiredweird HALL OF FAMETOP 500 REVIEWER on September 7, 2007
Format: Paperback
First, the brevity. This book nominally contains 160 pages - take off a few for indicia and intro, and it's down to 150. Of those, page 87 and up are all "answers to exercises" - not really part of the exposition. Then, within those 86 pages, about 30 are exercises. Although helpful to the involved reader, they aren't direct exposition either.

The 50 or 60 pages left are good, though. They present the combinatorial content in deep detail, even if breadth sometimes seems to suffer. Proofs and analyses are thorough, but become lengthy and require fair bits of calculus. These discussions range across the width of contemporary math and the length of its last few generations of history.

That leaves the algorithms - a few good ones, but only a few. If you came to this as a cut-and-paster, you won't find much to take home. On the whole, it's a worthy addition to "The Art" and to the collection that makes up Volume 4. For many, however, it won't be the hardest-working reference on the shelf.

-- wiredweird
Comment Was this review helpful to you? Yes No Sending feedback...
Thank you for your feedback. If this review is inappropriate, please let us know.
Sorry, we failed to record your vote. Please try again
8 of 12 people found the following review helpful By W Boudville HALL OF FAMETOP 1000 REVIEWERVINE VOICE on October 27, 2005
Format: Paperback
Only an author as smart and well known in his field as Donald Knuth would have tried this unusual format, which he terms a fascicle. In this third little book, he gives another extensive preview of his eventual fourth volume of "The Art of Computer Programming". When it finally appears, this volume is expected to span several books. In the interim, you will have to be content with these fascicles.

Even though this book is so slender, it is chock-a-block with tidbits, in the style of the first three volumes. Thus you can find out about a binomial tree, or even an infinite binomial tree. Or see how the Gray binary code also arises in the context of combinations.

An elegant aspect of this book is how Knuth ties in the discrete math of combinations with calculus applications. Quite often, these are two different worlds of maths, with different practitioners. Knuth uses the example of the varied properties of Bell numbers. Specifically, the rate at which these grow can be estimated by complex residues and saddle point analysis. Surprising results!
Comment Was this review helpful to you? Yes No Sending feedback...
Thank you for your feedback. If this review is inappropriate, please let us know.
Sorry, we failed to record your vote. Please try again
Format: Paperback Verified Purchase
You might be wondering if the fascicle series is still worth getting, given the whole series has now been updated in a single text here: The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1.

The answer is: it depends on whether you have a specific area of combinatorics you're interested in (example: Fascicle 0 is great for logic gates and hence circuit designers), or if you're interested in the entire area of combinatorics and all 5 fascicles (0-4).

All 5 are essentially covered in the 2011 book above, with some corrections and deletions. Don't be fooled by the "part 1" because this series can be confusing. Go to Dr. Knuth's website to see the entire map of current and planned volumes and editions, including this series in .pdf: just Google/Bing Knuth website art of programming and click on the dot cs dot faculty dot stanford link for the series.

As you'll see on the site, part 1 (if the Dr's health holds out) has now been expanded with additional draft fascicles, especially in the essentially uncovered area of stochastic combinatorics. Probability wasn't even applied to computational combinatorics yet in the 60's, so this is not a flaw in Doc Knuth's coverage! There is a 4B, 4C, 4D etc. planned, mostly expanding recursion, statistics and other new areas of combinatorics.

Great self study intro to everything computational complexity, as combinatorics greatly pushes the "big O" computing envelope, and the talented Doc Knuth even weighs in on P/NP. Many examples given with mem counts that are up to date.
Read more ›
Comment Was this review helpful to you? Yes No Sending feedback...
Thank you for your feedback. If this review is inappropriate, please let us know.
Sorry, we failed to record your vote. Please try again
By Roger Zhong on August 6, 2014
Format: Paperback Verified Purchase
these books are really my career collections
Comment Was this review helpful to you? Yes No Sending feedback...
Thank you for your feedback. If this review is inappropriate, please let us know.
Sorry, we failed to record your vote. Please try again