% CHANGES TO FASCICLE V4F2 OF THE ART OF COMPUTER PROGRAMMING % % Copyright (C) 2005,2006,2007,2008 by Donald E. Knuth % This file may be freely copied provided that no modifications are made. % All other rights are reserved. % % Three levels of changes to the books are distinguished here: % % "\bugonpage" introduces the correction of an error; % "\amendpage" introduces new material for future editions; % "\improvepage" introduces ameliorations of lesser importance. % % (Changes introduced by \improvepage do not appear in the hardcopy listing.) % % Also, "\planforpage" introduces some of the author's half-baked intentions. % % NOTE: TO PUT THE INDEX ON A SEPARATE PAGE, RUN THIS WITH THE COMMAND LINE % tex "\let\indexeject+ \input err4f2" \newif\ifall % \alltrue means show the trivial items too \relax % hook \def\vertical{|} \def\inref#1 #{\expandafter\def\csname\vertical#1\endcsname} \catcode`|=\active \let|\inref \input \jobname.ref \catcode`|=12 \input taocpmac % use the format for TAOCP, with modifications below \def\becomes{\ifmmode\ \hbox\fi{\manfnt y}\ } % wiggly arrow indicates a change \def\bugonpage#1.#2 #3 (#4) { \medbreak\defaultpointsize \line{\kern-5pt\llap{\manfnt x}% print a black triangle in left margin {\bf Page #2}\enspace #3 \leaders\hrule\hfill\ \eightrm\date#4.} \nobreak\smallskip\iftrue\noindent} \def\amendpage#1.#2 #3 (#4) { \medbreak\defaultpointsize \line{\kern-5pt{\bf Page #2}\enspace #3 \leaders\hrule\hfill\ \eightrm\date#4.} \nobreak\smallskip\iftrue\noindent} \def\improvepage#1.#2 #3 (#4) {\ifall \medbreak\ninepoint \line{\kern-6pt{\sl Page #2\enspace #3\/} \leaders\hrule\hfill\ \eightrm\date#4.} \nobreak\smallskip\noindent} \def\planforpage#1.#2 #3 (#4) { \medbreak\defaultpointsize \line{\kern-5pt{\bf Page #2}\enspace #3 \leaders\hbox to 5pt{\hss.\hss}\hfill\ \eightrm\date#4.} \nobreak\smallskip\begingroup\let\endchange=\endgroup\sl\noindent} \let\endchange=\fi \def\nl{\par\noindent} \def\nlh{\par\noindent\hangit} \def\hangit{\hangindent2em} \def\cutpar{{\parfillskip=0pt\par}} \def\date#1.#2.#3.{% convert "yy.mm.dd." to "dd Mon 19yy" #3 \ifcase#2\or Jan\or Feb\or Mar\or Apr\or May\or Jun\or Jul\or Aug\or Sep\or Oct\or Nov\or Dec\fi \ \ifnum #1<97 \hundred#1\else19#1\fi} \def\hundred{20} % the "century" for dates before '97 \def\ex #1. [#2]{\ninepoint \textindent{\bf#1.}[{\it#2\/}]\kern6pt} \def\EX #1. [#2]{\ninepoint \textindent{\llap{\manfnt x}\bf#1.}[{\it#2\/}]\kern6pt} \def\foottext#1{\medskip \hrule height\ruleht width5pc \kern-\ruleht \kern3pt \eightpoint \smallskip\textindent{#1}} \def\volheadline#1{\line{\hss\cleaders\hbox{\raise3pt\hbox{\manfnt\char'36}}\hfill \titlefont\ #1\ \cleaders\hbox{\raise3pt\hbox{\manfnt\char'36}}\hfill\hss}} \def\refin#1 {\let|\inref \input #1.ref \let|\crossref} \let\defaultpointsize=\tenpoint %%%%%%%%%%%%%% opening remarks %%%%%%%%%%%%%%%%%%%%%%%% \def\lhead{INTRODUCTION} \let\rhead=\lhead \titlepage \volheadline{THE ART OF COMPUTER PROGRAMMING} \bigskip \volheadline{ERRATA TO VOLUME 4 FASCICLE 2} \bigskip \noindent This document is a transcript of the notes that I have been making in my personal copy of {\sl The Art of Computer Programming}, Volume~4, Fascicle~2, since it was first printed in 2005. \ifall Four levels of updates\dash---``errors,'' ``amendments,'' ``plans,'' and ``improvements''\dash---appear, indicated by four \else Three levels of updates\dash---``errors,'' ``amendments,'' and ``plans''\dash---appear, indicated by three \fi different typographic conventions: \begingroup\def\hundred{17} \bugonpage 0.666 line 1 (76.07.04) Technical or typographical errors (aka bugs) are the most critical items, so they are flagged with a `\thinspace{\manfnt x}\thinspace' preceding the page number. The date on which I first was told about the bug is shown; this is the effective date on which I paid the finder's fee. The necessary corrections are indicated in a straightforward way. If,~for example, the book says `$n$' where it should have said `$n+1$', the change is shown thus: \smallskip $n$ \becomes $n+1$ \endchange \amendpage 0.666 line 2 (89.07.14) Amendments to the text appear in the same format as bugs, but without the~`\thinspace{\manfnt x}\thinspace'. These are things I wish I had known about or thought of when I wrote the original text, so I added them later. The date is the date I drafted the new text. \endchange \def\hundred{19} \planforpage 0.666 line 3 (17.11.20) Plans for the future represent a third kind of item. In such notes I~sketched my intentions about things that I wasn't ready to flesh out further when I~wrote them down. You can identify these items because they're written in slanted type, and preceded by a bunch of dots `\hbox to 6em{\leaders\hbox to 5pt{\hss.\hss}\hfill}' leading to the date on which I recorded the plan in my files. \endchange \improvepage 0.666 line 4 (38.01.10) The fourth and final category\dash---indicated by page and line number in smaller, slanted type\dash---consists of minor corrections or improvements that most readers don't want to know about, because they are so trivial. You wouldn't even be seeing these items if you hadn't specifically chosen to print the complete errata list in all its gory details. Are you sure you wanted to do that? \endchange \endgroup \ifall\else\medskip\ninepoint My personal file of updates also includes a fourth category of items, not shown in this list. They are miscellaneous minor corrections or improvements that most readers don't want to know about, because they are so trivial. If you really want to see all of the gory details, you can download the full list from Internet webpage $$\.{http://www-cs-faculty.stanford.edu/\char`\~knuth/taocp.html}$$ by selecting the ``long form'' of the errata. \fi \medskip \tenpoint \beginconstruction The ultimate, glorious, future editions of Volumes 1--5 are works in progress. Please let me know of any improvements that you think I ought to make. Send your comments either by snail mail to D.~E. Knuth, Computer Science, Gates Building 4B, Stanford University, Stanford CA~94305-9045, or by email to {\tt taocp{\char`\@}cs.stanford.edu}. (Use email for book suggestions only, please\dash---all other correspondence is returned unread to the sender, or discarded, because I have no time to read ordinary email.) Although I'm working full time on Volume~4 these days, I~will try to reply to all such messages within a year of receipt. Current news about {\sl The Art of Computer Programming\/} is posted on $$\.{http://www-cs-faculty.stanford.edu/\char`~knuth/taocp.html}$$ and updated regularly. \par\endconstruction \rightline{\dash---Don Knuth, February 2005} \bigskip \bigskip {\quoteformat For a work of such scope as this, the first word of the author should be an apology for what is doubtless the too ambitious effort of a single writer. \author EDWARD W. BYRN (1900) % The Progress of Invention in the Nineteenth Century, page i \vfill\eject } \def\today{\number\day\space\ifcase\month\or January\or February\or March\or April\or May\or June\or July\or August\or September\or October\or November\or December\fi \space\number\year} %%%%%%%%%%%%%%% CHANGES FOR VOLUME 4 FASCICLE 2 %%%%%%%%%%%%%%%%%%%%%%%%%%% \def\lhead{CHANGES TO V4F2: GENERATING ALL TUPLES AND PERMUTATIONS} \let\rhead=\lhead \titlepage \volheadline{GENERATING ALL TUPLES AND PERMUTATIONS} \bigskip \rightline{Copyright \copyright\ 2005, 2006, 2007, 2008, Addison\with Wesley; all rights reserved} \rightline{Last updated \today} \bigskip \rightline{\sl Most of these corrections have already been made in recent printings.} \smallskip \let\defaultpointsize=\tenpoint \amendpage 4f2.iii line 12 (05.09.15) There will also be a Fascicle 1 for Volume 4. \becomes There will also be a Fascicle 1 for Volume 4, and even a Fascicle~0. \endchange \improvepage 4f2.iv line $-13$ (05.12.04) indices \becomes indexes \endchange \amendpage 4f2.0 replacement for lines 3 and 4 (07.06.13) \beginconstruction The opening sections of this chapter will appear in Volume~4, Fascicle~0, and Volume~4, Fascicle~1, planned for publication in 2007 and 2008.\par\endgroup \endchange \bugonpage 4f2.2 in the running headline {(also on pages 4, 6, 8, \dots!)} (08.01.29) \eightpoint SEARCHING \becomes SEARCHING (F2) \endchange \bugonpage 4f2.3 {(and throughout the fascicle!)} (08.04.04) \ninepoint{\bf Fig.\ 10} \becomes {\bf Fig.\ 30} [and all figure numbers need to increased by 20] \endchange \amendpage 4f2.4 line 16 (06.10.18) 7.1--00 \becomes 7.1.3--117 \endchange \amendpage 4f2.6 line 4 (06.10.18) 7.1--\eq(00) \becomes 7.1.3--\eq(44) \endchange \amendpage 4f2.9 line $-7$ (06.10.18) Section 7.1 \becomes Section 7.1.3 \endchange \amendpage 4f2.11 in step W1 (06.10.18) line 2: $\bigl((z-m)\oplus z\oplus m\bigr)\land m'\ne0$ \becomes $\bigl((z-m)\oplus z\oplus m\bigr)\band m'\ne0$\nl line 4: 7.1--\eq(00); it \becomes 7.1.3--\eq(90). It \endchange \amendpage 4f2.11 lines 1--2 of step W2 (05.05.19) $m_0\gets z\land(2^5-1)$, \dots\ $m_4\gets z\land(2^{25}-2^{20})$ \becomes $m_0\gets z\band(2^5-1)$, $m_1\gets z\band(2^{10}-2^5)$, $m_2\gets z\band(2^{15}-2^{10})$, $m_3\gets z\band(2^{20}-2^{15})$, and $m_4\gets z\band(2^{25}-2^{20})$ \endchange \improvepage 4f2.12 replacement for {\eq(23)} (05.04.23) $$\def\,{\kern1pt}\vcenter{\halign{{\tt#}\,,&&\quad{\tt#}\,,\cr ducks&ducky&duces&dunes&dunks&dinks&dinky\cr dines&dices&dicey&dicky&dicks&picks&picky\cr pines&piney&pinky&pinks&punks&punky&\omit\quad{\tt pucks}\,.\cr}}\eqno(23)$$ \endchange \bugonpage 4f2.20 bottom line (05.04.17) $j$th forest \becomes $j$th tree \endchange \amendpage 4f2.30 line 1 (07.07.05) \ninepoint [{\it21\/}] \becomes [{\it23\/}] \endchange \improvepage 4f2.30 line 3 (07.07.05) \ninepoint summed over \becomes a polynomial in the variables $z_0$, $z_1$, $z_2$, and $z_3$, summed over \endchange \amendpage 4f2.32 line 2 of exercise 40 (05.05.19) \ninepoint $m_j=x\land(2\raise.7ex\hbox{$\scriptstyle5j$}-1)$ \becomes $m_j=x\band(2\raise.7ex\hbox{$\scriptstyle5j$}-1)$ \endchange \amendpage 4f2.33 new rating for exercise 55 (07.08.28) \ninepoint[{\it47\/}] \becomes [{\it35\/}] \endchange \amendpage 4f2.36 in exercise 85 (07.02.02) $\sqtimes$ \becomes $\boust$ (this notational change also affects answers 85--87). \endchange \amendpage 4f2.37 replacement for lines 1--4 of exercise 96 (05.06.17) \ninepoint \EX 96. [M28] Suppose a family of coroutines has been set up to generate a de~Bruijn cycle of length $m^n$ using Algorithms R and~D, based recursively on simple coroutines like Algorithm~S for the base case $n=2$. \item{a)} How many coroutines $(R_n, D_n, S_n)$ of each type will there be? \endchange \improvepage 4f2.39 and 40 formatting change (05.06.11) [I'm moving the quotations from page 39 to page 40, for better page breaks. This change affects several entries in the index.] \endchange \improvepage 4f2.42 bottom line (07.08.26) {\eightss DUCKWORTH and STEDMAN} \becomes {\eightss R. DUCKWORTH and F. STEDMAN} \endchange \improvepage 4f2.43 line $-21$ (05.09.17) musical or mathematical \becomes musical \endchange \improvepage 4f2.44 replacement for lines 3--7 (07.10.16) \algindentset{T1}% \algstep T3. [Hunt down.] Set $k\gets k+d$ and $j\gets m-1$. Then while $j>0$, set $t[k]\gets j$, $k\gets k+d$, and $j\gets j-1$. \algstep T4. [Offset.] Set $t[k]\gets t[k]+1$. \algstep T5. [Hunt up.] Set $k\gets k+d$, $j\gets 1$. While $jk$ \becomes $j2\lceil2^{n+1}\!/(n+2)\rceil \ge c'_k$ for $0\le jn_l']$ \endchange \bugonpage 4f2.102 replacement for line 2 of answer 7 (05.02.03) $${n_1+\cdots+n_t\over n}+{(n_1n_2+n_1n_3+\cdots+n_{t-1}n_t)+ n_1(n_1{-}1)+\cdots+n_t(n_t{-}1)\over n(n-1)}+\cdots{}\,.$$ \endchange \amendpage 4f2.102 insert a new sentence at the beginning of answer 9 (06.04.06) Assume that $r>0$ and that we begin with $a_01$. \endchange \bugonpage 4f2.116 line 8 (06.02.26) $\displaystyle \sum_{j+1}^{r-1}$ \becomes $\displaystyle \sum_{j=1}^{r-1}$ \endchange \bugonpage 4f2.116 line 9 (06.12.02) $F_{r+1}-2F_j+(-1)^{@j}F_{r+1-j}$ \becomes $F_{r+1}-2F_j-(-1)^{@j}F_{r+1-j}$ \endchange \amendpage 4f2.117 lines 3--5 of answer 100 (05.02.12) It appears likely \dots~for \becomes A.~D. King [{\sl Discrete Math.\ \bf306} (2006), 508--516] has shown that indecomposable permutations can be generated efficiently by making only a single transposition at each step. In fact, {\it adjacent\/} transpositions may well suffice; for example, when $n=4$ the indecomposable permutations are \endchange \bugonpage 4f2.118 line 4 of answer 105 (06.03.29) ments; \becomes ments''; \endchange \bugonpage 4f2.119 line 10 of answer 108 (07.03.21) 239--241 \becomes 739--741 \endchange \bugonpage 4f2.120 line 5 of answer 111 (06.03.29) Theorem 2.3.4.2D \becomes Theorem 2.3.4.2G \endchange \bugonpage 4f2.120 line $-2$ of answer 111 (06.04.21) Eulerian trials \becomes Eulerian trails \endchange \amendpage 4f2.120 new answer 112 (08.02.03) \begingroup \advance\parindent by 4pt % for them BIG exercise numbers \ans112. (a) If the cycle is $a_1a_2\ldots{}@$, use $\sigma$ at step~$j$ if the subsequence $a_ja_{j+1}\ldots a_{j+n-1}$ is a permutation; otherwise use $\rho$.\par (b) This statement follows immediately from exercise 72.\par (c) Let $\Omegait_2=\sigma^2$, and obtain $\Omegait_{n+1}$ from $\Omegait_n$ by substituting $\sigma\mapsto\sigma^2\!\rho^{n-1}$ and $\rho\mapsto\sigma^2\!\rho^{n-2}\sigma$. For example, $\Omegait_3=(\sigma^2\!\rho)^2$ and $\Omegait_4=\bigl((\sigma^2\!\rho^2)^2\sigma^2\!\rho\sigma\bigr){}^2$. Generate permutations by starting with $n\ldots21$ and applying the successive elements of~$\Omegait_n$; for example, the sequence when $n=4$ is $$\displaylines{ 4321,3214,2143,1423,4213,2134,1342,3412,4132,1324,3241,2431,\cr 4312,3124,1243,2413,4123,1234,2341,3421,4231,2314,3142,1432,\cr}$$ and the corresponding universal cycle is (432142134132431241234231). Notice that $n$ moves cyclically in this sequence of permutations; and the permutations that begin with~$n$ correspond to the sequence obtained from~$\Omegait_{n-1}$.\par [Universal cycles can also be constructed explicitly for permutations of a~{\it multiset}, analogous to 7.2.1.1--\eq(69); see F.~Ruskey and A.~Williams, to appear.] \endgroup \endchange \amendpage 4f2.120 and 121, changes to old answer 112 (08.02.03) [This answer is now the answer to exercise 113. In the second and third paragraphs, change `Notice first \dots~Now consider' \becomes `Consider'. Also delete the final paragraph.] \endchange \expandafter\ifx\csname indexeject\endcsname\relax\else\vfill\eject\fi \amendpage 4f2.122 and following (05.02.07) Miscellaneous changes to the existing index of Volume~4 Fascicle~2 are collected here, including corrections and amendments to the old entries as well as new entries that are occasioned by the new material. Thus, the lines of the full index that have changed serve also as an index to the present document. However, when a correction or amendment has caused an old index entry to be deleted, the deletion is usually not indicated. \input exotic \begindoublecolumns \indexformat \gdef\Uni1.08:{\bitmap24:1.08:} \hangindent2em \'Ad\'am, Andr\'as, 85. % 2nd Bakos, Tibor, 85. % 2nd Buckley, Michael Robert Warren, 66. % 2nd Cayley graphs, 58, 69--72, 75, 111. % 2nd Castown, Rudolph William, 11. % 2nd Codewords, 30. % 2nd Complete graph, 85. % 2nd Conway, John Horton, 74, 83. % 2nd Coroutines, 70--71. % 2nd \sub recursive, 24--25, 36--37. % 2nd Cyclic shifts, 26, 56, 58, 61, 68. % 2nd de Bruijn cycles, 22--27, 36--38, 74, 99, 121. % 2nd Dijkstra, Edsger Wybe, 42. % 2nd Direct product of matrices, 82. % 2nd Fibonacci, Leonardo, of Pisa (= Leonardo filio Bonacii Pisano), numbers, 36, 74, 116. % 2nd Fink, Ji\v{r}{\'\i}, 85. % 2nd Five-letter English words, 11, 32--33, 38, 66. % 2nd Gray code for $n$-tuples,\indexnoperiod \sub nonbinary, 18--20, 35--36, 80, 82, 88, 90--92. % 2nd Hamilton cycle, 13, 34, 41, 58--59, 69--72, 75, 85, 111. % 2nd Hamilton path, 15, 33, 41, 58--59, 70--71, 75, 85, 110--111. % 2nd Inversion tables, 41, 72, 101, 116. % 2nd Iv\'anyi, Antal Mikl\'os, 99. % 2nd Jackson, Bradley Warren, 74. % 2nd King, Andrew Douglas, 117. % 2nd \MMIX\ computer, ii, iv, 59--61, 72, 76. % 2nd Multisets, permutations of, 39--41, 62, 65, 71, 120. % 2nd $n$-cube, symmetries of, 66. % 2nd N\=ar\=aya\d{n}a Pa\d{n}\d{d}ita, \vadjust{\vskip1pt}son of N\d{r}si\:mha\indexbreak({\dn nArAyZ pE\char23Xt}, {\dn n\llap{\lower.12em\hbox{\char2}\kern.4em}Es\llap{\char92\kern-.05em}h-y p\llap{\lower.15em\hbox{\char0}\kern.3em}/,}), 39, 101. % 2nd Notational conventions:\indexnoperiod % 2nd \sub $\Gamma^R$ (reversal), 3. % 2nd \sub $\Gamma\boust\Gamma'$ (boustrophedon product), 36. % 2nd Organ-pipe order, 111, 118. % 2nd Permutations of a multiset, 39--41, 62, 65, 71, 120. % 2nd Poll\'ak, Gy\"orgy, 85. % 2nd Preferential arrangements, \see Weak orderings. % 2nd Recurrences, 23, 79, 81, 90, 95--96, 101. % 2nd Reflected Gray codes, 19--21, 35, 80, 90, 92. % 2nd Ruskey, Frank, iv, 20, 21, 28, 31, 33, 59, 72, 94, 98, 111, 112, 115, 116, 120. % 2nd \'S\=ar\:ngadeva, son of So\d{d}haladeva ({\dn fA\kern-.1em\char'263\kern-.25em\char'15\kern.05em\llap{\raise.35em\hbox{\char'24}}\kern-.09emd\kern-.1em\llap{\char3}v}, {\dn soYld\kern-.02em\llap{\char3}v p\llap{\lower.15em\hbox{\char0}\kern.3em}/,}), 101. % 2nd Smith, Derek Alan, 83. % 2nd Suparta, I Nengah, 80. % 2nd Universal cycles of permutations, 74--75. % 2nd van Zanten, Arend Jan, 80. % 2nd Weak orderings, 74, 118. % 2nd Williams, Aaron Michael, 75, 120. % 2nd Zanten, Arend Jan van, 80. % 2nd \vfill \enddoublecolumns \endchange \bye ******** I'm not sure yet about the Figure renumbering constant! ********** ******** (needs to be fixed also in err4f3 and err4f4) ******************** [The next printing will be the 2nd.] not listed above: page iii, The Stanford -> the Stanford page 1, I meant the "traditional military saying" lines to be unslanted page 1, fix dashes in Gilbert quote page 39, dots in Sayers and Lehmer quotes to come from cmssqi page 42, similarly in Duckworth quote page 69, I fixed the line break in the caption to Fig. 23 page 74, spacing in line 1 of exercise 107 page 79, answer 20: style of "Case 1" ... "Case 4" changed for conformity page 83, new version of \cal F page 84, avoided lineskip in answer 45 index entries for Lehmer, Sayers, R\"udiger, Reversing a string, Kent Triple index entries for Kedlaya and Kronecker product go away new index subentry "Permutations, balanced" index entry for "Transitive relation" becomes plural pages 37--39, 73--75, 97--100, 117--121: parindent too big on ex numbers > 99 in the index: Buchner moves to page 81, Paley moves to page 82 Also Cooke, matrix tree theorem, partition, hook, Young tableaux: 120->121 check 7.1.3.ref for changes: |inv-gray|=117, 4f2.4 |ruler-function|=44, 4f2.6 |test-for-zero-fields|=90, 4f2.11 |oplus-bound|=3, 4f2.80 |cycle-thru-mask|=79, 4f2.81 ARTICLES "TO APPEAR" THAT ARE STILL PENDING: Pak and Radoicic, exercise 7.2.1.2--69 [as of April 2007 it's still "preprint 2002" on Igor's research page; still "submitted" on Rados's page] Fink, solution to exercise 7.2.1.1--55 [was electronically accepted March 2007] Ruskey and Williams, in new answer 7.2.1.2--112, not yet submitted CROSS-REFERENCES TO "00": 7.2.3--|5bit-gray| 7.10--|bandwidth-of-n-cube|