Nijenhuis / Wilf / Rheinboldt Combinatorial Algorithms

For Computers and Calculators
2. Auflage 2014
ISBN: 978-1-4832-7345-7
Verlag: Elsevier Science & Techn.
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, 320 Seiten, Web PDF

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.

Autoren/Hrsg.

Nijenhuis, Albert

Wilf, Herbert S.

Rheinboldt, Werner

Inhaltsverzeichnis

1;Front Cover;1
2;Combinatorial Algorithms: For Computers and Calculators;4
3;Copyright Page;5
4;Dedication;6
5;Table of Contents;8
6;Preface to Second Edition;14
7;Preface to First Edition;16
8;Introduction;18
8.1;Aims;18
8.2;Highlights;19
8.3;Categories of Usage (Part I);20
8.4;Structure of the Chapters;22
8.5;The Specifications List;22
8.6;Structure of the "Next" Programs;23
8.7;Structure of the "Random" Programs;24
8.8;Arrays and Specifications;25
9;PART I: COMBINATORIAL FAMILIES;28
9.1;Chapter 1. Next Subset of an n-Set (NEXSUB/LEXSUB);30
9.1.1;(A) The Direct Approach;31
9.1.2;(B) The Gray Code;31
9.1.3;Algorithm NEXSUB;34
9.1.4;(C) Lexicographic Sequencing;34
9.1.5;Algorithm LEXSUB;35
9.1.6;Subroutine Specifications (NEXSUB);35
9.1.7;Subroutine Specifications (LEXSUB);36
9.1.8;Sample Output (NEXSUB);37
9.1.9;Sample Output (LEXSUB);38
9.2;Chapter 2. Random Subset of an n-Set (RANSUB);40
9.2.1;Algorithm RANSUB;40
9.2.2;Subroutine Specifications;40
9.2.3;Sample Output;41
9.3;Chapter 3. Next k-Subset of an n-Set (NEXKSB/NXKSRD);43
9.3.1;Algorithm NEXKSB (Lexicographic);44
9.3.2;Flow Chart NXKSRD;48
9.3.3;Subroutine Specifications (NEXKSB);49
9.3.4;Subroutine Specifications (NXKSRD);50
9.3.5;Sample Output (NEXKSB);52
9.3.6;Sample Output (NXKSRD);53
9.4;Chapter 4. Random k-Subset of an
n-Set (RANKSB);56
9.4.1;Algorithm RANKSB;58
9.4.2;Algorithm RKS2;60
9.4.3;Subroutine Specifications;60
9.4.4;Sample Intermediate Result;62
9.4.5;Sample Output;62
9.5;Chapter 5. Next Composition of n into k Parts (NEXCOM);63
9.5.1;Algorithm NEXCOM;66
9.5.2;Subroutine Specifications;66
9.5.3;Sample Output;67
9.6;Chapter 6. Random Composition of n into k Parts (RANCOM);69
9.6.1;Algorithm RANCOM;69
9.6.2;Subroutine Specifications;69
9.7;Chapter 7. Next Permutation of n Letters (NEXPER);71
9.7.1;Algorithm NEXPER;75
9.7.2;Subroutine Specifications;76
9.7.3;Sample Output;78
9.8;Chapter 8. Random Permutation of n Letters (RANPER);79
9.8.1;Algorithm RANPER;79
9.8.2;Subroutine Specifications;80
9.8.3;Sample Output;80
9.9;Chapter 9. Next Partition of Integer n (NEXPAR);82
9.9.1;Algorithm NEXPAR;85
9.9.2;Subroutine Specifications;86
9.9.3;Sample Output;87
9.10;Chapter 10. Random Partition of an Integer n (RANPAR);89
9.10.1;Algorithm RANPAR;91
9.10.2;Subroutine Specifications;92
9.10.3;Sample Output;94
9.11;Postscript: Deus ex Machina;95
9.11.1;Algorithm NEXT PLANE PARTITION;101
9.12;Chapter 11. Next Partition of an n-Set (NEXEQU);105
9.12.1;Algorithm NEXEQU;107
9.12.2;Subroutine Specifications;107
9.12.3;Sample Output;108
9.13;Chapter 12. Random Partition of an n-Set (RANEQU);110
9.13.1;Algorithm RANEQU;112
9.13.2;Flow Chart RANEQU;113
9.13.3;Subroutine Specifications;114
9.13.4;Sample Output;115
9.14;Chapter 13. Sequencing, Ranking, and Selection Algorithms in General Combinatorial Families (SELECT);116
9.14.1;(A) Introduction;116
9.14.2;(B) General Setting;117
9.14.3;Algorithm NEXT;119
9.14.4;(C) Examples;120
9.14.5;(D) The Formal Algorithms;123
9.14.6;Algorithm SELECT;124
9.14.7;Subroutine Specifications;125
9.14.8;(E) Decoding;130
9.14.9;Sample Output;132
9.15;Chapter 14. Young Tableaux (NEXYTB/RANYTB);134
9.15.1;(A) Introduction;134
9.15.2;(B) Lexicographic Sequencing;137
9.15.3;Algorithm NEXYTB;139
9.15.4;(C) Random Selection;140
9.15.5;Algorithm RANYTB;144
9.15.6;Subroutine Specifications (NEXYTB);145
9.15.7;Subroutine Specifications (RANYTB);147
9.15.8;Sample Output;148
10;PART II: COMBINATORIAL STRUCTURES;150
10.1;Chapter 15. Sorting (HPSORT/EXHEAP);152
10.1.1;Algorithm
(l, n);155
10.1.2;Algorithm TOHEAP;155
10.1.3;Algorithm SORTHEAP;156
10.1.4;Subroutine Specifications (HPSORT);157
10.1.5;Subroutine Specifications (EXHEAP);158
10.1.6;Sample Output;159
10.2;Chapter 16. The Cycle Structure of a Permutation (CYCLES);161
10.2.1;Algorithm TAG;162
10.2.2;Algorithm INVERT;163
10.2.3;Subroutine Specifications;163
10.2.4;Sample Output;165
10.3;Chapter 17. Renumbering Rows and Columns of an Array (RENUMB);167
10.3.1;Algorithm RENUMB;172
10.3.2;Subroutine Specifications;172
10.3.3;Sample Output;174
10.4;Chapter 18. Spanning Forest of a Graph (SPANFO);175
10.4.1;(A) Introduction;175
10.4.2;(B) Depth-First-Search;177
10.4.3;Algorithm DEPTHFIRST;178
10.4.4;(C) A Breadth-First Algorithm;178
10.4.5;Algorithm LINK (x, e,
n, E );179
10.4.6;Algorithm VISIT (x, e, n, E, q, l,
m, a);181
10.4.7;Algorithm SCAN (x, e, n, E, p, l0, m0, m,
r);182
10.4.8;Algorithm COMPONENT (x, e, n, E, p,
k, L);182
10.4.9;Algorithm SPANFO (x, e,
n, E, k);183
10.4.10;Subroutine Specifications;184
10.4.11;Sample Output;187
10.5;Chapter 19. Newton Forms of a Polynomial (POLY);188
10.5.1;Algorithm VALUE;188
10.5.2;Algorithm NEWTON;189
10.5.3;Algorithm TAYLOR;190
10.5.4;Algorithm STIRLING;191
10.5.5;Algorithm REVERSE STIRLING;191
10.5.6;Algorithm NWT (m, x, e,
. );192
10.5.7;Subroutine Specifications;192
10.5.8;Sample Output;194
10.6;Chapter 20. Chromatic Polynomial of a Graph (CHROMP);195
10.6.1;Algorithm CHROMP;199
10.6.2;Subroutine Specifications;200
10.6.3;Sample Output;202
10.7;Chapter 21. Composition of Power Series (POWSER);204
10.7.1;Algorithm POWSER (Options 1, 2, and 3);207
10.7.2;Algorithm POWSER (Option 4);208
10.7.3;Subroutine Specifications;208
10.7.4;First Sample Output, Option 1;210
10.7.5;Second Sample Output, Option 1;211
10.7.6;Sample Output, Option 3;211
10.7.7;Sample Output, Option 4;212
10.8;Chapter 22. Network Flows (NETFLO);213
10.8.1;Algorithm SWAP (i,j Option);220
10.8.2;Algorithm INIT;220
10.8.3;Algorithm SORT;220
10.8.4;Algorithm XREF;221
10.8.5;Algorithm KZNET;222
10.8.6;Algorithm PUSHOUT ( p, P);223
10.8.7;Algorithm OLDFLOW (p);224
10.8.8;Algorithm PUSHBACK (p);224
10.8.9;Flow Chart
PREFLOW;225
10.8.10;Algorithm
PREFLOW;225
10.8.11;Algorithm NETFLO (n, E, e, .,
source, sink, a, b, c, d, x);226
10.8.12;Subroutine Specifications;226
10.8.13;Sample Output;232
10.9;Chapter 23. The Permanent Function (PERMAN);234
10.9.1;Computation of the Permanent Function;237
10.9.2;Algorithm PERMAN;241
10.9.3;Subroutine Specifications;241
10.9.4;Sample Output;242
10.10;Chapter 24. Invert a Triangular Array (INVERT);243
10.10.1;Algorithm INVERT;243
10.10.2;Subroutine Specifications;244
10.11;Chapter 25. Triangular Numbering in Partially Ordered Sets (TRIANG);245
10.11.1;Algorithm TRIANG;247
10.11.2;Subroutine Specifications;247
10.11.3;Sample Output;248
10.12;Chapter 26. The Möbius Function
(MOBIUS);250
10.12.1;Subroutine Specifications;254
10.12.2;Sample Output;255
10.13;Chapter 27. The Backtrack Method (BACKTR);257
10.13.1;(A) General (BACKTR);257
10.13.2;Flow Chart BACKTR;261
10.13.3;Subroutine Specifications;262
10.13.4;(B) Coloring the Vertices of a Graph (COLVRT);263
10.13.5;Subroutine Specifications;264
10.13.6;Sample Output;265
10.13.7;(C) Euler Circuits (EULCRC);266
10.13.8;Algorithm EULCRC;267
10.13.9;Subroutine Spécifications;267
10.13.10;Sample Output;269
10.13.11;(D) Hamilton Circuits (HAMCRC);273
10.13.12;Subroutine Specifications;274
10.13.13;Sample Output 1;275
10.13.14;Sample Output 2;277
10.13.15;(E) Spanning Trees (SPNTRE);279
10.13.16;Subroutine Specifications;280
10.13.17;Sample Output;281
10.14;Chapter 28. Labeled Trees (LBLTRE);284
10.14.1;Algorithm LBLTRE;288
10.14.2;Subroutine Specifications;289
10.14.3;Sample Output;290
10.15;Chapter 29. Random Unlabeled Rooted Trees (RANRUT);291
10.15.1;Algorithm RANRUT;296
10.15.2;Subroutine Specifications;296
10.15.3;Sample Output;298
10.16;Chapter 30. Tree of Minimal Length (MINSPT);300
10.16.1;Algorithm MINSPT;301
10.16.2;Subroutine Specifications;302
10.16.3;Sample Output;303
11;Exercises;305
12;Bibliographic Notes;311
13;References;313
14;Index;316