|
The Art of Computer Programming, Fascicle 4: Generating All Trees - History of Combinatorial Generation (Art of Computer Programming)
To begin the fourth and later volumes of the set, Knuth has created a series of small books called fascicles, which publish at regular intervals. Each fascicle encompasses a section or more of wholly new material. Ultimately, the content of these fascicles will be rolled up into the comprehensive, final version of each volume, and the enormous undertaking
that began in 1962 will be complete. In the first part of this fascicle, Knuth establishes a strong foundation of tree generation through a very thorough discussion of the topic and 124 accompanying exercises. The second part of the fascicle consists of a never-before-told history of combinatorial patterns. From ancient Chinese, Indian, and Greek texts to elementary combinatorics in Persia, Japan, and Europe, ending with the arrival of electronic computers, combinatorial patterns often tie into poetry, music, and religion, making for a captivating read. The subsequent exercises are pulled from the early works on combinatorial generation described previously in this section.
Contents:
Chapter 7 Combinatorial Searching 1 7.2
Generating All Possibilities 1 7.2.1
Generating Basic Combinatorial Patterns 1 7.2.1.1
Generating all n-tuples 1 7.2.1.2
Generating all permutations 1 7.2.1.3 Generating all combinations 1 7.2.1.4 Generating all partitions 1 7.2.1.5 Generating all set partitions 2 7.2.1.6 Generating all trees 2 7.2.1.7 History and further references 48 Answers to Exercises 76Index and Glossary 112
Brief Description:
Focusing on the analysis of algorithms, this title covers the generation of various trees. Covering the history of combinatorial generation, it also tells a story of relevance to artful programmers.
|
