Matters Computional - Ideas, Algorithms, Source code - J.Arndt.pdf

(5305 KB) Pobierz
Matters Computational
Matters Computational
Ideas, Algorithms, Source Code
JorgArndt
ii
CONTENTS
iii
Contents
Preface
xi
I Low level algorithms
1
1 Bit wizardry 2
1.1 Trivia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Operations on individual bits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.3 Operations on low bits or blocks of a word . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.4 Extraction of ones, zeros, or blocks near transitions . . . . . . . . . . . . . . . . . . . . . 11
1.5 Computing the index of a single set bit . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.6 Operations on high bits or blocks of a word . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.7 Functions related to the base-2 logarithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.8 Counting the bits and blocks of a word . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.9 Words as bitsets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
1.10 Index of the i-th set bit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
1.11 Avoiding branches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
1.12 Bit-wise rotation of a word . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
1.13 Binary necklaces z . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
1.14 Reversing the bits of a word . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
1.15 Bit-wise zip . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
1.16 Gray code and parity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
1.17 Bit sequency z . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
1.18 Powers of the Gray code z . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
1.19 Invertible transforms on words z . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
1.20 Scanning for zero bytes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
1.21 Inverse and square root modulo 2 n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
1.22 Radix 2 (minus two) representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
1.23 A sparse signed binary representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
1.24 Generating bit combinations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
1.25 Generating bit subsets of a given word . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
1.26 Binary words in lexicographic order for subsets . . . . . . . . . . . . . . . . . . . . . . . . 70
1.27 Fibonacci words z . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
1.28 Binary words and parentheses strings z . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
1.29 Permutations via primitives z . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
1.30 CPU instructions often missed . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
1.31 Some space lling curves z . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
2 Permutations and their operations 102
2.1 Basic denitions and operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
2.2 Representation as disjoint cycles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
2.3 Compositions of permutations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
453316713.001.png
iv
CONTENTS
2.4 In-place methods to apply permutations to data . . . . . . . . . . . . . . . . . . . . . . . 109
2.5 Random permutations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
2.6 The revbin permutation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
2.7 The radix permutation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
2.8 In-place matrix transposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
2.9 Rotation by triple reversal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
2.10 The zip permutation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
2.11 The XOR permutation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
2.12 The Gray permutation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
2.13 The reversed Gray permutation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
3 Sorting and searching 134
3.1 Sorting algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
3.2 Binary search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
3.3 Variants of sorting methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
3.4 Searching in unsorted arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
3.5 Determination of equivalence classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148
4 Data structures 153
4.1 Stack (LIFO) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
4.2 Ring buer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
4.3 Queue (FIFO) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156
4.4 Deque (double-ended queue) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158
4.5 Heap and priority queue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160
4.6 Bit-array . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
4.7 Left-right array . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166
II Combinatorial generation
171
5 Conventions and considerations 172
5.1 Representations and orders . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172
5.2 Ranking, unranking, and counting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172
5.3 Characteristics of the algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173
5.4 Optimization techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174
5.5 Implementations, demo-programs, and timings . . . . . . . . . . . . . . . . . . . . . . . . 174
6 Combinations 176
6.1 Binomial coecients . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176
6.2 Lexicographic and co-lexicographic order . . . . . . . . . . . . . . . . . . . . . . . . . . . 177
6.3 Order by prex shifts (cool-lex) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180
6.4 Minimal-change order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182
6.5 The Eades-McKay strong minimal-change order . . . . . . . . . . . . . . . . . . . . . . . 183
6.6 Two-close orderings via endo/enup moves . . . . . . . . . . . . . . . . . . . . . . . . . . . 186
6.7 Recursive generation of certain orderings . . . . . . . . . . . . . . . . . . . . . . . . . . . 191
7 Compositions 194
7.1 Co-lexicographic order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194
7.2 Co-lexicographic order for compositions into exactly k parts . . . . . . . . . . . . . . . . 196
7.3 Compositions and combinations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198
7.4 Minimal-change orders . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199
8 Subsets 202
8.1 Lexicographic order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202
8.2 Minimal-change order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204
453316713.002.png
CONTENTS
v
8.3 Ordering with De Bruijn sequences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208
8.4 Shifts-order for subsets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208
8.5 k-subsets where k lies in a given range . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210
9 Mixed radix numbers 217
9.1 Counting (lexicographic) order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217
9.2 Minimal-change (Gray code) order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220
9.3 gslex order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224
9.4 endo order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226
9.5 Gray code for endo order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228
9.6 Fixed sum of digits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229
10 Permutations 232
10.1 Factorial representations of permutations . . . . . . . . . . . . . . . . . . . . . . . . . . . 232
10.2 Lexicographic order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242
10.3 Co-lexicographic order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243
10.4 An order from reversing prexes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 245
10.5 Minimal-change order (Heap's algorithm) . . . . . . . . . . . . . . . . . . . . . . . . . . . 248
10.6 Lipski's Minimal-change orders . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 250
10.7 Strong minimal-change order (Trotter's algorithm) . . . . . . . . . . . . . . . . . . . . . . 254
10.8 Star-transposition order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 257
10.9 Minimal-change orders from factorial numbers . . . . . . . . . . . . . . . . . . . . . . . . 258
10.10 Derangement order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 264
10.11 Orders where the smallest element always moves right . . . . . . . . . . . . . . . . . . . . 267
10.12 Single track orders . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 271
11 Permutations with special properties 277
11.1 The number of certain permutations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 277
11.2 Permutations with distance restrictions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 282
11.3 Self-inverse permutations (involutions) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 284
11.4 Cyclic permutations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 285
12 k-permutations 291
12.1 Lexicographic order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 292
12.2 Minimal-change order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293
13 Multisets 295
13.1 Subsets of a multiset . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 295
13.2 Permutations of a multiset . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 296
14 Gray codes for strings with restrictions 304
14.1 List recursions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 304
14.2 Fibonacci words . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 305
14.3 Generalized Fibonacci words . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 307
14.4 Run-length limited (RLL) words . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 310
14.5 Digit x followed by at least x zeros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 311
14.6 Generalized Pell words . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 313
14.7 Sparse signed binary words . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 315
14.8 Strings with no two consecutive nonzero digits . . . . . . . . . . . . . . . . . . . . . . . . 317
14.9 Strings with no two consecutive zeros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 318
14.10 Binary strings without substrings 1x1 or 1xy1 z . . . . . . . . . . . . . . . . . . . . . . . 320
15 Parentheses strings 323
15.1 Co-lexicographic order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323
15.2 Gray code via restricted growth strings . . . . . . . . . . . . . . . . . . . . . . . . . . . . 325
453316713.003.png

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin