Combinatorial Algorithms

For Computers and Calculators

2nd Edition - October 28, 1978

Authors: Albert Nijenhuis, Herbert S. Wilf

Editor: Werner Rheinboldt

eBook ISBN:

9 7 8 - 1 - 4 8 3 2 - 7 3 4 5 - 7

Combinatorial Algorithms for Computers and Calculators, Second Edition deals with combinatorial algorithms for computers and calculators. Topics covered range from combinatorial… Read more

Purchase options

LIMITED OFFER

Save 50% on book bundles

Immediately download your ebook while waiting for your print delivery. No promo code is needed.

Combinatorial Algorithms for Computers and Calculators, Second Edition deals with combinatorial algorithms for computers and calculators. Topics covered range from combinatorial families such as the random subset and k-subset of an n-set and Young tableaux, to combinatorial structures including the cycle structure of a permutation and the spanning forest of a graph. Newton forms of a polynomial and the composition of power series are also discussed. Comprised of 30 chapters, this volume begins with an introduction to combinatorial algorithms by considering the generation of all of the 2n subsets of the set {1, 2,...,n}. The discussion then turns to the random subset and k-subset of an n-set; next composition of n into k parts; and random composition of n into k parts. Subsequent chapters focus on sequencing, ranking, and selection algorithms in general combinatorial families; renumbering rows and columns of an array; the cycle structure of a permutation; and the permanent function. Sorting and network flows are also examined, along with the backtrack method and triangular numbering in partially ordered sets. This book will be of value to both students and specialists in the fields of applied mathematics and computer science.

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