The Art of Computer Programming, Vol. 4A - pearsoncmg.com

1 THE ARTOFCOMPUTER PROGRAMMINGM issing pages from select printings of Knuth, The Art of Computer programming , Volume 4A (ISBN-13: 9780201038040 / ISBN-10: 0201038048). Copyright 2011 Pearson Education, Inc. All rights University677 ADDISON WESLEYM issing pages from select printings of Knuth, The Art of Computer programming , Volume 4A (ISBN-13: 9780201038040 / ISBN-10: 0201038048). Copyright 2011 Pearson Education, Inc. All rights /Combinatorial Algorithms, Part 1 THE ART OFCOMPUTER PROGRAMMINGB oston Columbus Indianapolis New York San FranciscoAmsterdam Cape Town Dubai London Madrid MilanMunich Paris Montr al Toronto Mexico City S o PauloDelhi Sydney Hong Kong Seoul Singapore Taipei TokyoMissing pages from select printings of Knuth, The Art of Computer programming , Volume 4A (ISBN-13: 9780201038040 / ISBN-10: 0201038048).

2 Copyright 2011 Pearson Education, Inc. All rights poem on page437 is quoted fromThe Golden Gateby Vikram Seth (New York:Random House, 1986), copyrightc 1986 by Vikram author and publisher have taken care in the preparation of this book, but make noexpressed or implied warranty of any kind and assume no responsibility for errors oromissions. No liability is assumed for incidental or consequential damages in connectionwith or arising out of the use of the information or programs contained publisher offers excellent discounts on this book when ordered in quantity for bulkpurposes or special sales, which may include electronic versions and/or custom coversand content particular to your business, training goals, marketing focus, and brandinginterests. For more information, please Corporate and Government Sales(800) 382 sales outside the , please contact:International us on the of Congress Cataloging-in-Publication DataKnuth, Donald Ervin, 1938-The art of Computer programming / Donald Ervin ,883 p.

3 24 bibliographical references and : v. 1. Fundamental algorithms. -- v. 2. Seminumericalalgorithms. -- v. 3. Sorting and searching. -- v. 4a. Combinatorialalgorithms, part : v. 4a. Combinatorial algorithms, part 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. Computeralgorithms. I. ~ information about this book and related ~ informationaboutThe Stanford GraphBase, including downloadable software for dealing withthe graphs used in many of the ~ basic infor-mation about version by Mathematical Sciences Publishers (MSP), 2011 by Pearson Education, rights reserved. Printed in the United States of America. This publication isprotected by copyright, and permission must be obtained from the publisher prior toany prohibited reproduction, storage in a retrieval system, or transmission in any formor by any means, electronic, mechanical, photocopying, recording, or likewise.

4 Forinformation regarding permissions, write to:Pearson Education, and Contracts Department501 Boylston Street, Suite 900 Boston, MA 02116 Fax: (617) 671-3447 ISBN-13 978-0-201-03804-0 ISBN-100-201-03804-8 Third digital release, March 2017 Missing pages from select printings of Knuth, The Art of Computer programming , Volume 4A (ISBN-13: 9780201038040 / ISBN-10: 0201038048). Copyright 2011 Pearson Education, Inc. All rights put all the good stuff into one book is patently impossible,and attempting even to be reasonably comprehensiveabout certain aspects of the subject is likely to lead to runaway growth. GERALD B. FOLLAND, Editor s Corner (2005)The titleof Volume 4 isCombinatorial Algorithms, and when I proposed itI was strongly inclined to add a subtitle:The Kind of programming I Like editors have decided to tone down such exuberance, but the fact remainsthat programs with a combinatorial flavor have always been my the other hand I ve often been surprised to find that, in many people sminds, the word combinatorial is linked with computational difficulty.

5 Indeed,Samuel Johnson, in his famous dictionary of the English language (1755), saidthat the corresponding noun is now generally used in an ill sense. Colleaguestell me tales of woe, in which they report that the combinatorics of the sit-uation defeated us. Why is it that, for me, combinatorics arouses feelings ofpure pleasure, yet for many others it evokes pure panic?It s true that combinatorial problems are often associated with humongouslylarge numbers. Johnson s dictionary entry also included a quote from EphraimChambers, 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,40 2,200. Thecorresponding number for a 10-letter alphabet is 11,111,111,110; and it s only3905 when the number of letters is 5.

