Combinatorial Algorithms for Computers and Calculators (Computer science and applied mathematics)

This book can be read at several levels. Those whose only need is to use one of the computer programs can turn immediately to those pages and satisfy their wants. Thus, on one level, this is a collection of subroutines, in FORTRAN, for the solution of combinatorial problems.At the other extreme, pure mathematicians with no need of computer programs will find much that is new and hopefully interesting in these pages. For example, in the special section Deus ex Machina (pp. 78-87), the random selection algorithms of Chapters 10, 12, and 29 are shown to be manifestations of a general phenomenon which sheds light on a number of seemingly unrelated threads of research in combinatorial analysis.Between these two extremes is a rapidly growing category of (frequently youthful) persons who have access to a fancy calculator (hand-held or table-top). They may not be interested in either the de tailed mathematics or the FORTRAN programs - yet we hope they will find much to stimulate them and help them prepare their own programs.Our hope, however, is that many readers will want to follow the entire road from general mathematics to particular mathematics to informal algorithm to formal algorithm to computer program and back again, which occurs in virtually every chapter of the book.Our other hope is that readers will view these methods and programs as a beginning set of building blocks for their own kit of tools and will go on to add to these tools to meet their own needs, so that the contents of this book will be not a collection of pretty artifacts to be looked at but basic elements of the growing and working equipment of scientific investigation and learning. 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.