基本信息
- 原书名：The Art of Computer Programming, Volume 4, Fascicle 0: Introduction to Combinatorial Algorithms and Boolean Functions
- 原出版社： Addison-Wesley Professional
内容简介
书籍
计算机书籍
关于算法分析的这多卷论著已经长期被公认为经典计算机科学的定义性描述。迄今已出版的完整的三卷已经组成了程序设计理论和实践的唯一的珍贵源泉，无数读者都赞扬Knuth的著作对个人的深远影响。科学家们为他的分析的美丽和优雅所惊叹，而从事实践的程序员们已经成功地应用他的“菜谱式”的解到日常问题上，所有人都由于Knuth在书中所表现出的博学、清晰、精确和高度幽默而对他无比敬仰。
为开始第4卷及后续各卷的写作并更新现有三卷中的部分内容，Knuth创立了称作册的一系列小部头的书，定期出版。每一册将包含一部分或多个部分的全新的或修订的内容。最终，这些册子的内容将被归并成每卷综合的最后的版本，而在1962年开始的许多努力将得以完成。
本册揭开了计算机程序设计艺术目前最长一章的序幕，而论述组合算法的这章将包括完整的3卷。非正式地说，组合算法是对量非常大的对象，如排列或图元素，进行高速处理的技术。组合模式或排列技术可解决大量的现实问题，而处理这些问题的现代方法比起以前所采用的直接过程快上千倍。本册是后面章节的基础，这里首先讨论的是组合学的本质，接着介绍在计算机内部如何有效处理0和1的基本思想，包括布尔基础和布尔求值等内容。如常，为了强化作者的阐述，书中包括了大量细心组织、包括使用说明和详细解答的新的习题。
计算机书籍
关于算法分析的这多卷论著已经长期被公认为经典计算机科学的定义性描述。迄今已出版的完整的三卷已经组成了程序设计理论和实践的唯一的珍贵源泉，无数读者都赞扬Knuth的著作对个人的深远影响。科学家们为他的分析的美丽和优雅所惊叹，而从事实践的程序员们已经成功地应用他的“菜谱式”的解到日常问题上，所有人都由于Knuth在书中所表现出的博学、清晰、精确和高度幽默而对他无比敬仰。
为开始第4卷及后续各卷的写作并更新现有三卷中的部分内容，Knuth创立了称作册的一系列小部头的书，定期出版。每一册将包含一部分或多个部分的全新的或修订的内容。最终，这些册子的内容将被归并成每卷综合的最后的版本，而在1962年开始的许多努力将得以完成。
本册揭开了计算机程序设计艺术目前最长一章的序幕，而论述组合算法的这章将包括完整的3卷。非正式地说，组合算法是对量非常大的对象，如排列或图元素，进行高速处理的技术。组合模式或排列技术可解决大量的现实问题，而处理这些问题的现代方法比起以前所采用的直接过程快上千倍。本册是后面章节的基础，这里首先讨论的是组合学的本质，接着介绍在计算机内部如何有效处理0和1的基本思想，包括布尔基础和布尔求值等内容。如常，为了强化作者的阐述，书中包括了大量细心组织、包括使用说明和详细解答的新的习题。
目录
PREFACE iii
PREFACE TO VOLUME 4 v
Chapter 7 Combinatorial Searching
7.1 Zeros and Ones 47
7.1.1 Boolean Basics 47
7.1.2 Boolean Evaluation 96
Answers to Exercises 134
Index and Glossary 201
译者序 219
前言 221
第4卷前言 223
第7章 组 合 搜 索
7.1 0和1 274
7.1.1 布尔基础 274
7.1.2 布尔求值 321
习题答案 356
PREFACE TO VOLUME 4 v
Chapter 7 Combinatorial Searching
7.1 Zeros and Ones 47
7.1.1 Boolean Basics 47
7.1.2 Boolean Evaluation 96
Answers to Exercises 134
Index and Glossary 201
译者序 219
前言 221
第4卷前言 223
第7章 组 合 搜 索
7.1 0和1 274
7.1.1 布尔基础 274
7.1.2 布尔求值 321
习题答案 356
译者序
本书是克努特（Knuth，中文名为高德纳，亦翻译为克鲁特）巨著《计算机程序设计艺术》第4卷第0册的双语版（中文版），自从第4卷第2、3、4册的双语版出版以来，众多读者翘首以待第4卷前面各册双语版的出版已经有一段时日了，希望本书不会让大家失望。
译者最早是在20世纪80年代初在图书馆看到标为“克鲁特著，管纪文、苏运霖译”的《计算机程序设计技巧》多卷本的，那时译者在浙江大学上大学，正学习Aho等著的《计算机算法的设计与分析》（由译者翻译的该书中文版已由机械工业出版社出版），由于当时用的是原版书籍，许多概念一头雾水，正是该书帮我澄清了很多概念，打发了许多时间，也培养了我阅读的兴趣。
后来写些小论文，经常使用LaTeX这个软件，惊叹于它的美丽，看了软件的说明，知道是从事分布式计算研究的著名学者兰伯特（Leslie Lamport）在克努特的TeX上构建的宏集，也了解了克努特暂时中断巨著撰写的原因，明白了“工欲善其事，必先利其器”的道理。
事实上，克努特从来就没有中断过巨著的写作计划，几十年来他孜孜不倦地搜集素材，了解计算机科学各方面的进展，我们期望他身体康健，厚积博发（这里没有写错）。
2000年我在哈佛大学进修的时候，研究程序设计语言的Ramsey教授邀请克努特到哈佛来做个讲座，我才遇到他本人，看到的是无腿水晶眼镜后面那双睿智的眼睛，听到的是娓娓道来的各种典故新说，他介绍的是他自行设计的MMIX计算机，虽然一开始克努特就说道，我要讲到没有一个人想听的时候为止。可教室的十多个人都倾心听讲并不时发问，直到晌午，大家吃了主持者叫来的外卖比萨，还孜孜不倦地继续讨论着他设计的新千年RISC机器。
借此机会再谈一下本书，本书是第4卷第0册，介绍的是组合搜索的一些预备知识，要阅读第4卷后面各册的读者最好先读一下本书。另外，《计算机程序设计艺术》一书的很多习题富有挑战性，按照作者的标记，0是最容易的题目，45是已解决的难题，如费马大定理等，而大于45的基本是未知答案的难题，这也给大家设立算法研究目标提供了参考。
本书的习题和解答由杜思奇、曾慧清、张王朋和恽筱源初译，最后由黄林鹏整理。本书的翻译还得到孙永强教授和梅宏、童维勤、陆朝俊、陈翌佳等的帮助，在此表示真挚的谢意。
对于此书的翻译，说实在话，一是英语非译者母语，新翻译卷册的质量恐难延续苏运霖教授翻译的广受好评的三卷；二是整书涉及内容非常广泛，译者肯定力有不逮。无奈出版社多次提及，译者只能勉强为之。错误难免，如果读者发现敬请发到lphuang@sjtu.edu.cn，以便再版修改，不胜感激。
黄林鹏
于上海交通大学
2009年12月
译者最早是在20世纪80年代初在图书馆看到标为“克鲁特著，管纪文、苏运霖译”的《计算机程序设计技巧》多卷本的，那时译者在浙江大学上大学，正学习Aho等著的《计算机算法的设计与分析》（由译者翻译的该书中文版已由机械工业出版社出版），由于当时用的是原版书籍，许多概念一头雾水，正是该书帮我澄清了很多概念，打发了许多时间，也培养了我阅读的兴趣。
后来写些小论文，经常使用LaTeX这个软件，惊叹于它的美丽，看了软件的说明，知道是从事分布式计算研究的著名学者兰伯特（Leslie Lamport）在克努特的TeX上构建的宏集，也了解了克努特暂时中断巨著撰写的原因，明白了“工欲善其事，必先利其器”的道理。
事实上，克努特从来就没有中断过巨著的写作计划，几十年来他孜孜不倦地搜集素材，了解计算机科学各方面的进展，我们期望他身体康健，厚积博发（这里没有写错）。
2000年我在哈佛大学进修的时候，研究程序设计语言的Ramsey教授邀请克努特到哈佛来做个讲座，我才遇到他本人，看到的是无腿水晶眼镜后面那双睿智的眼睛，听到的是娓娓道来的各种典故新说，他介绍的是他自行设计的MMIX计算机，虽然一开始克努特就说道，我要讲到没有一个人想听的时候为止。可教室的十多个人都倾心听讲并不时发问，直到晌午，大家吃了主持者叫来的外卖比萨，还孜孜不倦地继续讨论着他设计的新千年RISC机器。
借此机会再谈一下本书，本书是第4卷第0册，介绍的是组合搜索的一些预备知识，要阅读第4卷后面各册的读者最好先读一下本书。另外，《计算机程序设计艺术》一书的很多习题富有挑战性，按照作者的标记，0是最容易的题目，45是已解决的难题，如费马大定理等，而大于45的基本是未知答案的难题，这也给大家设立算法研究目标提供了参考。
本书的习题和解答由杜思奇、曾慧清、张王朋和恽筱源初译，最后由黄林鹏整理。本书的翻译还得到孙永强教授和梅宏、童维勤、陆朝俊、陈翌佳等的帮助，在此表示真挚的谢意。
对于此书的翻译，说实在话，一是英语非译者母语，新翻译卷册的质量恐难延续苏运霖教授翻译的广受好评的三卷；二是整书涉及内容非常广泛，译者肯定力有不逮。无奈出版社多次提及，译者只能勉强为之。错误难免，如果读者发现敬请发到lphuang@sjtu.edu.cn，以便再版修改，不胜感激。
黄林鹏
于上海交通大学
2009年12月
前言
将所有好素材都放进一本书显然不可能，对一个主题的某个方面进行适当广泛的讨论甚至也可能导致篇幅的增长失去控制。
—杰拉尔德·弗兰德（Gerald B. Folland）编辑之角（2005）
著书立说最重要之事便是决定置何于卷首。
—布莱斯·帕斯卡尔（Blaise Pascal）《思想录》740（c.1660）
本书是《计算机程序设计艺术，第4卷：组合算法》的第0册。如本书第1卷第1册的前言所述，本书以这种分册的非完整形式出版是因为第4卷的写作将延续多年，而我却迫不及待地等待人们阅读我业已完成的部分内容并提供他们宝贵的反馈意见。
从整卷的情况看，本册是组合算法这一宏大篇章的起始。如果我身体状况许可，那么第7章会是《计算机程序设计艺术》一书最长的一章，其最终将划归为至少3个分卷（4A、4B和4C）。和篇幅次长的第5章类似，出现在主要内容之前的是介绍性的材料，其中包含了数十个习题。即将开始的漫漫征途需要备好充足的重要补给。另外，由于第6章的撰写和出版已有30多年了，我需要使第6章过渡到新一章的过程中出现的冲突尽可能少。
第7章以7.1节，即0和1，作为合适的起点，虽然层次不同，也是引论性的内容，在此我们深入探究作为计算机基础的布尔函数相关的所有重要问题。其中，7.1.1节为以后要建立的重要上层建筑打下坚实的理论和实践基础，7.1.2节则考虑如何最有效地计算一个布尔函数的值的问题。
7.1节的剩余部分7.1.3节和7.1.4节将作为第4卷第1册出版。接着的是7.2节，生成所有的可能性。对应于7.2.1节的分册已经出版，7.2.2节将从总体上对回溯问题进行研究。如果一切顺利，本书的篇章将继续延续，而目前规划的整个第7章的轮廓，可参见封底列出的TAOCP网址。
这些介绍性小节的习题数比我原先规划的要多出一倍。事实上，本册的习题总数是难以置信的336，但其中许多十分简单，目的是强化读者对基本概念的理解，或对斯坦福图库（The Stanford GraphBase）的了解。而其他习题真的是很有吸引力的，很有必要在这里出现。不管你相信与否，我拒绝了许多比这里出现的练习更有诱惑力的习题。
感谢Robert W. Floyd，1977年他应我之邀阅读了本书的草稿并给出了数十个极有价值的建设性意见。感谢开放大学的Robin Wilson，他仔细阅读了本书并提出了许多详细的建议。感谢数以百计的读者，他们针对本书草稿提出了许多极具价值的反馈意见并发布于互联网上。
对于本书出现的每一个错误，不管是印刷上的、技术上的还是与历史相关的，我都将乐意奉上2.56美元的酬谢给第一个报告的读者。如果你发现了忘了放进索引的条目，也可得到同样的酬谢。每个对行文进行改进的建议的酬谢是32美分（而且，如果你发现了一个习题更好的解，那么你得到的将远非金钱，作为荣誉性的奖励，我会在最后的出版物中列入你的名字）。
本册所用但未加说明的记法可参见第1、2或3卷中的记法索引。索引给出了与记法相关的进一步信息之所在（你还可参见各册“记法说明”之下的内容）。当然，未来某个时日，第4卷也会有它自己的记法索引。
与尚未完成的内容间的交叉索引有时以“00”标示，这个现在不存在的值留作他日填写实际页码之用。
祝大家阅读愉快！
D. E. K.
加利福尼亚，斯坦福
2008年1月
第4卷前言
第4卷的标题是组合算法，给出标题的时候我就很想加上一个子标题：我最喜欢的程序设计类型。但我的编辑认为题目应该不带感情色彩。但事实仍是，我一直喜欢散发有组合风味的程序。
另一方面，我经常惊奇地发现，在许多人的脑海里，单词“组合”是和计算难度联系在一起的。确实，在Samuel Johnson编著的闻名的英语语言字典（1755）中，他就称其相应的名词“现通常被用于引起痛苦的场合”。同事告诉我他遇到挫折时会说“各种困境的组合打败了我”。为何会这样呢？对我而言，组合学所引发的是完全纯净的喜悦；难道对其他人，它所唤起的会是纯粹的恐慌吗？
—杰拉尔德·弗兰德（Gerald B. Folland）编辑之角（2005）
著书立说最重要之事便是决定置何于卷首。
—布莱斯·帕斯卡尔（Blaise Pascal）《思想录》740（c.1660）
本书是《计算机程序设计艺术，第4卷：组合算法》的第0册。如本书第1卷第1册的前言所述，本书以这种分册的非完整形式出版是因为第4卷的写作将延续多年，而我却迫不及待地等待人们阅读我业已完成的部分内容并提供他们宝贵的反馈意见。
从整卷的情况看，本册是组合算法这一宏大篇章的起始。如果我身体状况许可，那么第7章会是《计算机程序设计艺术》一书最长的一章，其最终将划归为至少3个分卷（4A、4B和4C）。和篇幅次长的第5章类似，出现在主要内容之前的是介绍性的材料，其中包含了数十个习题。即将开始的漫漫征途需要备好充足的重要补给。另外，由于第6章的撰写和出版已有30多年了，我需要使第6章过渡到新一章的过程中出现的冲突尽可能少。
第7章以7.1节，即0和1，作为合适的起点，虽然层次不同，也是引论性的内容，在此我们深入探究作为计算机基础的布尔函数相关的所有重要问题。其中，7.1.1节为以后要建立的重要上层建筑打下坚实的理论和实践基础，7.1.2节则考虑如何最有效地计算一个布尔函数的值的问题。
7.1节的剩余部分7.1.3节和7.1.4节将作为第4卷第1册出版。接着的是7.2节，生成所有的可能性。对应于7.2.1节的分册已经出版，7.2.2节将从总体上对回溯问题进行研究。如果一切顺利，本书的篇章将继续延续，而目前规划的整个第7章的轮廓，可参见封底列出的TAOCP网址。
这些介绍性小节的习题数比我原先规划的要多出一倍。事实上，本册的习题总数是难以置信的336，但其中许多十分简单，目的是强化读者对基本概念的理解，或对斯坦福图库（The Stanford GraphBase）的了解。而其他习题真的是很有吸引力的，很有必要在这里出现。不管你相信与否，我拒绝了许多比这里出现的练习更有诱惑力的习题。
感谢Robert W. Floyd，1977年他应我之邀阅读了本书的草稿并给出了数十个极有价值的建设性意见。感谢开放大学的Robin Wilson，他仔细阅读了本书并提出了许多详细的建议。感谢数以百计的读者，他们针对本书草稿提出了许多极具价值的反馈意见并发布于互联网上。
对于本书出现的每一个错误，不管是印刷上的、技术上的还是与历史相关的，我都将乐意奉上2.56美元的酬谢给第一个报告的读者。如果你发现了忘了放进索引的条目，也可得到同样的酬谢。每个对行文进行改进的建议的酬谢是32美分（而且，如果你发现了一个习题更好的解，那么你得到的将远非金钱，作为荣誉性的奖励，我会在最后的出版物中列入你的名字）。
本册所用但未加说明的记法可参见第1、2或3卷中的记法索引。索引给出了与记法相关的进一步信息之所在（你还可参见各册“记法说明”之下的内容）。当然，未来某个时日，第4卷也会有它自己的记法索引。
与尚未完成的内容间的交叉索引有时以“00”标示，这个现在不存在的值留作他日填写实际页码之用。
祝大家阅读愉快！
D. E. K.
加利福尼亚，斯坦福
2008年1月
第4卷前言
第4卷的标题是组合算法，给出标题的时候我就很想加上一个子标题：我最喜欢的程序设计类型。但我的编辑认为题目应该不带感情色彩。但事实仍是，我一直喜欢散发有组合风味的程序。
另一方面，我经常惊奇地发现，在许多人的脑海里，单词“组合”是和计算难度联系在一起的。确实，在Samuel Johnson编著的闻名的英语语言字典（1755）中，他就称其相应的名词“现通常被用于引起痛苦的场合”。同事告诉我他遇到挫折时会说“各种困境的组合打败了我”。为何会这样呢？对我而言，组合学所引发的是完全纯净的喜悦；难道对其他人，它所唤起的会是纯粹的恐慌吗？
