Combinatorial algorithms by Albert Nijenhuis and Herbert Wilf
1. Combinatorial algorithms (1975), by Albert Nijenhuis and Herbert S Wilf.
1.1 From the Preface.
Mathematical Reviews MR0396274 (53 #142).
Bull. Amer. Math. Soc. 82 (6) (1976), 870-871.
2. Combinatorial algorithms for computers and calculators (2nd edition) (1978), by Albert Nijenhuis and Herbert Wilf.
In the course of our combinatorial work over the past several years, we have been fond of going to the computer from time to time in order to see some examples of the things we were studying. We have built up a fairly extensive library of programs, and we feel that other might be interested in learning about the methods and/or use of the programs. This book is the result. It can be read as a collection of mathematical algorithms, and as such we hope the reader will find much that is new and interesting. Yet to do so would be to miss something that to us seems essential: the interchange between the computer programs per se, the computer, the algorithms, and ultimately the mathematics. To capture the complete spirit of this work, we urge the reader to study the programs themselves. The extra dimension that the computer and the mathematics bestow on each other is, we believe, worth the effort. Above all, we hope we have placed in the reader's hands a kit of building blocks with which the reader can construct more elaborate structures of his or her own.
1.2. Review by: Alon Itai.Mathematical Reviews MR0396274 (53 #142).
The main purpose of this book is to supply a set of FORTRAN subroutines for combinatorial algorithms in the spirit of numerical analysis packages. The subjects include the random and sequential production of subsets, permutations, compositions, partitions, etc.; graph algorithms - finding spanning forests, chromatic polynomials, coloring, random trees, minimal length spanning trees, Euler and Hamiltonian circuits, etc.; finding Möbius functions, the permanent, maximal flow, sorting and some theoretical subjects. Some important subjects are omitted, such as testing for planarity, tree and graph isomorphism, connectivity of a graph, maximum matching, etc. Each problem includes a theoretical background, an algorithm, a flowchart and a FORTRAN subroutine. The theoretical background is generally clear and concise. However, in some cases it is sketchy.
1.3. Review by: Earl Glen Whitehead, Jr.Bull. Amer. Math. Soc. 82 (6) (1976), 870-871.
Combinatorial algorithms are computational procedures which are designed to help solve combinatorial problems. Combinatorial problems are problems involving arrangements of elements from a finite set and selections from a finite set. These problems can be divided into three basic types: (1) enumeration problems, (2) existence problems, and (3) optimization problems. In enumeration problems the goal is either to find how many arrangements there are satisfying the given properties or to produce a list of arrangements satisfying the given properties. In existence problems the goal is to decide whether or not an arrangement exists satisfying the given properties. In optimization problems the goal is to find where a given function of several variables takes on an extreme value (maximum or minimum) over a given finite domain. Graph theoretic algorithms are included in the above definition of combinatorial algorithms. In this book Nijenhuis and Wilf discuss various combinatorial algorithms. ... At first glance Combinatorial algorithms may appear to be just a collection of over 30 algorithms. A more careful study of this book reveals that these algorithms may be placed into classes of similar algorithms. The largest class of algorithms contains those algorithms which generate a random combinatorial arrangement. ... Since Combinatorial algorithms by Nijenhuis and Wilf bridges the gap between computer science and mathematics, it should be included in both computer science libraries and mathematics libraries. This book can be used by readers interested in building a collection of combinatorial programs and by readers interested in studying the mathematics associated with the algorithms. Like a novel, this book may be read on several levels.
2.1. From the Preface.
SIAM Review 22 (2) (1980), 238-239.
American Scientist 67 (5) (1979), 620.
3. Combinatorial algorithms: an update (1989), by Herbert S Wilf.
Since the appearance of the first edition in 1975, the field of combinatorial algorithms has continued its rapid evolution. We have substantially rewritten several of the chapters in order to take account of theoretical or algorithmic improvements, and to clarify the presentation. The result has been that a number of speedups, storage economies, and program simplifications have been made, some significant new theoretical material such as that in the two new chapters (13 and 14) has been added, and some minor errors have been corrected.
2.2. From the Publisher.
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.
2.3. Review by: Earl Glen Whitehead, Jr.SIAM Review 22 (2) (1980), 238-239.
This book is suitable for a wide audience. Both computer scientists and mathematicians will find it interesting. The typical chapter includes the following features: (1) the mathematical background of the problem, (2) a formal algorithm for solving the problem, (3) an implementation of the algorithm as a FORTRAN subroutine, and (4) a sample output obtained by a computer run of the subroutine. Computer scientists will find the formal algorithms presented in a style similar to that used in computer science journal articles. Mathematicians will enjoy reading the background of these problems. All readers will find the FORTRAN subroutines useful in solving problems. ... I recommend this book to computer scientists and mathematicians. In fact, there are enough improvements in the second edition over the original 1975 edition, to recommend the purchase of the second edition by those readers who already own the original edition. I consider this book to be a valuable addition to my personal library.
2.4. Review by: Hale Freeman Trotter.American Scientist 67 (5) (1979), 620.
The form of this book is highly appropriate to its subject. Problems and their solutions are first discussed in mathematical terms, followed by formal algorithms with commentary for the solutions. Then FORTRAN subroutines are given, with the roles of all arguments and variables clearly stated. Almost half the book deals with generation of all combinatorial objects of a certain family, or of a random sample of them. The families range from the subsets of a given set (trivial to handle crudely, but admitting interesting refinements) to partitions and Young tableaux. The remaining portion of the book covers a variety of topics, several from network and graph theory, and includes a general discussion of backtrack methods. The programs will be immediately useful to anyone who has need of them. The mathematical sections can be read by themselves with pleasure. The well-organized combination of the two, however, is what gives the book its special value. The authors have provided convincing support for their belief that studying the interplay between computer programs, algorithms, and mathematics can illuminate all three.
3.1. Review by: Peter Eades.
Mathematical Reviews MR0993775 (90g:05002).
Mathematical Reviews MR0993775 (90g:05002).
This brief monograph is an update of the well-known 1978 book of Nijenhuis and Wilf on algorithms for listing and randomly selecting combinatorial objects such as permutations, combinations, and graphs. The "update" is almost entirely self-contained, and there are very few occasions when the reader needs to refer to the 1978 book. ... While the monograph does not pretend to be a comprehensive survey, the material covered is a fairly representative sample of the techniques currently available. The theorems and algorithms are all described in an intuitive yet precise manner, and the monograph would be an easy-to-read introduction to the area for any graduate student of mathematics or computer science.
JOC/EFR October 2016
The URL of this page is:
http://www-history.mcs.st-andrews.ac.uk/Extras/Combinatorial_algorithms.html