6 Thus a combinatorial explosion certainlydoes occur as the size of the problem grows from 5 to 10 to 24 and machines have become tremendously more powerful throughoutmy life. As I write these words, I know that they are being processed by a lap-top whose speed is more than 100,000 times faster than the trusty IBM Type 650computer to which I ve dedicated these books; my current machine s memorycapacity is also more than 100,000 times greater. Tomorrow s computers will beeven faster and more capacious. But these amazing advances have not diminishedpeople s craving for answers to combinatorial questions; quite the contrary. Ouronce-unimaginable ability to compute so rapidly has raised our expectations,and whetted our appetite for more because, in fact, the size of a combinatorialproblem can increase more than 100,000-fold whennsimply increases by algorithms can be defined informally as techniques for thehigh-speed manipulation of combinatorial objects such as permutations or typically try to find patterns or arrangements that are the best possible waysto satisfy certain constraints.

7 The number of such problems is vast, and the artvMissing pages from select printings of Knuth, The Art of Computer programming , Volume 4A (ISBN-13: 9780201038040 / ISBN-10: 0201038048). Copyright 2011 Pearson Education, Inc. All rights writing such programs is especially important and appealing because a singlegood idea can save years or even centuries of Computer , the fact that good algorithms for combinatorial problems can have aterrific payoff has led to terrific advances in the state of the art. Many problemsthat once were thought to be intractable can now be polished off with ease, andmany algorithms that once were known to be good have now become about 1970, Computer scientists began to experience a phenomenonthat we called Floyd s Lemma : Problems that seemed to needn3operationscould actually be solved inO(n2); problems that seemed to requiren2could behandled inO(nlogn); andnlognwas often reducible toO(n).

8 More difficultproblems saw a reduction in running time fromO(2n) toO( ) toO( ),etc. Other problems remained difficult in general, but they were found to haveimportant special cases that are much simpler. Many combinatorial questionsthat I once thought would never be answered during my lifetime have now beenresolved, and those breakthroughs have been due mainly to improvements inalgorithms rather than to improvements in processor 1975, such research was advancing so rapidly that a substantial fractionof the papers published in leading journals of Computer science were devotedto combinatorial algorithms. And the advances weren t being made only bypeople in the core of Computer science; significant contributions were comingfrom workers in electrical engineering, artificial intelligence, operations research,mathematics, physics, statistics, and other fields.

9 I was trying to completeVolume 4 ofThe Art of Computer programming , but instead I felt like I wassitting on the lid of a boiling kettle: I was confronted with a combinatorialexplosion of another kind, a prodigious explosion of new ideas!This series of books was born at the beginning of 1962, when I na velywrote out a list of tentative chapter titles for a 12-chapter book. At that timeI decided to include a brief chapter about combinatorial algorithms, just forfun. Hey look, most people use computers to deal with numbers, but we canalso write programs that deal with patterns. In those days it was easy to givea fairly complete description of just about every combinatorial algorithm thatwas known. And even by 1966, when I d finished a first draft of about 3000handwritten pages for that already-overgrown book, fewer than 100 of thosepages belonged to Chapter 7.

10 I had absolutely no idea that what I d foreseen asa sort of salad course would eventually turn out to be the main great combinatorial fermentation of 1975 has continued to churn, asmore and more people have begun to participate. New ideas improve upon theolder ones, but rarely replace them or make them obsolete. So of course I vehad 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-stopshopping for everyone who has combinatorial problems to solve. The array ofapplicable techniques has mushroomed to the point where I can almost neverdiscuss a subtopic and say, Here s the final solution: end of story. Instead, Imust restrict myself to explaining the most important principles that seem tounderlie all of the efficient combinatorial methods that I ve encountered so pages from select printings of Knuth, The Art of Computer programming , Volume 4A (ISBN-13: 9780201038040 / ISBN-10: 0201038048).