计算机程序设计艺术：第4卷 第2册 生成所有元组和排列（双语版）

　　关于算法分析的这多卷论著已经长期被公认为经典计算机科学的定义性描述。作为关于组合查找的冗长一章的一部分，这个分册开始关于如何生成所有可能性的讨论。具体地说，它讨论所有n元组的生成，然后把这些思想扩充到所有排列上。这样一些算法提供了一个自然的导引，借助于此，关于组合数学的许多关键思想都可加以介绍和剖析。.
　　 本册的出版揭开了人们急切等待的《计算机程序设计艺术 第4卷 组合算法》的序幕。作为关于组合查找的冗长一章的一部分，这一册开始讨论如何生成所有可能性。特定地说，它讨论所有n元组的生成，然后把这些思想扩充到所有排列上。这样一些算法提供了一个自然的导引，借助于此，关于组合数学的许多关键思想都可加以介绍和剖析。在第4卷的这一册和其他册中，通过讨论有关的游戏和数学难题，knuth阐明一个重要的观点：严肃的程序设计也可以是一种乐趣。...

preface.
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

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

　　我对所有朋友表示感谢，并且在这里把他们记录下来，我还要
　　对一个适当的期间之后，不再问我：“书写得怎样了”的那些朋友，
　　表示最特殊的感谢。
　　－彼得.约.戈姆斯(Peter J.Gomes)
　　好的书(1996)
　　本书是计算机程序设计艺术，第4卷，组合算法的第二分册。如同在第一卷的第一分册的序言中所说的那样，我在这个预备性的形式中来公布这些内容，因为我知道，完成第4卷的任务将花费多年时间。我迫不及待地等着人们来阅读我已写完的内容并向我提供宝贵的反馈意见。
　　也还将有第4卷的第1分册，但我先写完第2分册。有经验的程序员都懂得，在程序的主体完成之前，一个程序的初始化通常不能被适当地写出。
　　为把这些内容放进合适的范畴，这一分册包含了关于组合查找的一个极冗长的一章的7.2.1.1小节和7.2.1.2小节。假定我能保持自己的健康状态，则第7章将最终归入三卷中（即卷4A，4B和4C）。它将以图论的一个简短复习开始，重点在于突出斯坦福大学图库中的某些重要图形，从中我将引出许多例子，然后开始第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分册中。7.2.1.6小节（关于树）以及7.2.1.7（关于组合生成的历史）将组成第4分册。7.2.2一般地涉及回溯，然后如果一切顺利，它将继续下去。关于当前设想的整个第7章的轮廓如同在taocp的网页所见到的那样，在第ii页中对它作了引述。
　　我写这些内容时内心充满极大的愉快，就类似于在许多年前我写第2卷时所感到的激动那样。如同在第二卷中那样，在那里我高兴地发现，初等概率论和数论的基本原理很自然地出现在关于随机数生成和算术的算法的研究中。而当我准备编写7.2.1小节时，我注意到，当我们研究组合生成的算法时，初等组合学的基本原理自然地并以高度带激励的方式出现。因此，我再次发现，一个漂亮的故事就在那儿等候着被讲述。
　　我本打算以少得多的篇幅来讲述这一课题，但当我看到对于组合研究说来，一般地那些思想是何等地基本，我就知道了，除非我十分透彻地来讲述它们，否则我将决不可能满意。因此我正尽我所能地来构筑理论和实践的思想的坚固基础。它们将支持许多种类的可靠超级结构。
　　厌恶平方根或代数的普通男孩很喜欢涉及相同原理的智力
　　游戏，而且可能导致他去学习一门课程，而这将以使家庭成员
　　惊异的方式发展数学和创造发明的才能。
　　萨姆尔.洛伊德(SAM LOYD).
　　The world of puzzledom（困境的世界） (1986)
　　对于在这个分册中所出现的每个错误，当它是头一个向我报告的时，我将很高兴为发现者支付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’表示；这不可能的值是对于稍后要加以提供的实际数字的位置的表示。