The Art of Computer Programming 4 Generating all n-Tuples, Permutations, Combinations

1 Tuples
	Preface
	Generating basic combinatorial Patterns
	Algorithm M - mixed-Radix
	Gray Binary Code
	Algorithm G - Gray Binary
	Faster
	Algorithm L - loopless Gray Binary
	Other Binary Gray Codes
	Theorem D & Corollary B
	Binary Gray Paths
	Nonbinary Gray Codes
	Algorithm H - loopless reflected Mixed-Radix Gray
	Subforests
	Algorithm K - loopless reflected Subforest
	Shift Register Sequences
	Algorithm S - generic Shift Register
	Algorithm A - almost-linear Bit-Shift
	Algorithm R - recirsive de Bruijn Cycle
	Algorithm D - doubly recursive de Bruijn C
	Definition P
	Theorem P
	Definition Q & Theorem Q
	Algorithm F - prime & preprime String
	Exercise
	Answers
	Index
2 Permutations
	Preface
	Algorithm L - lexicographic Permutation
	Adjacent Interchanges
	Algorithm P - plain Changes
	Algorithm T - plain Change Transitions
	Alphametics
	General Framework
	Lemma S
	Using the General Framework
	Algorithm G - general Permutation
	Bypassing unwanted Blocks
	Algorithm X - lexicographic Permutations with restricted Prefixes
	Dual Methods
	Algorithm H - dual Permutation
	Algorithm C - cyclic Shifts
	Algorithm E - Ehrlich Swaps
	Using fewer Generators
	Theorem R
	Faster
	Topological Sorting
	Algorithm V - all topological Sorts
	Think twice
	Exercises
	Answers
	Index
3 Combinations
	Preface
	Generating all Combinations
	Lexicographic Generation
	Algorithm L - lexicographic Combinations
	Algorithm T - lexicographic Combinations
	Theorem L
	Binomial Trees
	Algorithm F - filling a Rucksack
	Gray Codes for Combinations
	Algorithm R - Revolving-Door Combinations
	Near-perfect Schemes
	Theorem N
	Algorithm C - Chase Sequence
	Analysis of Chase Sequence
	Near-perfect Multiset Permutations
	Perfect Schemes
	Theorem P
	Combinations of Multiset
	Shadows
	Theorem K
	Theorem M
	Theorem W
	Lemma S
	Corollary C
	Exercises
	Answers
	Index