《Combinatorial Algorithms Second Edition》

ContentsPreface to Second Edition13

Preface to First Edition15

Introduction1

Aims1

Highlights2

Categories of Usage(Part Ⅰ)3

Structure of the Chapters5

The Specifications List5

Structure of the"Next"Programs6

Structure of the"Random"Programs7

Arrays and Specifications8

PART 1 COMBINATORIAL FAMILIES8

1 Next Subset of an n-Set(NEXSUB/LEXSUB)13

(A)The Direct Approach14

(B)The Gray Code14

Algorithm NEXSUB17

(C)Lexicographic Sequencing17

Algorithm LEXSUB18

Subroutine Specifications(NEXSUB)18

Subroutine Specifications(LEXSUB)19

Sample Output(NEXSUB)20

Sample Output(LEXSUB)21

2 Random Subset of an n-Set(RANSUB)23

Algorithm RANSUB23

Subroutine Specifications23

Sample Output24

3 Next k-Subset of an n-Set(NEXKSB/NXKSRD)26

Algorithm NEXKSB(Lexicographic)27

Flow Chart NXKSRD31

Subroutine Specifications(NEXKSB)32

Subroutine Specifications(NXKSRD)33

Sample Output(NEXKSB)35

Sample Output(NXKSRD)36

4 Random k-Subset of an n-Set(RANKSB)39

Algorithm RANKSB41

Algorithm RKS243

Subroutine Specifications43

Sample Intermediate Result45

Sample Output45

5 Next Composition of n into k Parts(NEXCOM)46

Algorithm NEXCOM49

Subroutine Specifications49

Sample Output50

6 Random Composition of n into k Parts(RANCOM)52

Algorithm RANCOM52

Subroutine Specifications52

7 Next Permutation of n Letters(NEXPER)54

Algorithm NEXPER58

Subroutine Specifications59

Sample Output61

8 Random Permutation of n Letters(RANPER)62

Algorithm RANPER62

Subroutine Specifications63

Sample Output63

9 Next Partition of Integer n(NEXPAR)85

Algorithm NEXPAR68

Subroutine Specifications69

Sample Output70

10 Random Partition of an Integer n(RANPAR)72

Algorithm RANPAR74

Subroutine Specifications75

Sample Output77

Postscript:Deus ex Machina78

Algorithm NEXT PLANE PARTITION84

11 Next Partition of an n-Set(NEXEQU)88

Algorithm NEXEQU90

Subroutine Specifications90

Sample Output91

12 Random Partition of an n-Set(RANEQU)93

Algorithm RANEQU95

Flow Chart RANEQU96

Subroutine Specifications97

Sample Output98

13 Sequencing,Ranking,and Selection Algorithms in General Combinatorial Families(SELECT)99

(A)Introduction99

(B)General Setting100

Algorithm NEXT102

(C)Examples103

(D)The Formal Algorithms106

Algorithm SELECT107

Subroutine Specifications108

(E)Decoding113

Sample Output115

14 Young Tableaux(NEXYTB/RANYTB)117

(A)Introduction117

(B)Lexicographic Sequencing120

Algorithm NEXYTB122

(C)Random Selection123

Algorithm RANYTB127

Subroutine Specifications(NEXYTB)128

Subroutine Specifications (RANYTB)130

Sample Output131

PART 2 COMBINATORIAL STRUCTURES131

15 Sorting(HPSORT/EXHEAP)135

Algorithm ？(l,n)138

Algorithm TOHEAP138

Algorithm SORTHEAP139

Subroutine Specifications(HPSORT)140

Subroutine Specifications(EXHEAP)141

Sample Output142

16 The Cycle Structure of a Permutation(CYCLES)144

Algorithm TAG145

Algorithm INVERT146

Subroutine Specifications146

Sample Output148

17 Renumbering Rows and Columns of an Array(RENUMB)150

Algorithm RENUMB155

Subroutine Specifications155

Sample Output157

18 Spanning Forest of a Graph(SPANFO)158

(A)Introduction158

(B)Depth-First-Search160

Algorithm DEPTHFIRST161

(C)A Breadth-First Algorithm161

Algorithm LINK(x,∈,n,E)162

Algorithm VISIT(x,∈,n,E,q,l1,m1,a)164

Algorithm SCAN(x,∈,n,E,p,l0,m0,m,r)165

Algorithm COMPONENT(x,∈,n,E,p,k,L)165

Algorithm SPANFO(x,∈,n,E,k)166

Subroutine Specifications167

Sample Output169

19 Newton Forms of a Polynomial(POLY)171

Algorithm VALUE171

Algorithm NEWTON172

Algorithm TAYLOR173

Algorithm STIRLING174

Algorithm REVERSE STIRLING174

Algorithm NWT(m,x,∈,γ)175

Subroutine Specifications175

Sample Output177

20 Chromatic Polynomial of a Graph(CHROMP)178

Algorithm CHROMP182

Subroutine Specifications183

Sample Output185

21 Composition of Power Series(POWSER)187

Algorithm POWSER(Options 1,2,and 3)190

Algorithm POWSER(Option 4)191

Subroutine Specifications191

First Sample Output,Option 1193

Second Sample Output,Option 1194

Sample Output,Option 3194

Sample Output,Option 4195

22 Network Flows(NETFLO)196

Algorithm SWAP(i,j Option)203

Algorithm INIT203

Algorithm SORT203

Algorithm XREF204

Algorithm KZNET205

Algorithm PUSHOUT(p,P)206

Algorithm OLDFLOW(p)207

Algorithm PUSHBACK(p)207

Flow Chart PREFLOW208

Algorithm PREFLOW208

Algorithm NETFLO(n,E,∈,γ,source,sink,a,b,c,d,x)209

Subroutine Specifications209

Sample Output215

23 The Permanent Function(PERMAN)217

Computation of the Permanent Function220

Algorithm PERMAN223

Subroutine Specifications224

Sample Output225

24 Invert a Triangular Array(INVERT)226

Algorithm INVERT226

Subroutine Specifications227

25 Triangular Numbering in Partially Ordered Sets (TRIANG)228

Algorithm TRIANG230

Subroutine Specifications230

Sample Output231

26 The M？bius Function(MOBIUS)233

Subroutine Specifications237

Sample Output238

27 　The Backtrack Method(BACKTR)240

(A)General(BACKTR)240

Flow Chart BACKTR244

Subroutine Specifications245

(B)Coloring the Vertices of a Graph(COLVRT)246

Subroutine Specifications247

Sample Output248

(C)Euler Circuits(EULCRC)249

Algorithm EULCRC250

Subroutine Specifications250

Sample Output252

(D)Hamilton Circuits(HAMCRC)256

Subroutine Specifications257

Sample Output 1258

Sample Output 2260

(E)Spanning Trees(SPNTRE)262

Subroutine Specifications263

Sample Output264

28 Labeled Trees(LBLTRE)267

Algorithm LBLTRE271

Subroutine Specifications272

Sample Output273

29 Random Unlabeled Rooted Trees(RANRUT)274

Algorithm RANRUT279

Subroutine Specifications279

Sample Output281

30 Tree of Minimal Length(MINSPT)283

Algorithm MINSPT284

Subroutine Specifications285

Sample Output286

Exercises288

Bibliographic Notes294

Referenees296

Index299