Arndt - Algorithms for Programmers (523138), страница 2
Текст из файла (страница 2)
. . . . . . . . 1377.10 The green code permutation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1387.11 The reversed green code permutation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1387.12 Factorizing permutations . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . 1407.13 General permutations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141CONTENTS47.13.1 Basic definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1417.13.2 Compositions of permutations . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . 1437.13.3 Applying permutations to data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1467.14 Generating all Permutations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1477.14.1 Lexicographic order . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1477.14.2 Minimal-change order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1497.14.3 Derangement order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1517.14.4 Star-transposition order . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . 1527.14.5 An order from graph traversal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1538 Some bit wizardry1558.1Trivia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1558.2Operations on low bits/blocks in a word . . . . . . . . .
. . . . . . . . . . . . . . . . . . . 1588.3Operations on high bits/blocks in a word . . . . . . . . . . . . . . . . . . . . . . . . . . . 1608.4Functions related to the base-2 logarithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 1638.5Counting the bits in a word . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1648.6Swapping bits/blocks of a word . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1658.7Reversing the bits of a word . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . 1668.8Generating bit combinations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1678.9Generating bit subsets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1708.10 Binary words in lexicographic order. . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . 1708.11 Bit set lookup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1738.12 The Gray code of a word. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1748.13 Generating minimal-change bit combinations . . . . . . . . . .
. . . . . . . . . . . . . . . 1778.14 Bitwise rotation of a word . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1798.15 Functions related to bitwise rotation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1808.16 Bitwise zip . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . 1828.17 Bit sequency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1838.18 Misc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1848.19 Hilbert’s space-filling curve .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1868.20 Manipulation of colors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1888.21 2-adic inverse and root . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . 1908.22 Powers of the Gray code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1918.23 Invertible transforms on words . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1928.24 CPU instructions often missed . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . 1989 Sorting and searching1999.1Sorting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1999.2Searching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2019.3Index sorting . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202CONTENTS59.4Pointer sorting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2039.5Sorting by a supplied comparison function . . . . . . . . . . . . . . . . . .
. . . . . . . . . 2049.6Unique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2059.7Misc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2079.8Heap-sort . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21010 Data structures21110.1 Stack (LIFO) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21110.2 Ring buffer . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . 21310.3 Queue (FIFO) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21410.4 Deque (double-ended queue) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . 21510.5 Heap and priority queue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21810.6 Bit-array. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22110.7 Resizable array . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . 22210.8 Ordered resizable array . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22510.9 Resizable set . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22611 Selected combinatorial algorithms22911.1 Combinations in lexicographic order . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . 22911.2 Combinations in co-lexicographic order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23011.3 Combinations in minimal-change order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23211.4 Combinations in alternative minimal-change order . .
. . . . . . . . . . . . . . . . . . . . 23411.5 Offline functions: funcemu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23511.6 Parenthesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23811.7 Partitions . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24011.8 Compositions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24211.8.1 Compositions in lexicographic order . . . .
. . . . . . . . . . . . . . . . . . . . . . 24211.8.2 Compositions from combinations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24411.8.3 Compositions in minimal-change order . . . . . . . . . . . . . . . . . . . . .
. . . . 24511.9 Numbers in lexicographic order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24511.10Subsets in lexicographic order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24611.11Subsets in minimal-change order . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . 24811.12Subsets ordered by number of elements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25011.13Subsets ordered with shift register sequences12 Shift register sequences. . . . . . . . . . . . . . . . . . . . . . . . . 25125312.1 Linear feedback shift register (LFSR) . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . 25312.2 Generation of binary shift register sequences . . . . . . . . . . . . . . . . . . . . . . . . . . 25412.2.1 Searching primitive polynomials . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25612.2.2 Irreducible polynomials of certain forms * . . .
. . . . . . . . . . . . . . . . . . . . 26012.3 Computations with binary polynomials . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 262CONTENTS612.3.1 Basic operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . 26312.3.2 Computations modulo a polynomial . . . . . . . . . . . . . . . . . . . . . . . . . . 26412.3.3 Testing for irreducibility . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26512.3.4 Modulo multiplication with reversed polynomials * . . . . . . . . . . . . . . . . . . 26812.4 Feedback carry shift register (FCSR) . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . 26812.5 Linear hybrid cellular automata (LHCA) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27012.6 Necklaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . 27112.7 Necklaces and Gray codes * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27413 Arithmetical algorithms27913.1 Asymptotics of algorithms . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . 27913.2 Multiplication of large numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27913.2.1 The Karatsuba algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28013.2.2 Fast multiplication via FFT . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . 28013.2.3 Radix/precision considerations with FFT multiplication . . . . . . . . . . . . . . . 28213.3 Division, square root and cube root . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28313.3.1 Division . . . . . . . . . . . . . . . . . .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
