File Generation.h

↰ Parent directory (ADS/combinatorial)

The generation of the basic combinatorial objects of Knuth (7.2.1), beyond the book [see File Enumeration.h for the enumerations by backtrack of chapter 16]: each function calls visit() on every object, in a given order, and returns their number; a visit that returns true stops the generation.

Definition (ADS/combinatorial/Generation.h)

Detailed Description

  • mixedRadix() (Algorithm 7.2.1.1M) the n-tuples with :math:` 0 leq a_j < m_j ` in lexicographic order, and grayTuples() (Algorithm 7.2.1.1H, loopless) in the reflected mixed-radix Gray order, where two consecutive tuples differ by 1 in one place;

  • permutationsLex() (Algorithm 7.2.1.2L, of Narayana Pandita) the permutations of a multiset in lexicographic order, plainChanges() (Algorithm 7.2.1.2P, Steinhaus-Johnson-Trotter) those of n distinct items where two consecutive ones differ by a swap of adjacent items, and heapPermutations() (Heap’s method, 7.2.1.2G) by one swap each, with the least work per permutation;

  • combinationsLex() (Algorithm 7.2.1.3L) the t-combinations of n in lexicographic order, and revolvingDoor() (Algorithm 7.2.1.3R) in the order where two consecutive ones differ by one item in and one out;

  • integerPartitions() (Algorithm 7.2.1.4P) the partitions of n in reverse lexicographic order, and setPartitions() (Algorithm 7.2.1.5H) the partitions of a set of n by their restricted growth strings :math:` a_1 = 0 , a_{j+1} leq 1 + max( a_1 , ldots , a_j ) `;

  • nestedParentheses() (Algorithm 7.2.1.6P) the strings of n pairs of balanced parentheses in lexicographic order, i.e., the forests and the binary trees with n nodes.

The counts are :math:` prod m_j , the multinomial, n!, :math: binom{n}{t} , p( n ), the Bell number :math: varpi_n ` and the Catalan number :math:` C_n , and the tests check them. The contracts [see :ref:`file_ADS_Contract.h]: the radices are positive, 0 <= t <= n, n >= 0. The functions are defined in Generation.tpp.

    1. Knuth, The Art of Computer Programming, vol. 4A, Addison-Wesley, 2011, section 7.2.1

    1. Trotter, Algorithm 115: Perm, Communications of the ACM 5(8), 434-435, 1962, doi:10.1145/368637.368660

    1. Johnson, Generation of permutations by adjacent transposition, Mathematics of Computation 17(83), 282-285, 1963, doi:10.1090/S0025-5718-1963-0159764-2

    1. Heap, Permutations by interchanges, The Computer Journal 6(3), 293-298, 1963, doi:10.1093/comjnl/6.3.293

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Functions

Typedefs