Combinatorial Algorithms (eBook)

Front Cover 1
Combinatorial Algorithms: For Computers and Calculators 4
Copyright Page 5
Dedication 6
Table of Contents 8
Preface to Second Edition 14
Preface to First Edition 16
Introduction 18
Aims 18
Highlights 19
Categories of Usage (Part I) 20
Structure of the Chapters 22
The Specifications List 22
Structure of the "Next" Programs 23
Structure of the "Random" Programs 24
Arrays and Specifications 25
PART I: COMBINATORIAL FAMILIES 28
Chapter 1. Next Subset of an n-Set (NEXSUB/LEXSUB) 30
(A) The Direct Approach 31
(B) The Gray Code 31
Algorithm NEXSUB 34
(C) Lexicographic Sequencing 34
Algorithm LEXSUB 35
Subroutine Specifications (NEXSUB) 35
Subroutine Specifications (LEXSUB) 36
Sample Output (NEXSUB) 37
Sample Output (LEXSUB) 38
Chapter 2. Random Subset of an n-Set (RANSUB) 40
Algorithm RANSUB 40
Subroutine Specifications 40
Sample Output 41
Chapter 3. Next k-Subset of an n-Set (NEXKSB/NXKSRD) 43
Algorithm NEXKSB (Lexicographic) 44
Flow Chart NXKSRD 48
Subroutine Specifications (NEXKSB) 49
Subroutine Specifications (NXKSRD) 50
Sample Output (NEXKSB) 52
Sample Output (NXKSRD) 53
Chapter 4. Random k-Subset of an 
56 
Algorithm RANKSB 58
Algorithm RKS2 60
Subroutine Specifications 60
Sample Intermediate Result 62
Sample Output 62
Chapter 5. Next Composition of n into k Parts (NEXCOM) 63
Algorithm NEXCOM 66
Subroutine Specifications 66
Sample Output 67
Chapter 6. Random Composition of n into k Parts (RANCOM) 69
Algorithm RANCOM 69
Subroutine Specifications 69
Chapter 7. Next Permutation of n Letters (NEXPER) 71
Algorithm NEXPER 75
Subroutine Specifications 76
Sample Output 78
Chapter 8. Random Permutation of n Letters (RANPER) 79
Algorithm RANPER 79
Subroutine Specifications 80
Sample Output 80
Chapter 9. Next Partition of Integer n (NEXPAR) 82
Algorithm NEXPAR 85
Subroutine Specifications 86
Sample Output 87
Chapter 10. Random Partition of an Integer n (RANPAR) 89
Algorithm RANPAR 91
Subroutine Specifications 92
Sample Output 94
Postscript: Deus ex Machina 95
Algorithm NEXT PLANE PARTITION 101
Chapter 11. Next Partition of an n-Set (NEXEQU) 105
Algorithm NEXEQU 107
Subroutine Specifications 107
Sample Output 108
Chapter 12. Random Partition of an n-Set (RANEQU) 110
Algorithm RANEQU 112
Flow Chart RANEQU 113
Subroutine Specifications 114
Sample Output 115
Chapter 13. Sequencing, Ranking, and Selection Algorithms in General Combinatorial Families (SELECT) 116
(A) Introduction 116
(B) General Setting 117
Algorithm NEXT 119
(C) Examples 120
(D) The Formal Algorithms 123
Algorithm SELECT 124
Subroutine Specifications 125
(E) Decoding 130
Sample Output 132
Chapter 14. Young Tableaux (NEXYTB/RANYTB) 134
(A) Introduction 134
(B) Lexicographic Sequencing 137
Algorithm NEXYTB 139
(C) Random Selection 140
Algorithm RANYTB 144
Subroutine Specifications (NEXYTB) 145
Subroutine Specifications (RANYTB) 147
Sample Output 148
PART II: COMBINATORIAL STRUCTURES 150
Chapter 15. Sorting (HPSORT/EXHEAP) 152
Algorithm 
155 
Algorithm TOHEAP 155
Algorithm SORTHEAP 156
Subroutine Specifications (HPSORT) 157
Subroutine Specifications (EXHEAP) 158
Sample Output 159
Chapter 16. The Cycle Structure of a Permutation (CYCLES) 161
Algorithm TAG 162
Algorithm INVERT 163
Subroutine Specifications 163
Sample Output 165
Chapter 17. Renumbering Rows and Columns of an Array (RENUMB) 167
Algorithm RENUMB 172
Subroutine Specifications 172
Sample Output 174
Chapter 18. Spanning Forest of a Graph (SPANFO) 175
(A) Introduction 175
(B) Depth-First-Search 177
Algorithm DEPTHFIRST 178
(C) A Breadth-First Algorithm 178
Algorithm LINK (x, e, 
179 
Algorithm VISIT (x, e, n, E, q, l, 
181 
Algorithm SCAN (x, e, n, E, p, l0, m0, m, 
182 
Algorithm COMPONENT (x, e, n, E, p, 
182 
Algorithm SPANFO (x, e, 
183 
Subroutine Specifications 184
Sample Output 187
Chapter 19. Newton Forms of a Polynomial (POLY) 188
Algorithm VALUE 188
Algorithm NEWTON 189
Algorithm TAYLOR 190
Algorithm STIRLING 191
Algorithm REVERSE STIRLING 191
Algorithm NWT (m, x, e, 
192 
Subroutine Specifications 192
Sample Output 194
Chapter 20. Chromatic Polynomial of a Graph (CHROMP) 195
Algorithm CHROMP 199
Subroutine Specifications 200
Sample Output 202
Chapter 21. Composition of Power Series (POWSER) 204
Algorithm POWSER (Options 1, 2, and 3) 207
Algorithm POWSER (Option 4) 208
Subroutine Specifications 208
First Sample Output, Option 1 210
Second Sample Output, Option 1 211
Sample Output, Option 3 211
Sample Output, Option 4 212
Chapter 22. Network Flows (NETFLO) 213
Algorithm SWAP (i,j Option) 220
Algorithm INIT 220
Algorithm SORT 220
Algorithm XREF 221
Algorithm KZNET 222
Algorithm PUSHOUT ( p, P) 223
Algorithm OLDFLOW (p) 224
Algorithm PUSHBACK (p) 224
Flow Chart 
225 
Algorithm 
225 
Algorithm NETFLO (n, E, e, ., 
226 
Subroutine Specifications 226
Sample Output 232
Chapter 23. The Permanent Function (PERMAN) 234
Computation of the Permanent Function 237
Algorithm PERMAN 241
Subroutine Specifications 241
Sample Output 242
Chapter 24. Invert a Triangular Array (INVERT) 243
Algorithm INVERT 243
Subroutine Specifications 244
Chapter 25. Triangular Numbering in Partially Ordered Sets (TRIANG) 245
Algorithm TRIANG 247
Subroutine Specifications 247
Sample Output 248
Chapter 26. The Möbius Function 
250 
Subroutine Specifications 254
Sample Output 255
Chapter 27. The Backtrack Method (BACKTR) 257
(A) General (BACKTR) 257
Flow Chart BACKTR 261
Subroutine Specifications 262
(B) Coloring the Vertices of a Graph (COLVRT) 263
Subroutine Specifications 264
Sample Output 265
(C) Euler Circuits (EULCRC) 266
Algorithm EULCRC 267
Subroutine Spécifications 267
Sample Output 269
(D) Hamilton Circuits (HAMCRC) 273
Subroutine Specifications 274
Sample Output 1 275
Sample Output 2 277
(E) Spanning Trees (SPNTRE) 279
Subroutine Specifications 280
Sample Output 281
Chapter 28. Labeled Trees (LBLTRE) 284
Algorithm LBLTRE 288
Subroutine Specifications 289
Sample Output 290
Chapter 29. Random Unlabeled Rooted Trees (RANRUT) 291
Algorithm RANRUT 296
Subroutine Specifications 296
Sample Output 298
Chapter 30. Tree of Minimal Length (MINSPT) 300
Algorithm MINSPT 301
Subroutine Specifications 302
Sample Output 303
Exercises 305
Bibliographic Notes 311
References 313
Index 316