MARK BGWEM
`
`
`
`Oracle-
`
`1025 p. 1
`Oracle v. Teleputers
`|PR2021-00078
`
`Oracle-1025 p. 1
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`ELEMENTS OF
`COMBINATORIAL
`COMPUTING
`
`MARK B. WELLS
`Computer Science Research Group
`Leader, Los Alamos Scientific
`Laboratory of the University of
`California
`
`The field of combinatorial computing
`is a relatively new one and this book
`represents one of the first attempts
`to consolidate many of the scattered
`methods of discrete computing. Its
`primary purpose is to supply the
`elementary concepts and procedures
`required for combinatorial computing.
`Fundamental digital computer
`algorithms for manipulating
`combinatorial objects such as
`permutations, partitions and linear
`graphs are presented and discussed.
`The techniques examined range from
`counting I-bits and binary search
`through backtrack programming to
`sieving processes and isomorph
`rejection. Several examples of the
`incorporation of the basic
`algorithms in involved combinatorial
`investigations are also included. The
`most significant special aspect of the
`work is the emphasis on algorithmic
`structure and the unification of
`particular jobs into general combinatorial
`processes. This approach
`helps the reader to modify existing
`algorithms and construct his own
`combinatorial procedures. Two
`underlying goals of the book are to
`introduce the pure mathematician to
`the possibilities of high-speed
`computation, and to point out to the
`computer scientist some of the needs
`of the research mathematician.
`The book will be of use to
`honours degree and first year
`graduate students of computer
`science and mathematics, computer
`programmers in industry, and to
`mathematicians interested in the
`computer as a tool. It will also be a
`valuable supplementary text for
`courses in combinatorial theory,
`numerical methods or computational
`algorithms.
`
`Oracle-1025 p. 2
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`ELEMENTS OF
`COMBINATORIAL COMPUTING
`
`Oracle-1025 p. 3
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`To my parents a!J,d my MARvellous harem
`
`Oracle-1025 p. 4
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`ELEMENTS OF
`COMBINATORIAL COMPUTING
`
`BY
`MARK B. WELLS .
`Computer Science Research Group Leader, Los Alamos Scientific Laboratory(cid:173)
`of the University California, Los Alamos, New Mexico 87544
`
`PERGAMON PRESS
`OXFORD , NEW YORK
`TORONTO . SYDNEY , BRAUNSCHWBIG
`
`Oracle-1025 p. 5
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`Pergamon Press Ltd., Headington Hill Hall, Oxford
`Pergamon Press Inc., Maxwell House, Fairview Park, Elmsford,
`New York 10523
`Pergamon pf Canada Ltd., !).07 ·Queen's Quay West, Toronto 1
`Pergamon Press (Aust.) Pty. 'Ltd., 19a Boundary Street,
`Rushcut~rs Bay, N.S.W. 2011, Australia
`Vieweg & Sohn 'GmbH, Burgplatz 1, Braunschweig
`Copyright© 1971 Pergamon Press Inc.
`All Rights Reserved. No part of this publication may be
`reproduced, stored in a retrieval system, or transmitted, in any
`form or by any means, ~lectronic, mechanical, photocopying,
`recording or· ·otherwise, without the prior permission of
`Pergamon Press Inc.
`First edition 1971
`Library of Congress Catalog Card No. 77-129633
`
`Printed in Hungary
`
`08 0160913
`
`Oracle-1025 p. 6
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`CONTENTS
`
`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/or 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
`
`V
`
`xi
`
`1
`
`2
`2
`4
`6
`7
`
`9
`10
`11
`11
`
`13
`13
`14
`15
`16
`
`18
`18
`19
`22
`23
`24
`
`27
`28
`29
`33
`33
`
`I
`37
`
`38
`38
`39
`40
`42
`
`Oracle-1025 p. 7
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`VI
`
`CONTENTS
`
`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
`Incidence Systems
`3.4.3
`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
`
`44
`44
`45
`45
`47
`48
`
`49
`50
`51
`52
`
`53
`53
`54
`56
`
`58
`
`58
`59
`60
`61
`62
`62
`
`64
`65
`65
`67
`67
`
`70
`70
`71
`72
`74
`76
`
`78
`78
`79
`81
`81
`
`85
`85
`86
`87
`
`89
`89
`90
`
`Oracle-1025 p. 8
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`CONTENTS
`
`Chapter 4 Search and Enumeration-Backtrack Programming
`Introduction to Backtrack Programming-The Search Tree
`4.1
`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
`
`vii
`
`93
`93
`94
`96
`97
`
`100
`100
`101
`103
`104
`
`107
`107
`109
`113
`115
`116
`
`118
`119
`121
`122
`124
`
`127
`
`127
`127
`129
`130
`
`134
`135
`137
`138
`140
`
`143
`143
`145
`
`146
`147
`148
`149
`
`150
`150
`151
`152
`154
`
`Oracle-1025 p. 9
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`vw
`
`CONTENTS
`
`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-Warshall's 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
`lrredundant Covers
`6.4.3
`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
`1.1
`Incidence Matrix Equivalence
`Invariants
`7.1.1
`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 of Poset Consistent Permutations-Discussion
`7.2.3 The Enumeration Program
`7.2.4 Computer Study of the Cafe n = 12
`
`1.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
`
`158
`158
`158
`160
`161
`
`164
`164
`166
`167
`
`169
`170
`171
`173
`
`175
`176
`178
`179
`181
`
`185
`185
`187
`189
`
`190
`191
`192
`193
`
`198
`198
`198
`200
`203
`
`206
`207
`209
`211
`213
`
`215
`215
`218
`221
`224
`
`Oracle-1025 p. 10
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`1.4 Parker's Orthogonal Latin Square Generation
`1.5 Simplification of Normal Form Boolean Expressions
`
`CONTENTS
`
`Appendix 1 Tables of Important Numbers
`1.1 Powers of2; Factorials; Bell Numbers; Segner Numbers
`1.2 Binomial Coefficients
`1.3 Stirling Numbers of Second Kind
`1.4 Number of Partitions of n into Parts .,.; m
`1.5 Prime Numbers < 1000 (by bit-pattern)
`
`Appendix II Tables of Interesting Numbers
`11.1 Excess Number of Multiples ( < 2") of p with Even 1-bit Parity
`11.2 Number of Solutions to Queens' Problem
`11.3 Folding Numbers
`11.4 Answers to a Distribution Problem for n = 5
`11.5 Number of Reduced Latin Squares
`11.6 Number of Zero-One Matrices with Vanishing Permanent
`11.7 Spectra of Determinant Magnitudes for Zero-One Matrices
`
`Appendix III Compendium of Four-color Reducible Configurations
`
`BIBLIOGRAPHY
`
`INDEX
`
`227
`229
`
`233
`233
`234
`235
`234
`236
`
`237
`237
`238
`238
`239
`240
`240
`241
`
`242
`
`243
`
`251
`
`Oracle-1025 p. 11
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`PREFACE
`
`THE development of high-speed computing over the past two decades has had an extra(cid:173)
`ordinary impact upon the scientific community. At first, this "computer revolution"
`most strongly influenced, and was influenced by, physicists, engineers, numerical ana(cid:173)
`lysts, and other applied scientists interested in performing arithmetic calculations to
`obtain numerical answers to their problems. However, the versatility of the electronic
`computer, its ability (crude and unplanned though it was and generally still is) to per(cid:173)
`form nonarithmetic manipulations, soon stimulated interest among "pure" mathemati(cid:173)
`cians-primarily, number theorists and algebraists-and among scientists of less numeri(cid:173)
`cally oriented disciplines such as operations research and linguistics. At present, "non(cid:173)
`numerical computing"-computing in which the basic operations are nonarithmetic
`(e.g. logical, set-theoretic, symbol manipulative) and in which classical numerical analysis
`plays, if at all, a minor role-is gaining in importance. This book is about one aspect of
`nonnumerical computing: the high-speed manipulation (e.g. generation, covering,
`comparison) of combinatorial objects such as permutations, partitions, and linear
`graphs.
`There is, of course, a close kinship between this combinatorial computing and combina(cid:173)
`torial mathematics. In fact, most of the methods and examples appearing in this book are
`taken from the study of problems in combinatorial theory. Nevertheless, there is impor(cid:173)
`tant interaction between such computing and other disciplines. The techniques presented
`here find application in the fields of number theory, algebra, switching theory, biomathe(cid:173)
`matics, game theory, and operations research, as well as combinatorics.
`The primary purpose of this book is to bring together under one cover the basic and
`important computer methods of solving problems which involve the handling of combi(cid:173)
`natorial entities (more generally, of finite sets). Moreover, we wish to assist the reader in
`gaining facility for constructing combinatorial algorithms of his own design. Thus
`special attention is given to the structure of the algorithm, why they work, and how they
`may be altered to accomplish similar but distinct tasks. Of course, we also hope that
`this book will be a source of ideas for workers in combinatorics and computer science.
`Two underlying goals of this book are to introduce the pure mathematician to the possi(cid:173)
`bilities of high-speed computation, and to point out to the computer scientist some of
`the needs of the research mathematician.
`With regard to these objectives, the language used for describing the algorithms is of
`central importance; and there are several considerations in choosing an algorithmic
`
`xi
`
`Oracle-1025 p. 12
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`X11
`
`PREFACE
`
`language. Firstly, the language should be natural, i.e., it should be readable and reason(cid:173)
`ably concise, using established mathematical notation as much as possible. Use of an
`uncontrived, not altogether foreign, language simplifies and enhances understanding of
`the algorithms and eases the task of their modification. Secondly, the language should
`have a degree of sophistication which allows suppression of detail inessential to concep(cid:173)
`tual understanding of the processes. Certainly a user should not be required to repeat in
`detail the thought processes previously followed by other qualified algorithmists or
`computer designers. Finally, it is desirable to have the algorithmic language serve as the
`programming language, i.e., to have facilities available for the automatic translation
`of the algorithms into "absolute code" for a particular computer. This, of course,
`greatly shortens the time from problem conception to the production of useful results.
`(This capability should play a subordinate role in the design of the algorithmic language,
`however.)
`Algorithms are presented in this book in a language especially designed for combina(cid:173)
`torial computing. This language is both more natural and more sophisticated than the
`common programming languages Fortran and Algol. Also, most of its features have
`indeed been implemented-as part of the programming language Madcap for the Maniac
`II computer in Los Alamos. The language and its implementation are discussed in
`Chapters 1 and 2. Chapter 3 is both an introduction to combinatorial terminology and to
`data representation within a computer. The serious discussion of algorithms and their
`structure begins with Chapter 4. An attempt has been made to use notations from the
`language in textual descriptions of the algorithms as well as in the programs which
`implement the algorithms.
`Translation from the notation of this book to a programming language available
`on a specific computer should cause little difficulty, particularly if certain basic non(cid:173)
`numerical operations such as logical or, logical and, shifting, and counting I-bits are
`readily programmable for that machine. To simplify this translation, care has been
`taken to define sophisticated notations in terms of previously defined, more elementary
`notations which closely resemble familiar Fortran and Algol statements.
`Actually, sophistication is a relative matter. The science of computing and its lan(cid:173)
`guage of presentation, like mathematics, grows in steps, the methods and notation at one
`level being the building blocks for higher order methods and notation. With the tech(cid:173)
`niques and language presented here, we attempt to take but the first step in the founding
`of a science of combinatorial computing-the use of the word "elements" in the title of
`this book is certainly appropriate. We hope, however, to have achieved a unification of
`many of the basic concepts which can easily lead to more advanced methods and nota(cid:173)
`tions for combinatorial computing.
`This book is intended primarily for mathematically trained individuals interested in
`the use of high-speed digital computers for obtaining "answers" (counter-examples and
`heuristic data perhaps more so than final results) to combinatorial problems. Beyond
`basic mathematical training-finite set theory and the elements of algebra and number
`theory (number systems, groups, congruences, etc.)-this book presupposes only a grasp
`
`Oracle-1025 p. 13
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`PREFACE
`
`X lJ l
`
`of the concept of algorithmic computing. Actually, much computer and combinatorial
`terminology with which a person with this training could be expected to be familiar is
`herein explained anew. Just as the numerical analyst finds it necessary to employ differ(cid:173)
`ence equations when seeking help from a digital computer, the combinatorial analyst
`also finds it necessary to return to fundamentals for preparation of his computer programs.
`The fundamentals here, with which it is assumed the reader has facility, are the principle
`of induction (more precisely, the concept of recursive definition) and the logical rule-of(cid:173)
`sum and rule-of-product (in a set-theoretic language, these are An B = O implies
`IAUBI = IAl+IBI and IAXBI = IAI-IBI, respectively). However, let the reader be
`warned that the elementary nature of the tools does not necessarily imply simplicity
`of the structures built with them. Many combinatorial algorithms are extremely com(cid:173)
`plicated, and their mastery involves much plain hard work.
`Discussion of the algorithms is for the most part casual; formal proofs are not in(cid:173)
`cluded. Nevertheless, this book is appropriate as a supplementary textbook for an upper
`class or graduate course in combinatorial theory, computing, or numerical analysis.
`(In this respect it should be noted that the order of Chapters 4, 5, and 6 is somewhat
`arbitrary, as is the order of the major sections in Chapters 6 and 7.) Of course, this book
`could also be used as a basis for a course entitled, say, Introduction to Discrete Comput(cid:173)
`ing; although, for such an endeavor to be truly successful, an implementation of the
`language should be available to the student. t Indeed, it is our hope that many of the
`language features used here will some day be incorporated into a generally available
`programming language.
`The exercises at the end of each major section are considered an integral part of the
`text. They should be read, even though not solved, since besides practice problems they
`contain definition of terminology, discussion of alternate methods and useful modifica(cid:173)
`tions, and suggestions for further research. Some of the programming exercises antici(cid:173)
`pate later discussion; hence their answers appear in the text. Most problems, however,
`are best pursued by actual computer experience. Answers to a few of these problems
`appear in Appendix II as tables calculated by the author. Asterisks are used to mark
`more difficult exercises, those which might better be called projects.
`The single bibliography at the end of the book is organized by chapter. It contains
`suggestions for further reading as well as cited references. Many of the works are listed
`by virtue of their expository character and the extensive bibliographies which they
`contain.
`All of the procedures presented in this book have been tested on the Maniac II com-
`
`t The author, as a Visiting Professor, used the manuscript of this book for a senior level course·
`.under the Department of Mathematical Sciences at Rice University, Houston, Texas, during the
`spring semester 1970. Translation to Burroughs Compatible Algol for the B5500 computer at Rice
`was annoying but not difficult.
`There is somewhat more material in this text than can be covered in one semester. A full year's
`course entitled "Combinatorics and Computing" could be fashioned from this book by introducing
`certain concepts of theoretical combinatorial analysis (e.g. generating functions, inclusion-exclusion>
`Polya enumeration) at appropriate points in the presentation.
`
`Oracle-1025 p. 14
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`xiv
`
`PREFACE
`
`puter at the University of California Los Alamos Scientific Laboratory, Los Alamos, New
`Mexico. However, since there is still the possibility of inaccuracies due to debugging
`oversights, language ambiguities, or other errors, the reader is advised to take nothing
`for granted.
`Many people have assisted me in diverse ways in the preparation of this work.
`First, I would like to thank the administration of the Los Alamos Scientific Laboratory
`for allowing me to undertake this project under their sponsorship. Discussions with
`Stanislaw Ulam, Roger Lazarus, Paul Stein, Robert Bivins, Nicholas Metropolis,
`Myron Stein, Marvin Wunderlich, Robert Korfhage, Donald Knuth, and Robert
`Floyd influenced this work. Particular thanks are due to Robert Bivins, Roger Lazarus,
`Nicholas Metropolis, and Paul Stein for their constructive comments upon reading the
`manuscript. I am indebted to Verna Gardiner for debugging assistance and to Donald
`Bradford for his patient help with the language development as well as for debugging
`assistance. The final manuscript was expertly typed by Margery McCormick and Dorothy
`Camillo. I also wish to thank Fred Cornwell, Jay London, and Jane Rasmussen for
`their clerical support. Finally, along a somewhat different vein, I would like to acknowl(cid:173)
`edge two especial debts-to Professor S. tnam for his continued stimulation of my work
`and to Professor D. H. Lehmer whose commonsense approach to mathematics and
`computing has always been an inspiration to me.
`This work was performed under the auspices of the United States Atomic Energy
`Commission.
`
`Oracle-1025 p. 15
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`CHAPTER 3
`
`COMPUTER REPRESENTATION
`OF MATHEMATICAL OBJECTS
`
`FROM a "physical" problem which a computer is to solve one must first erect a model
`-a representation of pertinent entities-in a form comprehensible to the computer.
`This is often a two-step process: first a mathematical model for the physical problem
`(e.g. a linear graph as a model for a city street plan) is derived and then a computer
`representation for the mathematical object (e.g. a 2-array of zeros and ones as a repre(cid:173)
`sentation for the graph) is constructed. We are primarily concerned here with the second
`step, with constructing computer representations of mathematical objects. In this
`respect, this chapter can be considered an extension of§ 2.1. It serves as an introduction
`to the applications appearing in this book and in the literature. Also, for those less famil(cid:173)
`iar with combinatorial mathematics, it may serve as an introduction to basic combina(cid:173)
`torial terminology.
`It should be noted that the proper choice of a model depends heavily upon the indi(cid:173)
`vidual computer system as well as upon particular features of an intended study. Also,
`generally speaking, the more compact the representation, the more difficult it is to extract
`the usable information-a happy medium should be found for each problem. Thus we
`often present alternative representations. However, as discussed in Chapter 2, our
`representations (and resulting algorithms) are indeed biased toward systems with con(cid:173)
`venient bit-manipulative facilities.
`
`3.1. Natural Numbers
`
`Basic to combinatorial computing are the positive and negative integers and zero.
`In many number-theoretic investigations these numbers themselves are the primary
`objects of study. In other combinatorial studies these numbers serve either to label or to
`count various discrete objects under consideration. Actually, the negative integers are
`seldom needed-the natural numbers 0, 1, 2, ... serve nicely as both indices (labels)
`and tallies (counts). This section discusses the common and useful representations for
`the natural numbers.
`We should point out that for clarity of textual presentation it is often necessary to use
`
`S8
`
`Oracle-1025 p. 16
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`COMPUTER REPRESENTATION OF MATHEMATICAL OBJECTS
`
`59
`
`nonnumeric labels such as a, b, c, ... , or v1, v2, v3 •••• However, this does not imply
`their use within the computer. In fact, our language and algorithms rely significantly on
`the representation of labels as natural numbers.
`
`3.1.1. Positional Representation
`
`The most important representation of a natural number is by means of the conven(cid:173)
`tional positional notation. For a fixed integer B, B ➔ 2, the base or radix, and arbitrarily
`large integer n, each natural number N less than Bn may be represented by an ordered set
`of "digits" d0, d1, • ; ., dn-l defined by the expansion
`
`(3.1)
`
`where each d;, i = 0 to n -1, satisfies the inequality
`0..;;; d1 < B
`to insure that the representation is unique. For B = 10 (writing the digits in order
`dn_ 1dn_ 2 ••• d0 and omitting leftmost zeros) this is the conventional decimal notation.
`For B = 2 this is the common binary system of representation used by most high-speed
`digital computers.
`It is occasionally advantageous to express numbers relative to a base different from
`that used in the accordant hardware representation-the standard representation. Such
`representations may be formed "from scratch" using programmed operations (see
`· §§ 4.1 and 5.1) or may be derived by conversion from the existing numbers in standard
`representation. The conversion may be accomplished from either end, i.e. the new
`digits may be calculated in order d0, di, ... , dn-l• or in order dn_ 1, dn_ 2, ••• , d0 • The
`former is achieved by successively dividing firstN, and then each resulting quotient, by B;
`the resulting remainders provide the digits. That is, % = N, q1 = d;+q;+1B for i = 0
`to n - I. The latter sequence is formed by dividing N by Bn-1, the resulting remainder
`, and so forth; the resulting quotients provide the digits. That is, 'n-i = N,
`by Bn- 2
`r; = r;_ 1 +d;B for i = n-1, n-2, ... , 0. Computing the digits in ascending order of
`subscript is slightly more efficient as the process may be terminated when a zero quotient
`appears, while for the descending process, since we begin with a sufficiently large n so
`that N < Bn, several zero digits may be inadvertently computed.
`This descending conversion, however, which is given in Fig. 3.1, is perhaps more
`useful in representations closely related to the positional model just discussed. An
`
`C.l
`C.2
`
`C.3
`
`C.4
`
`r=N
`for i = n - I, n -2, ... , 1 :
`.
`r
`define d;, r by Bi "r (old) = r (new)+d;B'"
`
`do= r
`Fm. 3.1. (Descending) conversion to radix B.
`
`Oracle-1025 p. 17
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`60
`
`ELEMENTS OF COMBINATORIAL COMPUTING
`
`important representation of this type is the so-called factorial representation where each
`N, N < n! (n an arbitrary positive integer) is given by an ordered set of factorial digits
`a1, a2, ••• , an-i defined by the expansion
`
`(3.2)
`where each a;, i = I to n -1 (a0 = 0 is sometimes introduced) satisfies the inequality
`(3.3)
`
`to insure that the representation is unique. Only minor modifications of the conversion
`of Fig. 3.1-replacing B1 of line C.3 by i! and shortening the iteration by one-are
`needed to enable it to calculate the factorial digits associated with a given natural number
`N (see§ 5.2).
`
`3.1.2. Gray Codes
`
`A Gray code [162] is a function of the numbers 0, I, ... , 2n- 1 onto themselves
`(i.e. a permutation) such that the images of successive numbers differ at a single-bit
`position in their binary representation. For example, 0, 1, 3, 2 (or in binary 00, 01, 11, 10)
`is a Gray code for 0, I, 2, 3. For arbitrary n, many distinct Gray codes exist (in fact,
`the exact number is unknown for n .,.,. 5-see § 4.2.4). Given a Gray code, the Gray code
`representation of N _is the image of N under the code.
`A particular Gray code, of interest because of its simplicity, is defined as follows:
`Let n be an arbitrary positive integer. Let b0, b1, • • • , bn-i be the binary digits of a
`natural number N, N < 2n, in the standard positional representation. Consider the
`representation g0, g1, ••• , gn-l• where gi E {O, 1} and
`gi = h1 !lb1+1, j = 0 to n-1, bn = 0.
`(Symmetric subtraction of bits is mentioned in§ 1.2.2.) For this to be a Gray code, the
`representation of g;, g;, ... , g;_ 1 for N+ I must differ from g0 , g1 , ••• , gn-i in
`precisely one place, i.e. there must exist a k such that gz ~ gk, and g7 = g1 for i ~ k.
`Indeed, let k be the smallest index for which bk = 0 (i.e. when one is added to N, "carry(cid:173)
`propagation" reaches just to position k). Now bits 'b;, b;, ... , b: of N + 1 are comple(cid:173)
`ments of b0, b1, ••• , bk and thus g1* = g1 for j = 0 to k -1. Since hZ+i = bk+i and
`hZ ~ bk, we have gz ~ Kk• Furthermore, since none of the bits beyond bk were changed
`by addition of one to N (i.e. b; = b1 for j = k + I to n -1 ), we have g; = g1 for
`j = k+ 1 to n-1. Therefore, (3.4) does define a Gray code. Note further that gz equals
`0 or 1 according as bk+i equals 1 or O respectively.
`To express Nin conventional binary given its Gray code representation Ko, K1, •.. ,
`Kn-i as defined above, the inverse of (3.4) may be employed, namely
`
`(3.4)
`
`(3.5)
`
`Further discussion of this particular Gray code appears in§ 5.1. The generation of other
`Gray codes is treated in§ 4.2.4.
`
`Oracle-1025 p. 18
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`COMPUTER REPRESENTATION OF MATHEMATICAL OBJECTS
`
`61
`
`3.1.3. Residue Representation
`Let m1, m2, ••• , mn be n positive integers relatively prime in pairs and let M =
`Tii=l to nCmi). That each number N less than Mis uniquely determined by its n least positive
`residues modulo mi, j = 1 to n, is a well-known number-theoretic result. The represen(cid:173)
`tation of N by these residues r1, r2, ... , rn is called the residue (or Chinese or modular)
`representation.
`If N is represented in this fashion by the I-array (r 1,r 2, ••• ,r J and N* by (r;,
`r;, .. . ,r;), then it follows from the elementary rules of modular arithmetic that N+N*
`is represented by
`
`(r1 +ri (mod m1), ... ,rn+r! (mod mn))
`and NN* is represented by
`
`(r1ri (mod m1), ... ,rnr! (mod mn)).
`
`The independence of the r's in these calculations has aroused some interest among com(cid:173)
`puter designers although no actual hardware implementation seems to have appeared
`(but see Szabo and Tanaka [97]).
`The conversion from residue to standard representation, often required in number(cid:173)
`theoretic calculations, may be accomplished by means of the venerable Chinese remainder
`theorem [34]. This says that
`
`N = Lt=l to n(r,b, !) (mod M),
`whereb1is some integer such thatb1(M/m1)-1 is amultipleofm1(i.e.btCM/m1) = 1 (mod
`m,)). The existence of each b1 is insured by the pairwise relative primeness of the m's
`which makes m1 and M/m1 relatively prime. A naive, yet often satisfactory, method of
`l until the correct one is
`determining b; is simply to try each of the values I, 2, ... , m1-
`found. For example, the function
`B.O
`inverse(c,m)
`inverse()= [firstj = 1 to m-1 ')jc = 1 (modm)]
`B.1
`would produce b1 when applied to M/m1 and m1 as arguments. More sophisticated
`means of determining b1 are pursued in the exercises. In any event, given n, the vectots
`m1 ton and r1 ton• and a procedure, say inverse( ), for calculating each b1, the formula
`(3.6) may be evaluated directly-by use of the program
`M = Tii=l to n(mi)
`N = Li=l to n(r, :, inverse(:, ,m,)) (mod M)
`
`(3.6)
`
`(3.7)
`
`f