Academic
Publications
The Art of Computer Programming: Volume IV: Fascicle 2: Generating All Tuples and Permutations

The Art of Computer Programming: Volume IV: Fascicle 2: Generating All Tuples and Permutations,Donald E. Knuth

The Art of Computer Programming: Volume IV: Fascicle 2: Generating All Tuples and Permutations   (Citations: 37)
BibTex | RIS | RefWorks Download
Published in 2005.
Cumulative Annual
    • ...An introduction to the topic is given by Knuth [5], which opposed to the original text does not demand a background in group theory...

    Florian Wisser. Creating Possible Worlds Using Sims Tables for the Imperfect Informati...

    • ...Section 7.2.1 of Knuth’s The Art of Computer Programming [10,11,12] is an exceptional reference...
    • ...Therefore, r240 =5a ndt240 = 2. For a more complete example, the staircase strings of length 3 appear in column (a) of Table 1 in co-lex order, while columns (b) and (c) contain R4 and T4. (Table 1 appears on page 371 and columns (b) and (c) have been offset by half a row to emphasize the transition between successive staircase strings.) To generate R and T , one can simply augment Algorithm M (Mixed-radix generation) in 7.2.1.1 of [10] ...
    • ...To generate R and T by a loopless algorithm, we can again follow [10]...
    • ...Algorithm H in [10] generates multi-radix strings in reflected Gray code order...
    • ...As Knuth points out at the beginning of Section 7.2.1.2 in The Art of Computer Programming [10], an iterative algorithm for creating the permutations of � n� in co-lex order dates back to the 14th-century...
    • ...Which other orders of permutations can be explained by the specialization of Algorithm H [10] to staircase strings or downward staircase strings (using bases n, n − 1 ,..., 2)? O(1)-Time Unsorting in a Boustrophedon Linked List 379...

    Aaron Williams. O(1)Time Unsorting by Prefix-Reversals in a Boustrophedon Linked List

    • ...The area is so important to computer science that Knuth has dedicated over 400 pages to the subject in his upcoming volume of The Art of Computer Programming [27, 28]...
    • ...The reader is directed towards [28, 27, 29] and [31] for excellent treatments of the subject...

    Aaron Williams. Loopless generation of multiset permutations using a constant number o...

    • ...5 A canonical coordinate sequence is the one in which each coordinate k appears before the first appearance of k + 1 [11]...

    Yury Chebiryaket al. Finding Lean Induced Cycles in Binary Hypercubes

    • ...a Gray code [15] when enumerating steps, always using one group operation per step (this is especially useful for small p, saving up to a factor of 2). A more significant optimization available with Shanks’ method is the ability to perform k discrete logarithms in a group of size N using 2 √ kN (rather than 2k √ N) group operations by storing √ kN baby steps in a lookup table and then taking p N/k...

    Andrew V. Sutherland. Structure computation and discrete logarithms in finite abelian p-grou...

Sort by: