关于算法分析的这多卷论著已经长期被公认为经典计算机科学的定义性描述。迄今已出版的完整的三卷组成了程序设计理论和实践的惟一的珍贵源泉，无数读者都赞扬Knuth的著作对个人的深远影响。科学家们为他的分析的美丽和优雅所惊叹，而从事实践的程序员们已经成功地应用他的“菜谱式”的解到日常问题上，所有人都由于Knuth在他的书中表现出的博学、清晰、精确和高度幽默而对他无比敬仰。
　　为开始后续各卷的写作并更新现有三卷中的部分内容，Knuth创立了称作册的一系列小部头的书，定期出版。每一册将包含一部分或多个部分的全新的或修订的内容。这些册的内容将归并成每卷综合的最终版本，而在1962年开始的许多努力将得以完成。

第4册　　第3册
　　本册以及第4卷第2册的出版揭开了人们急切等待的《计算机程序设计艺术 第4卷 组合算法》的序幕。作为关于组合查找的冗长一章的一部分，这一册开始关于生成所有组合和分划的讨论。在Knuth讨论这两个主题的过程中，读者不仅会看到很多新内容，并且会发现本册与前三卷及计算机科学和数学的其他方面的丰富联系。一如既往，书中包括了大量的习题和富有挑战性的难题。通过讨论有关的游戏和数学难题，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计算机的基本信息。)

无

在我的第1版的前言中，
　　我请求读者不要去注意错误，
　　我现在希望我不曾这样做，
　　而对于忽略我请求的少数读者我谨致谢意。
　　—施图亚特．苏德兰德，The International Dictionary of Psychology (1996)
　　本册是《计算机程序设计艺术 第4卷 组合算法》的第3册，如同在第1卷第1册的前言中所说明的那样，我以这种预备形式来传播这个材料，因为我知道，完成第4卷的任务将花费许多年。我急不可待地让人们开始来读迄今我已写成的材料，并且提供有价值的反馈。
　　从整卷的情况来看，这一册包含关于组合查找的这一冗长一章的7.2.1.3节、7.2.1.4节和7.2.1.5节。假设我能维持自己的健康状态，第7章将最终归入三卷中(即卷4A、4B和4C)。它将以关于图论的一个简短复习开始，并且强调在斯坦福图库中一些重要图形的某些要点，从这出发我将引出许多例子。然后是7.1节，它涉及按位操作并讨论有关布尔函数的一些算法。7.2节是关于生成所有可能性的，而且它由7.2.1节“生成基本的组合模式”开始。关于生成n元组的各种有用方法的细节在7.2.1.1节中，而在7.2.1.2节中讨论排列的生成。这就设置了本册的主要内容的框架，即7.2.1.3节(把这些思想推广到一次从n个事物中取t个组合)；7.2.1.4节(关于一个整数的分划)；以及7.2.1.5节(关于一个集合的分划)。然后是在第4册中给出7.2.1.6节(关于树形)和7.2.1.7节(关于组合生成的历史)。7.2.2节将一般地讨论回溯。因此如果一切进展顺利，它将继续下去。作为当前想像的整个第7章的轮廓，可参见封底所给出的taocp网页。
　　我怀着非常喜悦的心情来写这部分内容，就像许多年前写第2卷时我感觉到的激动那样。如同在第2卷中那样，在那里我高兴地看到，初等概率论和数论的基本原理很自然地出现在关于随机数生成和算术运算的研究中。而在准备7.2.1节的过程中我了解到，当我们研究组合生成的算法时，初等组合学的基本原理也自然地出现，并且具有高度启发性。因此，我再次发现，一个美丽的故事就在那里等候着被讲述。
　　例如，在本册中，我们发现由组合形成的许多美丽的模式，有的有重复，有的没有重复，而且还知道，它们如何同外部组合学的著名定理相关联。于是，这就成了我来讲述分划的不同寻常的故事的机会了；确实，关于分划的理论是所有数学中最为优美的章节之一，而且在7.2.1.5节中，由查 圣 珀西(C.S.Peirce)所发现的鲜为人知的数的三角形证明，是简化和统一化集合分划的研究，是另一个重要的课题。沿着这一方面，我还对算法分析中极为重要的两个数学技术进行了剖析：即泊松(Poisson)的求和公式和强有力的马鞍点方法。如同在以前的分册中那样，也还有游戏和难题。
　　我原来打算简单介绍这些课题，但当我看到，这些想法对于一般的组合研究是何等基本时，我就懂得了，除非我十分透彻地讲解这些基础，否则我绝不会感到快乐。因此我就尽最大努力来构筑理论和实践的思想的一个坚实基础，它们将支持许多类型的可靠的超级结构。
　　我要向弗朗克 拉斯基表示感谢，感谢他大胆地向大学生们讲授本书的初稿并向我讲述他的授课经验。还有许多其他读者也帮助我检查最初的一些草稿，我还要特别感谢乔治 克莱门特斯(George Clements)和斯万特 简森(Svante Janson)的深刻透彻的评论。
　　我还将高兴地为头一个向我报告本分册中的每一个错误的人支付2.56美元的酬金，无论这个错误是印刷上的、技术上的还是历史上的。对于我忘了放进索引的那些条目，也有同样的酬金。而对于正文的有价值的改进建议，每一个将获32美分的奖励。(而且，如果你找到一个习题更好的解答，我将通过在最后出版的书中公布你的名字来实际上以永久的荣誉来奖励你，而不仅仅是钱。)
　　这里所使用的记号以及未予说明的记号可以在第1、2或3卷末尾的记号索引中找到。这些索引指向可以获得进一步信息的那些位置。当然，某天第4卷也将包含它自己的记号索引。
　　在《计算机程序设计艺术》所有未来版本中的机器语言的例子，都将基于MMIX计算机，它在第1卷第1册中介绍过了。
　　在以下的篇幅中，对于尚未完成的内容的交叉参考有时以“00”来表示；这个不可能的值是以后要予以提供的实际号码的位置表示。
　　祝阅读愉快!
　　D.E.K.
　　加利福尼亚，斯坦福
　　2005年6月

　　关于算法分析的这多卷论著已经长期被公认为经典计算机科学的定义性描述。迄今已出版的完整的三卷组成了程序设计理论和实践的惟一的珍贵源泉，无数读者都赞扬Knuth的著作对个人的深远影响。科学家们为他的分析的美丽和优雅所惊叹，而从事实践的程序员们已经成功地应用他的“菜谱式”的解到日常问题上，所有人都由于Knuth在他的书中表现出的博学、清晰、精确和高度幽默而对他无比敬仰。 　　为开始后续各卷的写作并更新现有三卷中的部分内容，Knuth创立了称作册的一系列小部头的书，定期出版。每一册将包含一部分或多个部分的全新的或修订的内容。这些册的内容将归并成每卷综合的最终版本，而在1962年开始的许多努力将得以完成。 第4册　　第3册 本册以及第4卷第2册的出版揭开了人们急切等待的《计算机程序设计艺术 第4卷 组合算法》的序幕。作为关于组合查找的冗长一章的一部分，这一册开始关于生成所有组合和分划的讨论。在Knuth讨论这两个主题的过程中，读者不仅会看到很多新内容，并且会发现本册与前三卷及计算机科学和数学的其他方面的丰富联系。一如既往，书中包括了大量的习题和富有挑战性的难题。通过讨论有关的游戏和数学难题，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计算机的基本信息。)

苏运霖：颇具盛名的计算机科学专家，出生于印度尼西亚，曾任教于吉林大学、暨南大学，现任广西大学梧州分校顾问、计算机科学系主任，学科带头人。他曾被评为全国电工学会优秀科技工作者和电机工程优秀科技工作者，获国务院特殊津贴。他还被美国纽约科学院邀请为该院院士，名字被录入《国际传记辞典》、《国际卓越领导者名单》以及《世界知识名人录》。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 0
7.2.1　 Generating Basic Combinatorial Patterns 0
7.2.1.1　 Generating all n-tuples 0
7.2.1.2　 Generating all permutations 0
7.2.1.3　 Generating all combinations 1
7.2.1.4　 Generating all partitions 36
7.2.1.5　 Generating all set partitions 61
Answers to Exercises 87
目　　　录
译者序 147
前言 151
第7章　 组合查找
7.2　生成所有可能性 154
7.2.1　生成基本的组合模式 154
7.2.1.1　生成所有n元组 154
7.2.1.2　生成所有排列 154
7.2.1.3　生成所有组合 154
7.2.1.4　生成所有分划 188
7.2.1.5　生成所有集合的分划 212
习题答案 238
索引和词汇表 305