# Combinatorial Algorithms

## 2nd Edition

### For Computers and Calculators

**Authors:**Albert Nijenhuis Herbert S. Wilf

**Editors:**Werner Rheinboldt

**eBook ISBN:**9781483273457

**Imprint:**Academic Press

**Published Date:**28th October 1978

**Page Count:**320

## 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.

## Table of Contents

Preface to Second Edition

Preface to First Edition

Introduction

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 Specifications

Part 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 Output

Part 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 Output

Exercises

Bibliographic Notes

References

Index

## Details

- No. of pages:
- 320

- Language:
- English

- Copyright:
- © Academic Press 1978

- Published:
- 28th October 1978

- Imprint:
- Academic Press

- eBook ISBN:
- 9781483273457