About This eBook ePUB is an open, industry-standard format for eBooks. However, support of ePUB and its many features varies across reading devices and applications. Use your device or app settings to customize the presentation to your liking. Settings that you can customize often include font, font size, single or double column, landscape or portrait mode, and figures that you can click or tap to enlarge. For additional information about the settings and features on your reading device or app, visit the device manufacturer’s Web site. Many titles include programming code or configuration examples. To optimize the presentation of these elements, view the eBook in single-column, landscape mode and adjust the font size to the smallest setting. In addition to presenting code and configurations in the reflowable text format, we have included images of the code that mimic the presentation found in the print book; therefore, where the reflowable format may compromise the presentation of the code listing, you will see a “Click here to view code image” link. Click the link to view the print-fidelity code image. To return to the previous page viewed, click the Back button on your device or app. In this eBook, the limitations of the ePUB format have caused us to render some equations as text and others as images, depending on the complexity of the equation. This can result in an odd juxtaposition in cases where the same variables appear as part of both a text presentation and an image presentation. However, the author’s intent is clear and in both cases the equations are legible. THE ART OF COMPUTER PROGRAMMING Volume 4A / Combinatorial Algorithms, Part 1 DONALD E. KNUTH Stanford University ADDISON–WESLEY Upper Saddle River, NJ · Boston · Indianapolis · San Francisco New York · Toronto · Montréal · London · Munich · Paris · Madrid Capetown · Sydney · Tokyo · Singapore · Mexico City The poem on page 437 is quoted from The Golden Gate by Vikram Seth (New York: Random House, 1986), copyright © 1986 by Vikram Seth. The author and publisher have taken care in the preparation of this book, but make no expressed or implied warranty of any kind and assume no responsibility for errors or omissions. No liability is assumed for incidental or consequential damages in connection with or arising out of the use of the information or programs contained herein. The publisher offers excellent discounts on this book when ordered in quantity for bulk purposes or special sales, which may include electronic versions and/or custom covers and content particular to your business, training goals, marketing focus, and branding interests. For more information, please contact: U.S. Corporate and Government Sales (800) 382–3419 [email protected] For sales outside the U.S., please contact: International Sales [email protected] Visit us on the Web: informit.com/aw Library of Congress Cataloging-in-Publication Data Knuth, Donald Ervin, 1938- The art of computer programming / Donald Ervin Knuth. xvi,883 p. 24 cm. Includes bibliographical references and index. Contents: v. 1. Fundamental algorithms. -- v. 2. Seminumerical algorithms. -- v. 3. Sorting and searching. -- v. 4a. Combinatorial algorithms, part 1. Contents: v. 4a. Combinatorial algorithms, part 1. ISBN 978-0-201-89683-1 (v. 1, 3rd ed.) ISBN 978-0-201-89684-8 (v. 2, 3rd ed.) ISBN 978-0-201-89685-5 (v. 3, 2nd ed.) ISBN 978-0-201-03804-0 (v. 4a) 1. Electronic digital computers--Programming. 2. Computer algorithms. I. Title. QA76.6.K64 1997 005.1--DC21 97-2147 Internet page http://www-cs- faculty.stanford.edu/~knuth/taocp.html contains current information about this book and related books. See also http://www-cs-faculty.stanford.edu/~knuth/sgb.html for information about The Stanford GraphBase, including downloadable software for dealing with the graphs used in many of the examples. And see http://www-cs-faculty.stanford.edu/~knuth/mmix.html for basic information about the MMIX computer. Electronic version by Mathematical Sciences Publishers (MSP), http://msp.org Copyright © 2011 by Pearson Education, Inc. All rights reserved. Printed in the United States of America. This publication is protected by copyright, and permission must be obtained from the publisher prior to any prohibited reproduction, storage in a retrieval system, or transmission in any form or by any means, electronic, mechanical, photocopying, recording, or likewise. For information regarding permissions, write to: Pearson Education, Inc. Rights and Contracts Department 501 Boylston Street, Suite 900 Boston, MA 02116 Fax: (617) 671-3447 ISBN-13 978-0-201-03804-0 ISBN-10 0-201-03804-8 First digital release, August 2014 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, “Editor’s 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 I’ve often been surprised to find that, in many people’s 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? It’s true that combinatorial problems are often associated with humongously large numbers. Johnson’s 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 for a 10-letter alphabet is 11,111,111,110; and it’s only 3905 when the number of letters is 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 I’ve dedicated these books; my current machine’s memory capacity is also more than 100,000 times greater. Tomorrow’s computers will be even faster and more capacious. But these amazing advances have not diminished people’s 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 “Floyd’s Lemma”: Problems that seemed to need n3 operations could actually be solved in O(n2); problems that seemed to require n2 could be handled in O(n log n); and n log n was often reducible to O(n). More difficult problems saw a reduction in running time from O(2n) to O(1.5n) to O(1.3n), etc. Other problems remained difficult in general, but they were found to have important special cases that are much simpler. Many combinatorial questions that I once thought would never be answered during my lifetime have now been resolved, and those breakthroughs have been due mainly to improvements in algorithms rather than to improvements in processor speeds. By 1975, such research was advancing so rapidly that a substantial fraction of the papers published in leading journals of computer science were devoted to combinatorial algorithms. And the advances weren’t being made only by people in the core of computer science; significant contributions were coming from workers in electrical engineering, artificial intelligence, operations research, mathematics, physics, statistics, and other fields. I was trying to complete Volume 4 of The Art of Computer Programming, but instead I felt like I was sitting on the lid of a boiling kettle: I was confronted with a combinatorial explosion of another kind, a prodigious explosion of new ideas! This series of books was born at the beginning of 1962, when I naïvely wrote out a list of tentative chapter titles for a 12-chapter book. At that time I decided to include a brief chapter about combinatorial algorithms, just for fun. “Hey look, most people use computers to deal with numbers, but we can also write programs that deal with patterns.” In those days it was easy to give a fairly complete description of just about every combinatorial algorithm that was known. And even by 1966, when I’d finished a first draft of about 3000 handwritten pages for that already-overgrown book, fewer than 100 of those pages belonged to Chapter 7. I had absolutely no idea that what I’d foreseen as a sort of “salad course” would eventually turn out to be the main dish. The great combinatorial fermentation of 1975 has continued to churn, as more and more people have begun to participate. New ideas improve upon the older ones, but rarely replace them or make them obsolete. So of course I’ve had to abandon any hopes that I once had of being able to surround the field, to write a definitive book that sets everything in order and provides one-stop shopping for everyone who has combinatorial problems to solve. The array of applicable techniques has mushroomed to the point where I can almost never discuss a subtopic and say, “Here’s the final solution: end of story.” Instead, I must restrict myself to explaining the most important principles that seem to underlie all of the efficient combinatorial methods that I’ve encountered so far. At present I’ve accumulated more than twice as much raw material for Volume 4 as for all of Volumes 1–3 combined. This sheer mass of material implies that the once-planned “Volume 4” must actually become several physical volumes. You are now looking at Volume 4A. Volumes 4B and 4C will exist someday, assuming that I’m able to remain healthy; and (who knows?) there may also be Volumes 4D, 4E, . . .; but surely not 4Z. My plan is to go systematically through the files that I’ve amassed since 1962 and to tell the stories that I believe are still waiting to be told, to the best of my ability. I can’t aspire to completeness, but I do want to give proper credit to all of the pioneers who have been responsible for key ideas; so I won’t scrimp on historical details. Furthermore, whenever I learn something that I think is likely to remain important 50 years from now, something that can also be explained elegantly in a paragraph or two, I can’t bear to leave it out. Conversely, difficult material that requires a lengthy proof is beyond the scope of these books, unless the subject matter is truly fundamental. OK, it’s clear that the field of Combinatorial Algorithms is vast, and I can’t cover it all. What are the most important things that I’m leaving out? My biggest blind spot, I think, is geometry, because I’ve always been much better at visualizing and manipulating algebraic formulas than objects in space. Therefore I don’t attempt to deal in these books with combinatorial problems that are related to computational geometry, such as close packing of spheres, or clustering of data points in n-dimensional Euclidean space, or even the Steiner tree problem in the plane. More significantly, I tend to shy away from polyhedral combinatorics, and from approaches that are based primarily on linear programming, integer programming, or semidefinite programming. Those topics are treated well in many other books on the subject, and they rely on geometrical intuition. Purely combinatorial developments are easier for me to understand. I also must confess a bias against algorithms that are efficient only in an asymptotic sense, algorithms whose superior performance doesn’t begin to “kick in” until the size of the problem exceeds the size of the universe. A great many publications nowadays are devoted to algorithms of that kind. I can understand why the contemplation of ultimate limits has intellectual appeal and carries an academic cachet; but in The Art of Computer Programming I tend to give short shrift to any methods that I would never consider using myself in an actual program. (There are, of course, exceptions to this rule, especially with respect to basic concepts in the core of the subject. Some impractical methods are simply too beautiful and/or too insightful to be excluded; others provide instructive examples of what not to do.) Furthermore, as in earlier volumes of this series, I’m intentionally concentrating almost entirely on sequential algorithms, even though computers are increasingly able to carry out activities in parallel. I’m unable to judge what ideas about parallelism are likely to be useful five or ten years from now, let alone fifty, so I happily leave such questions to others who are wiser than I. Sequential methods, by themselves, already test the limits of my own ability to discern what the artful programmers of tomorrow will want to know. The main decision that I needed to make when planning how to present this material was whether to organize it by problems or by techniques. Chapter 5 in Volume 3, for example, was devoted to a single problem, the sorting of data into order; more than two dozen techniques were applied to different aspects of that problem. Combinatorial algorithms, by contrast, involve many different problems, which tend to be attacked with a smaller repertoire of techniques. I finally decided that a mixed strategy would work better than any pure approach. Thus, for example, these books treat the problem of finding shortest paths in Section 7.3, and problems of connectivity in Section 7.4.1; but many other sections are devoted to basic techniques, such as the use of Boolean algebra (Section 7.1), backtracking (Section 7.2.2), matroid theory (Section 7.6), or dynamic programming (Section 7.7). The famous Traveling Salesrep Problem, and other classic combinatorial tasks related to covering, coloring, and packing, have no sections of their own, but they come up several times in different places as they are treated by different methods. I’ve mentioned great progress in the art of combinatorial computing, but I don’t mean to imply that all combinatorial problems have actually been tamed. When the running time of a computer program goes ballistic, its programmers shouldn’t expect to find a silver bullet for their needs in this book. The methods described here will often work a great deal faster than the first approaches that a programmer tries; but let’s face it: Combinatorial problems get huge very quickly. We can even prove rigorously that a certain small, natural problem will never have a feasible solution in the real world, although it is solvable in principle (see the theorem of Stockmeyer and Meyer in Section 7.1.2). In other cases we cannot prove as yet that no decent algorithm for a given problem exists, but we know that such methods are unlikely, because any efficient algorithm would yield a good way to solve thousands of other problems that have stumped the world’s greatest experts (see the discussion of NP-completeness in Section 7.9). Experience suggests that new combinatorial algorithms will continue to be invented, for new combinatorial problems and for newly identified variations or special cases of old ones; and that people’s appetite for such algorithms will also continue to grow. The art of computer programming continually reaches new heights when programmers are faced with challenges such as these. Yet today’s methods are also likely to remain relevant. Most of this book is self-contained, although there are frequent tie-ins with the topics discussed in Volumes 1–3. Low-level details of machine language programming have been covered extensively in those volumes, so the algorithms in the present book are usually specified only at an abstract level, independent of any machine. However, some aspects of combinatorial programming are heavily dependent on low-level details that didn’t arise before; in such cases, all examples in this book are based on the MMIX computer, which supersedes the MIX machine that was defined in early editions of Volume 1. Details about MMIX appear in a paperback supplement to that volume called The Art of Computer Programming, Volume 1, Fascicle 1, containing Sections 1.3.1´, 1.3.2´, etc.; they’re also available on the Internet, together with downloadable assemblers and simulators. Another downloadable resource, a collection of programs and data called The Stanford GraphBase, is cited extensively in the examples of this book. Readers are encouraged to play with it, in order to learn about combinatorial algorithms in what I think will be the most efficient and most enjoyable way.