（已有11条评价）基本信息
- 原书名：The Art of Computer Programming: Volume 4,Fascicle 4: Generating All Trees History of Combinatorial Generation
- 原出版社： Addison-Wesley Professional
编辑推荐
算法和程序设计技术的先驱者、计算机排版系统TEX和METAFONT的发明者Donald.E.Knuth经典力作
knuth在本册中全面地讨论了这个著名的主题，提供了124个新的练习，继续为程序设计打下坚实的基础。
内容简介
书籍
计算机书籍
关于算法分析的这多卷论著已经长期被公认为经典计算机科学的定义性描述。迄今已出版的完整的三卷组成了程序设计理论和实践的惟一的珍贵源泉，无数读者都赞扬Knuth的著作对个人的深远影响。科学家们为他的分析的美丽和优雅所惊叹，而从事实践的程序员们已经成功地应用他的“菜谱式”的解到日常问题上，所有人都由于Knuth在书中所表现出的博学、清晰、精确和高度幽默而对他无比敬仰。.
为开始后续各卷的写作并更新现有三卷中的部分内容，Knuth创立了称作册的一系列小部头的书，定期出版。每一册将包含一部分或多个部分的全新的或修订的内容。最终，这些册的内容将归并成每卷综合的最终版本，而在1962年开始的许多努力将得以完成。..
本册主要讨论生成所有树，这个主题与《计算机程序设计艺术》前3卷有着令人吃惊的紧密联系。Knuth在本册中全面地讨论了这个著名的主题，提供了124个新的练习，继续为程序设计打下坚实的基础。同时，本册还论述了组合生成的历史。对几个文明古国及其他国家在这方面的历史进行了透彻的研究和精辟的分析。...
计算机书籍
关于算法分析的这多卷论著已经长期被公认为经典计算机科学的定义性描述。迄今已出版的完整的三卷组成了程序设计理论和实践的惟一的珍贵源泉，无数读者都赞扬Knuth的著作对个人的深远影响。科学家们为他的分析的美丽和优雅所惊叹，而从事实践的程序员们已经成功地应用他的“菜谱式”的解到日常问题上，所有人都由于Knuth在书中所表现出的博学、清晰、精确和高度幽默而对他无比敬仰。.
为开始后续各卷的写作并更新现有三卷中的部分内容，Knuth创立了称作册的一系列小部头的书，定期出版。每一册将包含一部分或多个部分的全新的或修订的内容。最终，这些册的内容将归并成每卷综合的最终版本，而在1962年开始的许多努力将得以完成。..
本册主要讨论生成所有树，这个主题与《计算机程序设计艺术》前3卷有着令人吃惊的紧密联系。Knuth在本册中全面地讨论了这个著名的主题，提供了124个新的练习，继续为程序设计打下坚实的基础。同时，本册还论述了组合生成的历史。对几个文明古国及其他国家在这方面的历史进行了透彻的研究和精辟的分析。...
作译者
Donald.E.Knuth：算法和程序设计技术的先驱者，是计算机排版系统TEX和METAFONT的发明者。Donald.E.Knuth(唐纳德.E.克努特，中文名高德纳)是斯坦福大学计算机程序设计艺术的荣誉退休教授，Knuth教授获得了许多奖项和荣誉，包括美国计算机协会图灵奖(ACM Turing Award)，美国前总统卡特授予的科学金奖(Medal of Science)，美国数学学会斯蒂尔奖(AMS Steele Prize)，以及1996年11月由于发明先进技术荣获的极受尊重的京都奖(KyotoPrize)。他因这些成就和大量创造性的影响深远的著作(19部书和160篇论文)而誉满全球。.
苏运霖：暨南大学教授，国内外颇具盛名的计算机科学专家。苏运霖教授是出生于印度尼西亚的华侨，他曾被选为全国电工学会优秀科技工作者和电机工程优秀科技工作者。他还被美国纽约科学院邀请为该院院士，名字被录入美国国际传记中心出版的《国际传记辞典》、英国传记研究所出版的《国际卓越领导者名单》，以及英国国际传记中心出版的《世界知识名人录》。...
苏运霖：暨南大学教授，国内外颇具盛名的计算机科学专家。苏运霖教授是出生于印度尼西亚的华侨，他曾被选为全国电工学会优秀科技工作者和电机工程优秀科技工作者。他还被美国纽约科学院邀请为该院院士，名字被录入美国国际传记中心出版的《国际传记辞典》、英国传记研究所出版的《国际卓越领导者名单》，以及英国国际传记中心出版的《世界知识名人录》。...
目录
译者序.
前言
第7章 组合查找
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 生成所有集合的分划
7.2.1.6 生成所有树
7.2.1.7 历史和进一步的参考文献
习题答案
索引和词汇表...
前言
第7章 组合查找
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 生成所有集合的分划
7.2.1.6 生成所有树
7.2.1.7 历史和进一步的参考文献
习题答案
索引和词汇表...
译者序
展现在你面前的这一分册是唐纳德·E克努特（即高德纳）第4卷的第3个分册。此前已经出版了第2和第3分册。.
作为计算机科学界的泰斗，高德纳又一次在本分册展现出他严谨的治学态度和追求完美、追求彻底的精神。
本书的正文部分实际上只有两个小节。一是生成所有可能的树。一开头他就指出：我们已经完成了关于经典组合学的概念的研究，即元组、排列、组合和分划。然而，计算机科学家们已经在传统的节目单上加上了称作树的层次体系的另一种基本的模式类。如果不讨论生成所有可能树的问题，显然会感到他的讨论还不够完整。这绝不是他的做事态度。因此，无论如何他都要对这个问题给予回答。
通过把嵌套的括弧和树相联系，使生成所有树的问题同卡塔兰数联系起来。进一步，他又通过把格雷码同树生成及嵌套括弧联系起来。这样一来，看似复杂的生成所有树的问题有了求解的有效途径。我们看到，生成所有树的问题在他手下不再是一个难题了。
使我们印象更深刻的是另一个小节，即关于生成所有可能组合这一问题的历史。在本分册中，高德纳对于几个文明古国以及其他国家在这方面的历史做了透彻的研究和精辟的分析。他首先介绍的是我国。这必然和易经相关，因为易经谈的是阴和阳两方面。这两者自然会有种种组合。然后介绍另一个文明古国印度。古代印度学者从完全不同的方面研究二进制。他们是在词律学中研究二进制，即从抑扬两种音的组合来研究。然后，介绍欧洲包括古希腊和古罗马的诗步。日本在这方面也同样有自己的创造。所以对于日本这一方面的工作，他也做了详细介绍。
我们看到，作为一名严肃的科学家，高德纳在做这些介绍时，采取的是尊重事实、尊重客观的态度，不带任何偏见，保证事实的准确性和调查的彻底性。还需指出，人们或许从某个角度也知道1，2，3，4，5，6，7，8，9这些数字按这个顺序排定，再考虑+，－，*，/ 以及左右括号等组成某个和数。然而，从组合学的角度来论述它们，并把这些事实集中在一起，这是高德纳的一个创造性工作。..
生成所有可能性还有一个特殊情况，即括弧的所有可能组合。看看如何组合，可使上述9个顺序的数字及运算符的结果成为100。高德纳给我们介绍了以下的可能性：
1+2*3+4*5－6+7+8*9
=（1+2－3－4）*（5－6－7－8－9）
=100
如果允许多位数字连在一起，我们可以得到：
（1/（2－3+4））*567－89=100
如果还允许使用小数点，还可以得到：
（.1－2－34*.5）/(.6－.789)=100
不仅如此，高德纳还讨论了对于上述三种类型，每种类型共有多少种可能性。比如，对于头一种情况，把这个问题表示为100=（（1/（（2+3）/4－5+6））*7+8）*9的9叉树，并把9个数字做成9个叶，有10 646 016种组合，共有1640个解。其中仅有一种是不使用乘法而只使用+ 、－、/ 的；有两种则需要5对括弧；有15种全然不用括弧。对于第二种情况，共有23 463 169种情况，其中有解的是3365种。对于第三种，则有8 157 017 474种情况，有96 504个解。但是，他没详细介绍结果如何得出。因此，对于读者来说，去算清这些结果仍然是一个激励思考的挑战。
译者...
2006年11月于梧州学院
作为计算机科学界的泰斗，高德纳又一次在本分册展现出他严谨的治学态度和追求完美、追求彻底的精神。
本书的正文部分实际上只有两个小节。一是生成所有可能的树。一开头他就指出：我们已经完成了关于经典组合学的概念的研究，即元组、排列、组合和分划。然而，计算机科学家们已经在传统的节目单上加上了称作树的层次体系的另一种基本的模式类。如果不讨论生成所有可能树的问题，显然会感到他的讨论还不够完整。这绝不是他的做事态度。因此，无论如何他都要对这个问题给予回答。
通过把嵌套的括弧和树相联系，使生成所有树的问题同卡塔兰数联系起来。进一步，他又通过把格雷码同树生成及嵌套括弧联系起来。这样一来，看似复杂的生成所有树的问题有了求解的有效途径。我们看到，生成所有树的问题在他手下不再是一个难题了。
使我们印象更深刻的是另一个小节，即关于生成所有可能组合这一问题的历史。在本分册中，高德纳对于几个文明古国以及其他国家在这方面的历史做了透彻的研究和精辟的分析。他首先介绍的是我国。这必然和易经相关，因为易经谈的是阴和阳两方面。这两者自然会有种种组合。然后介绍另一个文明古国印度。古代印度学者从完全不同的方面研究二进制。他们是在词律学中研究二进制，即从抑扬两种音的组合来研究。然后，介绍欧洲包括古希腊和古罗马的诗步。日本在这方面也同样有自己的创造。所以对于日本这一方面的工作，他也做了详细介绍。
我们看到，作为一名严肃的科学家，高德纳在做这些介绍时，采取的是尊重事实、尊重客观的态度，不带任何偏见，保证事实的准确性和调查的彻底性。还需指出，人们或许从某个角度也知道1，2，3，4，5，6，7，8，9这些数字按这个顺序排定，再考虑+，－，*，/ 以及左右括号等组成某个和数。然而，从组合学的角度来论述它们，并把这些事实集中在一起，这是高德纳的一个创造性工作。..
生成所有可能性还有一个特殊情况，即括弧的所有可能组合。看看如何组合，可使上述9个顺序的数字及运算符的结果成为100。高德纳给我们介绍了以下的可能性：
1+2*3+4*5－6+7+8*9
=（1+2－3－4）*（5－6－7－8－9）
=100
如果允许多位数字连在一起，我们可以得到：
（1/（2－3+4））*567－89=100
如果还允许使用小数点，还可以得到：
（.1－2－34*.5）/(.6－.789)=100
不仅如此，高德纳还讨论了对于上述三种类型，每种类型共有多少种可能性。比如，对于头一种情况，把这个问题表示为100=（（1/（（2+3）/4－5+6））*7+8）*9的9叉树，并把9个数字做成9个叶，有10 646 016种组合，共有1640个解。其中仅有一种是不使用乘法而只使用+ 、－、/ 的；有两种则需要5对括弧；有15种全然不用括弧。对于第二种情况，共有23 463 169种情况，其中有解的是3365种。对于第三种，则有8 157 017 474种情况，有96 504个解。但是，他没详细介绍结果如何得出。因此，对于读者来说，去算清这些结果仍然是一个激励思考的挑战。
译者...
2006年11月于梧州学院
前言
我喜欢在各种各样的领域中开展工作，使我不会犯明显的错误。.
—维克多·克里，(1999)
本册是《计算机程序设计艺术 第4卷 组合算法》的第4册。如第1卷第1册的前言所述，我采用这种分卷分册的出版形式，是因为我知道，完成第4卷的任务将花费许多年，我不能让读者等待太长的时间，而且我希望读者及时提供有价值的反馈意见。
从整卷的情况来看，这一册包括关于组合查找这一冗长章的7.2.1.6节和7.2.1.7节。假设我能维持自己的健康状态，第7章将最终归入三册中（即册4A、4B和4C）。第7章首先概述图论，强调在斯坦福图形库中一些重要图形的某些要点，从这出发我将引出许多例子。然后是7.1节，它涉及按位操作并讨论与布尔函数相关的一些算法。7.2节是关于生成所有可能性的，而且它由7.2.1节“生成基本的组合模式”开始。7.2.1.1~7.2.1.5节讨论生成n元组、排列、组合以及分划的各种方法的细节。下面两节是本册的主要内容，即7.2.1.6节（通过论述怎样生成各种不同类型的树结构而研究基本模式）以及7.2.1.7节（研究前面各节中概念的起源，并介绍与这些概念相关的参考信息）。7.2.2节将概述回溯。如果一切进展顺利，我将继续写下去。目前规划的整个第7章的轮廓，可参见封底所给出的taocp网页。
我怀着无比喜悦的心情来写这部分内容，就像许多年前写第2卷时的感受一样。在写第2卷时我高兴地发现，初等概率论和数论的基本原理很自然地出现在关于随机数生成和算术的算法研究中。而在写作7.2.1节的过程中我了解到，当我们研究组合生成的一些算法时，初等组合学的基本原理也自然地浮现出来，并且具有高度启发性。因此，我可以再次讲述一个美丽的故事。..
树结构在所有计算机科学家的心中占据着一个特殊的位置，事实上，很久以来我就想写关于树的生成。尽管我的确很喜欢写7.2.1.1~7.2.1.5节中的元组、排列、组合和分划这些经典的组合结构，但实际上，我更倾心于最后这一部分：宴会结束前的甜品。自1994年以来，我每年在斯坦福大学举办“圣诞树讲座”，谈论该年关于树最值得关注的事实，最后，我把这些讲座的内容汇总成书。这个课题如同甜品一样，内容极为丰富多彩，令人回味无穷。树理论把计算机程序设计中不同方面的许多概念紧密地联结在一起。
7.2.1.7节中关于组合生成的历史，同样令我大脑的另一半得到满足，因为这部分内容涉及诗歌、音乐、宗教、哲学、逻辑以及在世界各地来自不同文化的智力游戏。组合思维的根源很深，我禁不住想，当我把这个故事的各个部分合并在一起时，总的来说，我学习了很多关于人类的事情。
我原来打算简单介绍这些课题，但当我看到，这些思想是何等重要时，我就懂得了，除非我十分透彻地讲解这些基础知识，否则我绝不会感到快乐。因此，我竭尽全力来构筑理论和实践思想的坚实基础，这些思想将支持许多类型的可靠的超级结构。
我要向弗朗克·拉斯基表示感谢，感谢他大胆地向学生们讲授本书的初稿并向我讲述他的授课经验。还有许多其他读者也帮助我检查最初的一些草稿，特别是7.2.1.7节，我经常挑战我的能力极限来理解非英语的内容。
我还将高兴地为头一个向我报告本分册中的每一个错误的人支付2.56美元的酬金，无论这个错误是印刷上的、技术上的还是历史上的。对于我忘了放进索引的那些条目，也有同样的酬金。而对于正文的有价值的改进建议，每一个将获32美分的奖励。（而且，如果你找到一个习题更好的答案，我将通过在最后出版的书中刊登你的名字来给予永久的荣誉，而不仅仅是钱。）
本书对于尚未完成内容的引用，有时以“00”表示，这是以后要予以提供的实际号码的位置。
祝阅读愉快！
D.E.K
加利福尼亚，斯坦福
2005年6月...
—维克多·克里，(1999)
本册是《计算机程序设计艺术 第4卷 组合算法》的第4册。如第1卷第1册的前言所述，我采用这种分卷分册的出版形式，是因为我知道，完成第4卷的任务将花费许多年，我不能让读者等待太长的时间，而且我希望读者及时提供有价值的反馈意见。
从整卷的情况来看，这一册包括关于组合查找这一冗长章的7.2.1.6节和7.2.1.7节。假设我能维持自己的健康状态，第7章将最终归入三册中（即册4A、4B和4C）。第7章首先概述图论，强调在斯坦福图形库中一些重要图形的某些要点，从这出发我将引出许多例子。然后是7.1节，它涉及按位操作并讨论与布尔函数相关的一些算法。7.2节是关于生成所有可能性的，而且它由7.2.1节“生成基本的组合模式”开始。7.2.1.1~7.2.1.5节讨论生成n元组、排列、组合以及分划的各种方法的细节。下面两节是本册的主要内容，即7.2.1.6节（通过论述怎样生成各种不同类型的树结构而研究基本模式）以及7.2.1.7节（研究前面各节中概念的起源，并介绍与这些概念相关的参考信息）。7.2.2节将概述回溯。如果一切进展顺利，我将继续写下去。目前规划的整个第7章的轮廓，可参见封底所给出的taocp网页。
我怀着无比喜悦的心情来写这部分内容，就像许多年前写第2卷时的感受一样。在写第2卷时我高兴地发现，初等概率论和数论的基本原理很自然地出现在关于随机数生成和算术的算法研究中。而在写作7.2.1节的过程中我了解到，当我们研究组合生成的一些算法时，初等组合学的基本原理也自然地浮现出来，并且具有高度启发性。因此，我可以再次讲述一个美丽的故事。..
树结构在所有计算机科学家的心中占据着一个特殊的位置，事实上，很久以来我就想写关于树的生成。尽管我的确很喜欢写7.2.1.1~7.2.1.5节中的元组、排列、组合和分划这些经典的组合结构，但实际上，我更倾心于最后这一部分：宴会结束前的甜品。自1994年以来，我每年在斯坦福大学举办“圣诞树讲座”，谈论该年关于树最值得关注的事实，最后，我把这些讲座的内容汇总成书。这个课题如同甜品一样，内容极为丰富多彩，令人回味无穷。树理论把计算机程序设计中不同方面的许多概念紧密地联结在一起。
7.2.1.7节中关于组合生成的历史，同样令我大脑的另一半得到满足，因为这部分内容涉及诗歌、音乐、宗教、哲学、逻辑以及在世界各地来自不同文化的智力游戏。组合思维的根源很深，我禁不住想，当我把这个故事的各个部分合并在一起时，总的来说，我学习了很多关于人类的事情。
我原来打算简单介绍这些课题，但当我看到，这些思想是何等重要时，我就懂得了，除非我十分透彻地讲解这些基础知识，否则我绝不会感到快乐。因此，我竭尽全力来构筑理论和实践思想的坚实基础，这些思想将支持许多类型的可靠的超级结构。
我要向弗朗克·拉斯基表示感谢，感谢他大胆地向学生们讲授本书的初稿并向我讲述他的授课经验。还有许多其他读者也帮助我检查最初的一些草稿，特别是7.2.1.7节，我经常挑战我的能力极限来理解非英语的内容。
我还将高兴地为头一个向我报告本分册中的每一个错误的人支付2.56美元的酬金，无论这个错误是印刷上的、技术上的还是历史上的。对于我忘了放进索引的那些条目，也有同样的酬金。而对于正文的有价值的改进建议，每一个将获32美分的奖励。（而且，如果你找到一个习题更好的答案，我将通过在最后出版的书中刊登你的名字来给予永久的荣誉，而不仅仅是钱。）
本书对于尚未完成内容的引用，有时以“00”表示，这是以后要予以提供的实际号码的位置。
祝阅读愉快！
D.E.K
加利福尼亚，斯坦福
2005年6月...
