Combinatorial Algorithms

Combinatorial Algorithms

For Computers and Calculators

2nd Edition - October 28, 1978

Write a review

  • Authors: Albert Nijenhuis, Herbert S. Wilf
  • eBook ISBN: 9781483273457

Purchase options

Purchase options
DRM-free (PDF)
Sales tax will be calculated at check-out

Institutional Subscription

Free Global Shipping
No minimum order

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

Product details

  • No. of pages: 320
  • Language: English
  • Copyright: © Academic Press 1978
  • Published: October 28, 1978
  • Imprint: Academic Press
  • eBook ISBN: 9781483273457

About the Authors

Albert Nijenhuis

Herbert S. Wilf

About the Editor

Werner Rheinboldt

Ratings and Reviews

Write a review

Latest reviews

(Total rating for all reviews)

  • Sumit K. Fri Apr 20 2018

    Wonderful

    Covers everything