Combinatorial Algorithms
For Computers and Calculators
2nd Edition
Published on 10. May 2014
320 pages
978-1-4832-7345-7 (ISBN)
Description
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.
More details
Other editions
Additional editions
Albert Nijenhuis | Herbert S. Wilf
Combinatorial Algorithms
Book
01/1978
2nd Edition
Academic Press
€66.85
Article exhausted; check different version
Content
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)
