没有合适的资源?快使用搜索试试~ 我知道了~
Algorithm for programmer
需积分: 9 77 下载量 180 浏览量
2008-11-12
10:44:02
上传
评论
收藏 4.89MB PDF 举报
温馨提示
试读
992页
程序员的算法书.900多页,很全.有c/c++代码.一本比较新的书,而且随时都在更新.英文非扫描版.
资源推荐
资源详情
资源评论
ii
[fxtbook draft of 2008-November-04]
CONTENTS iii
Contents
Important remarks about this document xi
I Low level algorithms 1
1 Bit wizardry 3
1.1 Trivia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Operations on individual bits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.3 Operations on low bits or blocks of a word . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.4 Extraction of ones, zeros, or blocks near transitions . . . . . . . . . . . . . . . . . . . . . 12
1.5 Computing the index of a single set bit . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.6 Operations on high bits or blocks of a word . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.7 Functions related to the base-2 logarithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.8 Counting bits and blocks of a word . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.9 Counting bits of many words . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
1.10 Words as bit sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.11 Avoiding branches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
1.12 Bit-wise rotation of a word . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
1.13 Functions related to bit-wise rotation and binary necklaces . . . . . . . . . . . . . . . . . 30
1.14 Reversing the bits of a word . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
1.15 Bit-wise zip . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
1.16 Gray code and parity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
1.17 Bit sequency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
1.18 Powers of the Gray code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
1.19 Invertible transforms on words . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
1.20 Space filling curves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
1.21 Scanning for zero bytes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
1.22 2-adic inverse and square root . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
1.23 Radix −2 representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
1.24 A sparse signed binary representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
1.25 Generating bit combinations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
1.26 Generating bit subsets of a given word . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
1.27 Binary words as subsets in lexicographic order . . . . . . . . . . . . . . . . . . . . . . . . 73
1.28 Minimal-change bit combinations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
1.29 Fibonacci words . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
1.30 Binary words and parentheses strings * . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
1.31 Permutations via primitives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
1.32 CPU instructions often missed . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
2 Permutations 91
2.1 The revbin permutation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
2.2 The radix permutation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
[fxtbook draft of 2008-November-04]
iv CONTENTS
2.3 In-place matrix transposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
2.4 The triple reversion technique * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
2.5 The zip permutation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
2.6 The reversed zip permutation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
2.7 The XOR permutation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
2.8 The Gray code permutation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
2.9 The reversed Gray code permutation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
2.10 General permutations and their operations . . . . . . . . . . . . . . . . . . . . . . . . . . 109
3 Sorting and searching 121
3.1 Sorting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
3.2 Binary search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
3.3 Index sorting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
3.4 Pointer sorting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
3.5 Sorting by a supplied comparison function . . . . . . . . . . . . . . . . . . . . . . . . . . 127
3.6 Determination of unique elements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
3.7 Unique elements with inexact types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
3.8 Determination of equivalence classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
3.9 Determination of monotonicity and convexity * . . . . . . . . . . . . . . . . . . . . . . . . 137
3.10 Heapsort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140
3.11 Counting sort and radix sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140
3.12 Searching in unsorted arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
4 Data structures 147
4.1 Stack (LIFO) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
4.2 Ring buffer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
4.3 Queue (FIFO) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150
4.4 Deque (double-ended queue) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
4.5 Heap and priority queue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154
4.6 Bit-array . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158
4.7 Left-right array . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160
4.8 Finite state machines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
4.9 Emulation of coroutines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
II Combinatorial generation 169
5 Conventions and considerations 171
5.1 About representations and orders . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
5.2 Ranking, unranking, and counting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
5.3 Characteristics of the algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172
5.4 Optimization techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173
5.5 The implementations, demo-programs, and timings . . . . . . . . . . . . . . . . . . . . . 174
6 Combinations 175
6.1 Binomial coefficients . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175
6.2 Lexicographic and co-lexicographic order . . . . . . . . . . . . . . . . . . . . . . . . . . . 176
6.3 Order by prefix shifts (cool-lex) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180
6.4 Minimal-change order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181
6.5 The Eades-McKay strong minimal-change order . . . . . . . . . . . . . . . . . . . . . . . 182
6.6 Two-close orderings via endo/enup moves . . . . . . . . . . . . . . . . . . . . . . . . . . . 186
6.7 Recursive generation of certain orderings . . . . . . . . . . . . . . . . . . . . . . . . . . . 191
7 Compositions 193
[fxtbook draft of 2008-November-04]
CONTENTS v
7.1 Co-lexicographic order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193
7.2 Co-lexicographic order for compositions into exactly k parts . . . . . . . . . . . . . . . . 195
7.3 Compositions and combinations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197
7.4 Minimal-change orders . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198
8 Subsets 201
8.1 Lexicographic order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201
8.2 Minimal-change order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204
8.3 Ordering with De Bruijn sequences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207
8.4 Shifts-order for subsets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208
8.5 k-subsets where k lies in a given range . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210
9 Mixed radix numbers 219
9.1 Counting (lexicographic) order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219
9.2 Minimal-change (Gray code) order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222
9.3 gslex order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226
9.4 endo order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229
9.5 Gray code for endo order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 230
10 Permutations 233
10.1 Lexicographic order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233
10.2 Co-lexicographic order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235
10.3 Factorial representations of permutations . . . . . . . . . . . . . . . . . . . . . . . . . . . 236
10.4 An order from reversing prefixes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 246
10.5 Minimal-change order (Heap’s algorithm) . . . . . . . . . . . . . . . . . . . . . . . . . . . 249
10.6 Lipski’s Minimal-change orders . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251
10.7 Strong minimal-change order (Trotter’s algorithm) . . . . . . . . . . . . . . . . . . . . . . 254
10.8 Minimal-change orders from factorial numbers . . . . . . . . . . . . . . . . . . . . . . . . 259
10.9 Orders where the smallest element always moves right . . . . . . . . . . . . . . . . . . . . 265
10.10 Single track orders . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 271
10.11 Star-transposition order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 275
10.12 Derangement order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 277
10.13 Recursive algorithm for cyclic permutations . . . . . . . . . . . . . . . . . . . . . . . . . . 279
10.14 Minimal-change order for cyclic permutations . . . . . . . . . . . . . . . . . . . . . . . . . 281
10.15 Permutations with special properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283
11 Multisets 291
11.1 Subsets of a multiset . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291
11.2 Permutations of a multiset . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 292
12 Gray codes for strings with restrictions 301
12.1 List recursions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 301
12.2 Fibonacci words . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 302
12.3 Generalized Fibonacci words . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 304
12.4 Digit x followed by at least x zeros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 307
12.5 Generalized Pell words . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 308
12.6 Sparse signed binary words . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 310
12.7 Strings with no two successive nonzero digits . . . . . . . . . . . . . . . . . . . . . . . . . 312
12.8 Strings with no two successive zeros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314
12.9 Binary strings without substrings 1x1 or 1xy1 . . . . . . . . . . . . . . . . . . . . . . . . 315
13 Parenthesis strings 319
13.1 Co-lexicographic order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 319
13.2 Gray code via restricted growth strings . . . . . . . . . . . . . . . . . . . . . . . . . . . . 321
[fxtbook draft of 2008-November-04]
剩余991页未读,继续阅读
资源评论
魔鬼筋肉人
- 粉丝: 10
- 资源: 49
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功