Elements of Combinatorial Computing

Preface

Chapter 1 A Language for Combinatorial Computing


1.1 Fundamentals


1.1.1 Program Structure


1.1.2 Notation for Real Number Operations


1.1.3 Data-types and Arrays


1.1.4 Procedures


1.2 Set Manipulation


1.2.1 Notation for Sets


1.2.2 Operations


1.2.3 Functions Based on the Order of the Elements


1.3 Transfer of Control—Conditional Statements


1.3.1 Basic Statement Structure


1.3.2 Simple Conditions


1.3.3 Compound Conditions


1.3.4 Additional Forms


1.4 Notation for Iteration and Recursion


1.4.1 For-Statement Structure


1.4.2 Simple Range Specification and Generation Procedures


1.4.3 Auxiliary Transfer of Control Statements


1.4.4 Compound Range Specification


1.4.5 Notations Involving Iteration


1.5 Nested iteration and Recursive Programming


1.5.1 With-Statement Structure


1.5.2 Range Specification


1.5.3 Auxiliary Transfer of Control Statements


1.5.4 Recursive Operations

Chapter 2 Language Implementation and Program Efficiency


2.1 Data Representation


2.1.1 Single-Word Forms


2.1.2 Multiple-Word Forms


2.1.3 Storage Allocation


2.1.4 Toggles and Special Indicators


2.2 Operations


2.2.1 Shifting and Exponentiation


2.2.2 Modular Arithmetic


2.2.3 Counting and Locating 1-Bits


2.2.4 Functions


2.2.5 Control Language


2.3 Program Optimization


2.3.1 Precomputation


2.3.2 Specialization Versus Generalization


2.3.3 Use of Sophisticated Notations


2.4 System Organization—Procedures


2.4.1 Program Segmentation


2.4.2 Procedure Linkage


2.4.3 Compilation and Execution

Chapter 3 Computer Representation of Mathematical Objects


3.1 Natural Numbers


3.1.1 Positional Representation


3.1.2 Gray Codes


3.1.3 Residue Representation


3.1.4 Prime Factor Representation


3.1.5 Bit Parity of Multiples of Primes


3.2 Sets and Vectors


3.2.1 Unordered Sets—Masks


3.2.2 Unordered Sets as Ordered Lists—Binary Search


3.2.3 Signatures—Fractional Word Representation


3.2.4 Vectors and Polynomials Modulo 2


3.3 Elementary Combinatorial Configurations


3.3.1 Combinations and Permutations


3.3.2 Permutations as Transformations


3.3.3 Finite Groups


3.3.4 Compositions and Partitions of a Whole Number


3.3.5 Partitions of a Set


3.4 Linear Graphs and Networks


3.4.1 Definitions and Terminology


3.4.2 Representation by Incidence Matrices


3.4.3 Incidence Systems


3.4.4 Tree-Like Data Structures


3.5 The n-Cube


3.5.1 Graph-Theoretic Representation


3.5.2 Normal Form Expressions of Boolean Functions


3.5.3 Prime Implicants (Basic Cells)


3.6 Geometric Configurations


3.6.1 Polyominoes


3.6.2 Chessboard Models

Chapter 4 Search and Enumeration—Backtrack Programming


4.1 Introduction to Backtrack Programming—The Search Tree


4.1.1 Elementary Signature Generation


4.1.2 Normal Tree Scan and Basic Program Structure


4.1.3 Notational Variants


4.2 Basic Backtracking and Impasse Detection


4.2.1 Graph Coloring


4.2.2 Anticipated Impasse Detection


4.2.3 Search Rearrangement


4.2.4 Hamiltonian Path Generation


4.3 Optimization Backtracking


4.3.1 Branch and Bound—The Traveling Salesman Problem


4.3.2 The Algorithm of Little, Murty, Sweeney, and Karel


4.3.3 Min-Max Optimization—Computer Chess


4.3.4 Local Optima by Method-of-Ascent


4.3.5 More Refined Approximation


4.4 Branch Merging


4.4.1 The Cut-Off and Tier Scans


4.4.2 Permanent Evaluation


4.4.3 Dynamic Programming Approach to Optimization


4.4.4 Enumeration by Branch Merging

Chapter 5 Generation of Elementary Configurations


5.1 Subsets and Combinations


5.1.1 Generation of All Subsets


5.1.2 r-Subsets—Combinations of Distinct Objects


5.1.3 Serial Numbers and Ranking of Combinations


5.2 Permutations of Distinct Objects


5.2.1 Lexicographic Generation and Serial Numbers


5.2.2 Generation by Transposition


5.2.3 Generation by Adjacent Transposition


5.2.4 Permutations Consistent with a Partial Ordering


5.3 Permutations with Repeated Objects


5.3.1 Lexicographic Generation


5.3.2 Serial Number Calculation


5.4 Compositions


5.4.1 Relationship with Subsets—Serial Numbers


5.4.2 Generation in Signature Form


5.4.3 Compositions as Permutations of Partitions


5.5 Partitions


5.5.1 Numerical Partitions in Signature Form


5.5.2 Serial Numbers for Numerical Partitions


5.5.3 Partitions of a Set


5.5.4 Binary Trees—Partitions Without Crossing

Chapter 6 Additional Basic Techniques and Manipulations


6.1 Sieving Processes


6.1.1 Modular Sieves


6.1.2 Isomorph Rejection by Sieve


6.1.3 Further Examples of Recursive Sieving


6.2 Sorting Techniques


6.2.1 Pigeonholing—Sort by Address Calculation


6.2.2 Merge-Exchange Sorting—Shell's Method


6.2.3 The Sort Permutation


6.3 Procedures Concerned with Connectedness


6.3.1 The Connectivity Matrix—WarshalVs Method


6.3.2 Sequential Generation of Components


6.3.3 Consistency Determination (Cycle Detection)


6.4 Finite Set Covering


6.4.1 The Basic Branching Algorithm


6.4.2 Disjoint Covers—Steiner Triple Systems


6.4.3 Irredundant Covers


6.4.4 Other Program Refinements


6.5 Transformations


6.5.1 Matrix Translation and Transposition


6.5.2 Symmetries of the Square—The Dihedral Groups


6.5.3 Permutation Group Generation


6.6 Isomorph Rejection


6.6.1 A Typical Problem—Basic Program Structures


6.6.2 Direct Comparison


6.6.3 The Indirect Comparison Approach

Chapter 7 Applications—Advanced Algorithms


7.1 Incidence Matrix Equivalence


7.1.1 Invariants


7.1.2 An Equivalence Algorithm


7.1.3 Reduced Latin Square Enumeration


7.2 The Steinhaus Sorting Problem


7.2.1 The Ford-Johnson Algorithm


7.2.2 Enumeration ofPoset Consistent Permutations—Discussion


7.2.3 The Enumeration Program


7.2.4 Computer Study of the Case n = 12


7.3 A Computer Study of the Four-Color Problem


7.3.1 Elementary Kempe Reductions


7.3.2 A General Approach to Reducibility Testing


7.3.3 Tractable Circuit Colorations


7.3.4 Contractions


7.4 Parker's Orthogonal Latin Square Generation


7.5 Simplification of Normal Form Boolean Expressions

Appendix I Tables of Important Numbers

I.1 Powers of 2; Factorials; Bell Numbers; Segner Numbers

I.2 Binomial Coefficients

I.3 Stirling Numbers of Second Kind

I.4 Number of Partitions of n into Parts ≤ m

I.5 Prime Numbers < 1000 (by Bit-Pattern)

Appendix II Tables of Interesting Numbers

II.1 Excess Number of Multiples ( < 2n)of p with Even 1-bit Parity

II.2 Number of Solutions to Queens' Problem

II.3 Folding Numbers

II.4 Answers to a Distribution Problem for n = 5

II.5 Number of Reduced Latin Squares

II.6 Number of Zero-One Matrices with Vanishing Permanent

II.7 Spectra of Determinant Magnitudes for Zero-One Matrices

Appendix III Compendium of Four-Color Reducible Configurations

Bibliography

Index