Combinatorial Algorithms

Preface to Second EditionPreface to First EditionIntroduction Aims Highlights Categories of Usage (Part I) Structure of the Chapters The Specifications List Structure of the "Next" Programs Structure of the "Random" Programs Arrays and SpecificationsPart 1 Combinatorial Families 1 Next Subset of an n-Set (NEXSUB/LEXSUB) (A) The Direct Approach (B) The Gray Code Algorithm NEXSUB (C) Lexicographic Sequencing Algorithm LEXSUB Subroutine Specifications (NEXSUB) Subroutine Specifications (LEXSUB) Sample Output (NEXSUB) Sample Output (LEXSUB) 2 Random Subset of an n-Set (RANSUB) Algorithm RANSUB Subroutine Specifications Sample Output 3 Next k-Subset of an n-Set (NEXKSB/NXKSRD) Algorithm NEXKSB (Lexicographic) Flow Chart NXKSRD Subroutine Specifications (NEXKSB) Subroutine Specifications (NXKSRD) Sample Output (NEXKSB) Sample Output (NXKSRD) 4 Random k-Subset of an n-Set (RANKSB) Algorithm RANKSB Algorithm RKS2 Subroutine Specifications Sample Intermediate Result Sample Output 5 Next Composition of n into k Parts (NEXCOM) Algorithm NEXCOM Subroutine Specifications Sample Output 6 Random Composition of n into k Parts (RANCOM) Algorithm RANCOM Subroutine Specifications 7 Next Permutation of n Letters (NEXPER) Algorithm NEXPER Subroutine Specifications Sample Output 8 Random Permutation of n Letters (RANPER) Algorithm RANPER Subroutine Specifications Sample Output 9 Next Partition of Integer n (NEXPAR) Algorithm NEXPAR Subroutine Specifications Sample Output 10 Random Partition of an Integer n (RANPAR) Algorithm RANPAR Subroutine Specifications Sample Output Postscript: Deus ex Machina Algorithm Next Plane Partition 11 Next Partition of an n-Set (NEXEQU) Algorithm NEXEQU Subroutine Specifications Sample Output 12 Random Partition of an n-Set (RANEQU) Algorithm RANEQU Flow Chart RANEQU Subroutine Specifications Sample Output 13 Sequencing, Ranking, and Selection Algorithms in General Combinatorial Families (SELECT) (A) Introduction (B) General Setting Algorithm NEXT (C) Examples (D) The Formal Algorithms Algorithm SELECT Subroutine Specifications (E) Decoding Sample Output 14 Young Tableaux (NEXYTB/RANYTB) (A) Introduction (B) Lexicographic Sequencing Algorithm NEXYTB (C) Random Selection Subroutine Specifications (NEXYTB) Subroutine Specifications (RANYTB) Sample OutputPart 2 Combinatorial Structures 15 Sorting (HPSORT/EXHEAP) Algorithm 𝔉(1, n) Algorithm TOHEAP Algorithm SORTHEAP Subroutine Specifications (HPSORT) Subroutine Specifications (EXHEAP) Sample Output 16 The Cycle Structure of a Permutation (Cycles) Algorithm TAG Algorithm INVERT Subroutine Specifications Sample Output 17 Renumbering Rows and Columns of an Array (RENUMB) Algorithm RENUMB Subroutine Specifications Sample Output 18 Spanning Forest of a Graph (SPANFO) (A) Introduction (B) Depth-First-Search Algorithm DEPTHFIRST (C) A Breadth-First Algorithm Algorithm LINK (x, e, n, E ) 162 Algorithm VISIT (x, e, n, E, q, l1, m1, a) 164 Algorithm SCAN (x, e, n, E, p, l0, m0, m, r) 165 Algorithm COMPONENT (x, e, n, E, p, k, L) 165 Algorithm SPANFO (x, e, n, E, k) Subroutine Specifications Sample Output 19 Newton Forms of a Polynomial (POLY) Algorithm VALUE Algorithm NEWTON Algorithm TAYLOR Algorithm STIRLING Algorithm REVERSE STIRLING Algorithm NWT (m, x, e, y) Subroutine Specifications Sample Output 20 Chromatic Polynomial of a Graph (CHROMP) Algorithm Chromp Subroutine Specifications Sample Output 21 Composition of Power Series (POWSER) Algorithm POWSER (Options 1, 2, and 3) Algorithm POWSER (Option 4) Subroutine Specifications First Sample Output, Option Second Sample Output, Option 1 Sample Output, Option 3 Sample Output, Option 4 22 Network Flows (NETFLO) Algorithm SWAP (i, j Option) Algorithm INIT Algorithm SORT Algorithm XREF Algorithm KZNET Algorithm PUSHOUT (p , P) Algorithm OLDFLOW (p) Algorithm PUSHBACK (p) Flow Chart PREFLOW Algorithm PREFLOW Algorithm NETFLO (n, E, e, y, source, sink, a, b, c, d, x) Subroutine Specifications Sample Output 23 The Permanent Function (PERMAN) Computation of the Permanent Function Algorithm PERMAN Subroutine Specifications Sample Output 24 Invert a Triangular Array (INVERT) Algorithm INVERT Subroutine Specifications 25 Triangular Numbering in Partially Ordered Sets (TRIANG) Algorithm TRIANG Subroutine Specifications Sample Output 26 The Möbius Function (MOBIUS) Subroutine Specifications Sample Output 27 The Backtrack Method (BACKTR) (A) General (BACKTR) Flow Chart BACKTR Subroutine Specifications (B) Coloring the Vertices of a Graph (COLVRT) Subroutine Specifications Sample Output (C) Euler Circuits (EULCRC) Algorithm EULCRC Subroutine Specifications Sample Output (D) Hamilton Circuits (HAMCRC) Subroutine Specifications Sample Output 1 Sample Output 2 (E) Spanning Trees (SPNTRE) Subroutine Specifications Sample Output 28 Labeled Trees (LBLTRE) Algorithm LBLTRE Subroutine Specifications Sample Output 29 Random Unlabeled Rooted Trees (RANRUT) Algorithm RANRUT Subroutine Specifications Sample Output 30 Tree of Minimal Length (MINSPT) Algorithm MINSPT Subroutine Specifications Sample OutputExercisesBibliographic NotesReferencesIndex