关于算法分析的这多卷论著已经长期被公认为经典计算机科学的定义性描述。迄今已出版的完整的三卷组成了程序设计理论和实践的惟一的珍贵源泉，无数读者都赞扬Knuth的著作对个人的深远影响。科学家们为他的分析的美丽和优雅所惊叹，而从事实践的程序员们已经成功地应用他的“菜谱式”的解到日常问题上，所有人都由于Knuth在他的书中表现出的博学、清晰、精确和高度幽默而对他无比敬仰。
　　为开始后续各卷的写作并更新现有三卷中的部分内容，Knuth创立了称作册的一系列小部头的书，定期出版。每一册将包含一部分或多个部分的全新的或修订的内容。这些册的内容将归并成每卷综合的最终版本，而在1962年开始的许多努力将得以完成。
第4卷　 第2册
　　本册的出版揭开了人们急切等待的《计算机程序设计艺术 第4卷 组合算法》的序幕。作为关于组合查找的冗长一章的一部分，这一册开始讨论如何生成所有可能性。特定地说，它讨论所有n元组的生成，然后把这些思想扩充到所有排列上。这样一些算法提供了一个自然的导引，借助于此，关于组合数学的许多关键思想都可加以介绍和剖析。在第4卷的这一册和其他册中，通过讨论有关的游戏和数学难题，Knuth阐明一个重要的观点：严肃的程序设计也可以是一种乐趣。　
　　(说明：http://www-cs-faculty.stanford.edu/~knuth/taocp.html包含了与本书及相关图书有关的当前信息。http://www-cs-faculty.stanford.edu/~knuth/sgb.html 上有关于斯坦福图库的信息，包括可下载的软件，可用于处理第7章的许多例子中的图。 http://www-cs-faculty.stanford.edu/~knuth/mmix.html 上有关于MMIX计算机的基本信息。)

无

我对所有朋友表示感谢，并且在这里对那些一段时间之后不再问我：
　　“书写得怎样了”的朋友，表示最特殊的感谢。
　　—彼得．约．戈姆斯（Peter J. Gomes），
　　The Good Book（1996）
　　本书是《计算机程序设计艺术 第4卷 组合算法》的第2册。如同在第1卷第1册的前言中所说的那样，我采用这种预备性的形式来公布这些内容，因为我知道，完成第4卷的任务将花费多年时间。我迫不及待地等着人们来阅读我已写完的内容并向我提供宝贵的反馈意见。
　　第4卷将有第1册，甚至还有第0册，但我先写完第2册。有经验的程序员都懂得，在程序的主体完成之前，程序的初始化通常不能被适当地写出。
　　这一册包含了关于组合查找的一个极冗长的一章的7.2.1.1节和7.2.1.2节。假定我能保持自己的健康状态，则第7章将最终归入三卷中（即卷4A、4B和4C）。它将以图论的一个简短复习开始，重点在于突出The Stanford GraphBase一书中的某些重要图形，从中我将引出许多例子，然后开始7.1节。它将涉及按进位操作并讨论有关布尔函数的算法。7.2节是关于生成所有可能性的，而它由7.2.1节“生成基本的组合模式”开始，这就设置了本册的主要内容的框架，即7.2.1.1节（在这里我通过讨论n元组的生成来开始）和7.2.1.2节（该节把这个思想扩充到排列）。然后将是7.2.1.3节（关于组合）和7.2.1.4节（关于整数分划），以及7.2.1.5节（关于集合分划），这3节全在第3册中。7.2.1.6节（关于树）以及7.2.1.7节（关于组合生成的历史）将组成第4册。7.2.2节一般地讨论回溯，然后如果一切顺利，它将继续下去。关于当前设想的整个第7章的轮廓如同在taocp的网页所见到的那样，在封底中对它作了引述。
　　我怀着非常喜悦的心情来写这部分内容，就像许多年前写第2卷时我所感觉到的激动那样。如同在第2卷中那样，在那里我高兴地看到，初等概率论和数论的基本原理很自然地出现在关于随机数生成和算术运算的研究中。而在准备7.2.1节的过程中我了解到，当我们研究组合生成的算法时，初等组合学的基本原理也自然地出现，并且具有高度启发。因此，我再次发现，一个美丽的故事就在那里等候着被讲述。
　　我本打算以少得多的篇幅来讲述这一课题，但当我看到对于组合研究来说，那些思想是何等基本，我就知道了，除非我十分透彻地讲述它们，否则我将绝不可能满意。因此我正尽我所能地构筑理论和实践的思想的坚固基础，它们将支持许多种类的可靠的超级结构。
　　厌恶平方根或代数的普通男孩很喜欢玩相同原理的智力游戏，
　　而且可能导致他去学习一门课程，而这将以使家庭成员
　　惊异的方式发展数学和创造发明的才能。
　　—萨姆尔．洛伊德（Sam Loyd），
　　The World of Puzzledom（1896） 　　
　　对于在本册中所出现的每个错误，若是头一个向我报告的，我将很高兴为发现者支付2.56美元。无论这个错误是印刷上的、技术上的还是历史上的。对于我忘了放入索引中的条目，同样的报酬也适用。而每一个对于正文的改进建议值32美分。（而且，如果你找到一个习题的更好的解，我将通过在最后出版的书中发表你的名字，而不仅仅是钱，来给你以永久的荣誉的奖励。）
　　我愿在此对播口阳一表示感谢，是他帮助我构造和重新构造撰写本书的计算机，我还要感谢弗朗克 拉斯基（Frank Ruskey），因为他大胆地把本书的早期草稿介绍给大学生们并且向我讲述了他的授课经验。
　　这里所用的记号以及未加说明的那些记号可在第1、2、3卷末尾的记号索引中找到。那些索引指出可获得进一步信息的位置。当然，第4卷将在某一天包含它本身的记号索引。
　　在《计算机程序设计艺术》所有未来版本中的机器语言例子，都将以MMIX计算机为基础，它在第1卷第1册的1.3.1节中定义。对于现有小册子的1.3.1节、1.3.2节、1.4.1节、1.4.2节以及1.4.3节的交叉参考，请参阅相关分册。
　　对于尚未完成的内容的交叉参考有时在随后页中以“00”表示；这个不可能的值是日后要加以提供的实际号码的位置表示。
　　祝阅读愉快！

　　D. E. K
　　加利福尼亚，斯坦福
　　2004年12月

关于算法分析的这多卷论著已经长期被公认为经典计算机科学的定义性描述。迄今已出版的完整的三卷组成了程序设计理论和实践的惟一的珍贵源泉，无数读者都赞扬Knuth的著作对个人的深远影响。科学家们为他的分析的美丽和优雅所惊叹，而从事实践的程序员们已经成功地应用他的“菜谱式”的解到日常问题上，所有人都由于Knuth在他的书中表现出的博学、清晰、精确和高度幽默而对他无比敬仰。 为开始后续各卷的写作并更新现有三卷中的部分内容，Knuth创立了称作册的一系列小部头的书，定期出版。每一册将包含一部分或多个部分的全新的或修订的内容。这些册的内容将归并成每卷综合的最终版本，而在1962年开始的许多努力将得以完成。 第4卷 第2册 本册的出版揭开了人们急切等待的《计算机程序设计艺术 第4卷 组合算法》的序幕。作为关于组合查找的冗长一章的一部分，这一册开始讨论如何生成所有可能性。特定地说，它讨论所有n元组的生成，然后把这些思想扩充到所有排列上。这样一些算法提供了一个自然的导引，借助于此，关于组合数学的许多关键思想都可加以介绍和剖析。在第4卷的这一册和其他册中，通过讨论有关的游戏和数学难题，Knuth阐明一个重要的观点：严肃的程序设计也可以是一种乐趣。 (说明：http://www-cs-faculty.stanford.edu/~knuth/taocp.html包含了与本书及相关图书有关的当前信息。http://www-cs-faculty.stanford.edu/~knuth/sgb.html 上有关于斯坦福图库的信息，包括可下载的软件，可用于处理第7章的许多例子中的图。 http://www-cs-faculty.stanford.edu/~knuth/mmix.html 上有关于MMIX计算机的基本信息。)

Donald E.Knuth：Donald E.Knuth: 是算法和程序设计技术的先驱者，并发明了计算机排版系统TEX和METAFONT，他因这些成就和大量创造性的影响深远的论著而誉满全球。作为斯坦福大学计算机程序设计艺术的荣誉退休教授，Knuth现正投入全部的时间来完成其关于计算机科学的史诗性的七卷集。Knuth教授获得了许多奖项和荣誉，包括美国计算机协会图灵奖 (ACM Turing Award) ，美国前总统卡特授予的科学金奖 (Medal of Science) ，美国数学学会斯蒂尔奖 (AMS Steele Prize) ，以及极受尊重的京都奖 (Kyoto Prize) 。

苏运霖：颇具盛名的计算机科学专家，出生于印度尼西亚，曾任教于吉林大学、暨南大学，现任广西大学梧州分校顾问、计算机科学系主任，学科带头人。他曾被评为全国电工学会优秀科技工作者和电机工程优秀科技工作者，获国务院特殊津贴。他还被美国纽约科学院邀请为该院院士，名字被录入《国际传记辞典》、《国际卓越领导者名单》以及《世界知识名人录》。1983年到1986年间，与新西兰的几所著名大学研究组合算法、计算机网络、Petri网络理论。1989年，他到美国访问、讲学近一年，参加分布式算法的设计并撰写了一批有创见的论文。之后，他陆续到挪威、瑞典、瑞士、丹麦、奥地利、德国、比利时、冰岛、荷兰、卢森堡、日本、新加坡、印度尼西亚和香港等国家和地区讲学与访问。曾翻译D. E. Knuth的巨著《计算机程序设计艺术》，并编写了多部教材。

金秋华夏喜频传，神舟太空威尽现。在结束了第1卷第1册的翻译工作之后，我又立即投入了高德纳的第4卷第2、3册（现在已出版的即是这两册）的翻译工作。时间也从炎夏进入盛秋，而金秋时节的和风丽日，加上华夏大地频频传来的喜讯，给我的工作带来了强大的动力。
　　高德纳的这部巨著，始于1968年，而且很快，他就把前三卷完成了。人们原来以为，接下来出版的自然应该是第4卷了，然后顺理成章的是第5卷、第6卷，直到第7卷。然而，事实并非如此。近40年过去了，他对第1卷做过多次修改并再版。第2、3卷，也都分别至少做了一次修改并再版。而且如他所宣称的那样，每次修改，不论是哪一卷，都涉及几乎所有页面。工作量之大，作者为此付出之匠心，实在令人叹为观止。在此期间，他又发表了大量的论著，特别是完成了METAFONT和TEX，为计算机排版技术做出巨大贡献。完成了著名的《公理与外壳》和《具体数学》等著述。但是对于第4卷，却迟迟未闻有任何信息。只是后来才听说，第4卷将分为三个分卷出版，但也未见任何一卷问世。直到此前，人们才终于见到我现在译出的这第2册和第3册。至于后边还有多少分册，仍不得而知。因此，它的出场，真可谓是“犹抱琵琶半遮面”了。
　　但是，也正因为是经过几十年才出来的东西，因此它就不同凡响，是名副其实的专著和经典之作。作者在前言写道：“我怀着非常喜悦的心情来写这部分内容，就像许多年前写第2卷时我感觉到的激动那样。如同在第2卷中那样，在那里我高兴地看到，初等概率论和数论的基本原理很自然地出现在关于随机数生成和算术运算的研究中。而在准备7.2.1节的过程中我了解到，当我们研究组合生成的算法时，初等组合学的基本原理也自然地出现，并且具有高度启发性。”他感到，这里有着许多美丽的故事，等待他来讲述。
　　他说的确实是真的。我想，在这方面，至少有三个方面值得我们从中学习。我们不仅要学习其中的这些内容，还要学习作者的治学精神。
　　1. 首先是关于生成基本的组合模式的问题。
　　乍一看去，无论是生成所有n元组，还是生成排列，这些都不过是很简单的问题，并没有什么高深的理论，一说谁都知道，属于已经解决了的问题，再无什么遗留问题需要研究。然而，经过作者点拨，才发现事实上问题绝非我们所想像的那么简单。作者在提出对于这个问题的研究动机时指出，没有一个聪明人愿意通过以几千张纸来打印出{0，1，…，9}的所有10!=3 628 800个排列的清单，甚至也没有人愿意在一个计算机文件中把它们全写出来。但是，我们需要的是，当确实用得着它们时，在顷刻之间就以某种数据结构把它们提供出来，使得一个程序可以一次一个地来考察每个排列。正是出于这个目的，人们就还要考虑这样一个问题 。而且就这一点而言，它确实是远未解决的问题。
　　作者在研究中所体现的严谨性表现在，不仅考虑二进制，还考虑十进制和混合进制；不仅考虑集合的元素，还考虑集合的子集、多重集合等。因此，它就体现为既有问题的深度，又有问题的广度。
　　2. 关于组合模式同一些问题的关系
　　前边所说的深度，指的是如何以最快速度和最少内存访问来生成所需元组或排列。这样一个问题，竟是同图论有关，同哈密顿通路或循环有关，也同树形的遍历有关。因而作者在这里向我们揭示了这种关系，使我们懂得原来组合模式的问题还有这种背景，或者说可以从那些问题的求解中获得解决问题的理论基础。
　　记得几十年前当人工智能在我国掀起一股热潮时，一些人曾经从人工智能的角度研究过九链环（又称九龙环）的问题。然而，就译者所知，并没有任何一个中国学者，深入地去研究九链环问题的历史以及它的发展过程，更没有人去探讨它和其他问题的联系。但在这本书里，作者告诉我们，早在1872年法国人刘易斯?格罗斯在一本题为《步行理论》的小册子中，就揭示了九链环同二进制数之间的关系，比如我们以0表示环与杆分离的状态，而以1表示环在杆上的状态，则原来环锁在杆上的状态就是9个1的状态。问题是要通过从右边开始（或从左边开始），每次改换一位，最终使9个1变成为9个0。因此作者说，格罗斯才是格雷二进制码真正的发明者，也是九链环问题真正透彻的最初研究者。
　　所以，我们对于几十年前在我国人工智能学界曾经有过的研究九链环的热潮，不得不作一些反思，那就是我们对于问题的研究，是否确实应更着重于深度和广度。为什么不是我们，而是外国人来发现原本是我们提出的问题的理论基础，从而对它给出真正的解呢？
　　高德纳还列举了组合模式生成与欧洲教堂的洪钟鸣响模式的联系，揭示了各种钟鸣模式与生成排列的关系，这同样给人以巨大的启示。
　　3. 关于组合模式同字母算术或密码数学的关系
　　在国外，有些人或者生来就喜欢标新立异、独出心裁，或者有闲情逸致来这样做。因而很早以前就有人提出字母算术的概念。如亨利?厄思尼斯特?达德尼在1924年就提出这样一个著名问题：如果每个字母代表着不同的十进制数字，问要使
　　SEND
　　＋MORE
　　MONEY

　　表示一个正确的求和，则每个字母应当分别表示什么数？
　　这看似纯粹游戏的题目，却引发了人们的思考。假若要传送的是数字信息，用字母来对它们加密，这不就成了密码了吗？因而在1931年，西蒙?瓦特利宽特就给它起了另一个名称“密码数学”。
　　在他们的开创下，字母算术或密码数学就蓬勃发展起来。开头，人们关注于具有惟一解的问题。而后，人们开始考虑它们能有的各种解，乃至研究它有多少解。有惟一解的情况，称为纯的字母算术或纯的密码数学。而有的问题，不仅是字母上有意义，而且以数值解代入后仍正确。例如
　　VIOLIN+VIOLIN+VIOLA=TRIO+SUNATA
　　（小提琴+小提琴+中提琴=三重合奏）
　　ZEROES + ONES = BINARY
　　（诸0+诸1=二进制）
　　COUPLE+COUPLE=QUARTET
　　（两个+两个=四个）
等等。这些通过加法给出的字母算术，称为加法性字母算术。还可以有乘法性字母算术，例如
　　TWO×TWO=SQUARE
　　PI×R×R=AREA
等等。依照这些问题，我们也可以提出，如何代入数字，使
　　工业化+农业化+科学化=现代化
和
　　立党为公+执政为民=为人民服务
以及
　　更快×更高×更强=奥林匹克精神
成立？
　　除了字母算术外，也还有像在0与9这些数字之间，如何加上适当的加减乘除号，使得结果成为一个数，如100。在这方面的研究，不仅仅在于给出正确答案，还要研究它们可以有多少个解，如对于123456789，可以有12种方法来插入+和－，使其和为100，如100=1+23－4+5+6+78－9=123－45－67+89=－1+2－3+4+5+6+78+9。又如，在12345678987654321中，插入+和－的一个方式为100=－1234－5－6+7898－7－6543－2－1。
　　为了鼓励这方面的研究，国外出版了多种杂志，出版的专门书籍也不少。我们所知道的杂志就有J. Recreational Math（娱乐数学杂志）、Recreational Math. Magazine（娱乐数学期刊）等。这样，也就使这方面的研究长盛不衰，一直延续下来。它也推动了人们特别是青少年对于科学的兴趣和追求。
　　我们说，现代化的科学技术源自于基础理论。有了基础理论的深厚功底和深刻探索，才带来了现代科学技术的发展。最雄辩的例子是爱因斯坦的理论，乃是现代科学技术用之不竭的思想源泉。有一项研究表明，现代科学技术中直接利用爱因斯坦的理论成果的就达2300多项。因此我们可以斩钉截铁地说，没有基础数学的研究成果，也就没有今天的计算机科学和经济学等的辉煌成果。我国今天取得的航天领域的成就，也是我们在基础理论和综合科学技术方面的成就。然而，在我国仍然存在忽视基础理论研究的倾向，或者更确切地说，我们在基础理论研究上的投入和从事这方面研究的人数，同我们这样一个大国，是不大相称的。为了我国今后科学的持续发展，特别是为了使我国早日成为不仅是经济强国、军事强国，更是科学强国，我们希望上至党中央国务院，下至各地方党委政府，还有我国人民，都能从振兴中华，从民族的未来发展上重视这个问题。如果我们能引导青少年一代，首先重视自己的思想、素质的成长，然后是去专注于包括娱乐数学、娱乐物理这种难题的研究，从而激发对科学本身的兴趣，而不是沉溺于网上那些无聊的活动，那我们民族的科学素质就会大为改观。而到那时，科学大家的出现，诺贝尔奖、图灵奖的获得，都是指日可待的。
　　因此，我想，我们出版高德纳的书，其深远意义也应包括这些，而不仅仅在于计算机的那些算法本身上。
　　我们等待着祖国科学辉煌的明天。
　　译　 者
　　2006年2月于广西梧州

Chapter 7　
Combinatorial Searching
7.2　 Generating All Possibilities 2
7.2.1　 Generating Basic Combinatorial Patterns 2
7.2.1.1　 Generating all n-tuples 28
7.2.1.2　 Generating all permutations 51
Answers to Exercises 76
译者序 125
前言 129
第7章　 组 合 查 找
7.2　生成所有可能性 132
7.2.1　生成基本的组合模式 132
7.2.1.1　生成所有n元组 132
7.2.1.2　生成所有排列 170
习题答案 205
索引和词汇表 256