// -*- C++ -*- // automatically generated by autodoc // ========== HEADER FILE src/comb/acgray.h: ========== // ----- SRCFILE=src/comb/acgray.cc: ----- void ac_gray_delta(uchar *d, ulong ldn); // Generate a delta sequence for an adjacent-changes (AC) Gray code // of length n=2**ldn where ldn<=6. // Example (ldn=4): // 0: .... 0 0 // 1: ...1 1 1 0 ...1 // 2: ..11 2 3 1 ..1. // 3: .111 3 7 2 .1.. // 4: .1.1 2 5 1 ..1. // 5: .1.. 1 4 0 ...1 // 6: .11. 2 6 1 ..1. // 7: ..1. 1 2 2 .1.. // 8: 1.1. 2 10 3 1... // 9: 111. 3 14 2 .1.. // 10: 11.. 2 12 1 ..1. // 11: 11.1 3 13 0 ...1 // 12: 1111 4 15 1 ..1. // 13: 1.11 3 11 2 .1.. // 14: 1..1 2 9 1 ..1. // 15: 1... 1 8 0 ...1 // For ldn>=7 the routine produces delta sequences with // 2**(ldn-5) - 1 (ldn odd) // 2**(ldn-5) - 2 (ldn even) // non-AC transitions ("flaws"): // ldn =0..6 #non-ac = 0 // ldn = 7 #non-ac = 3 // ldn = 8 #non-ac = 6 // ldn = 9 #non-ac = 15 // ldn = 10 #non-ac = 30 // ldn = 11 #non-ac = 63 // ldn = 12 #non-ac = 126 // Near-AC Gray codes with fewer "flaws" may well exist. ulong test_ac_gray(ulong *g, ulong n); // Count the number of non-AC transitions in a Gray path. // If the returned value is zero, the Gray path is an AC-path. void ac_gray(ulong *g, ulong ldn); // Create an AC Gray code. // (see ac_gray_delta()) // ========== HEADER FILE src/comb/acyclic-map.h: ========== class acyclic_map; // Acyclic maps: maps from {1, 2, 3, .., n} to {0, 1, 2, 3, ..., n} where // each element is ultimately mapped to 0. // Lexicographic order. // See OEIS sequence A000272 (n^(n-2)). // ========== HEADER FILE src/comb/arith-3-progression.h: ========== inline ulong test_arith_3_progression(const ulong *a, ulong n); // Return last index of first 3-term arithmetic progression found // in a[], return 0 if there is none. inline bool has_arith_3_progression(const ulong *a, ulong n); // Return whether there is a 3-term arithmetic progression in a[]. inline ulong test_arith_3_progression_eqd(const ulong *a, ulong n); // Return last index of first equidistant 3-term arithmetic // progression found in a[], return 0 if there is none. // Here only progressions with equally separated indices // [t], [t+s], [t+2*s] are considered inline bool has_arith_3_progression_eqd(const ulong *a, ulong n); // Return whether there is an equidistant 3-term arithmetic // progression in a[]. inline ulong test_arith_3_progression_consec(const ulong *a, ulong n); // Return last index of first 3-term arithmetic progression in three // consecutive places found in a[], return 0 if there is none. inline bool has_arith_3_progression_consec(const ulong *a, ulong n); // Return whether there is 3-term arithmetic progression in three // consecutive places in a[]. // ========== HEADER FILE src/comb/arrangement-lex.h: ========== class arrangement_lex; // Arrangements (all permutations of all subsets). // Lexicographic order. // Cf. OEIS sequence A000522. // ========== HEADER FILE src/comb/arrangement-rgs.h: ========== class arrangement_rgs; // RGS for arrangements (all permutations of all subsets): // a digit is at most 1 + the number of nonzero digits in the prefix. // The positions of nonzero digits determine the subset, and // their values (decreased by 1) are the (left) inversion table // (a rising factorial number) for the permutation. // Lexicographic order. // Cf. OEIS sequence A000522. // ========== HEADER FILE src/comb/ascent-alt-rgs.h: ========== class ascent_alt_rgs; // Restricted growth strings (RGS) a[1,..,n], where a[k] < k and // no digit a[j] in prefix such that a[j] == a[k] + 1 // Lexicographic order. // The number of length-n RGS is (OEIS sequence A022493) // 1, 1, 2, 5, 15, 53, 217, 1014, 5335, 31240, 201608, ... // ========== HEADER FILE src/comb/ascent-nonflat-rgs.h: ========== class ascent_nonflat_rgs; // Ascent sequences (restricted growth strings, RGS) without flat steps // (i.e., no two adjacent digits are equal), lexicographic order. // An ascent sequence is a sequence [d(1), d(2), ..., d(n)] where d(k)>=0 // and d(k) <= 1 + asc([d(1), d(2), ..., d(k-1)]) and asc(.) counts the // number of ascents of its argument. // The number of length-n RGS is (OEIS sequence A138265) // 1, 1, 1, 2, 5, 16, 61, 271, 1372, 7795, 49093, 339386, 2554596, ... // ========== HEADER FILE src/comb/ascent-rgs-subset-lex.h: ========== class ascent_rgs_subset_lex; // Ascent sequences (restricted growth strings, RGS), subset-lex order. // An ascent sequence is a sequence [d(1), d(2), ..., d(n)] where d(1)=0, d(k)>=0, // and d(k) <= 1 + asc([d(1), d(2), ..., d(k-1)]) and asc(.) counts the // number of ascents of its argument. // The number of length-n RGS is (OEIS sequence A022493) // 1, 1, 2, 5, 15, 53, 217, 1014, 5335, 31240, 201608, ... // ========== HEADER FILE src/comb/ascent-rgs.h: ========== class ascent_rgs; // Ascent sequences (restricted growth strings, RGS), lexicographic order. // An ascent sequence is a sequence [d(1), d(2), ..., d(n)] where d(1)=0, d(k)>=0, // and d(k) <= 1 + asc([d(1), d(2), ..., d(k-1)]) and asc(.) counts the // number of ascents of its argument. // See OEIS sequence A022493. // ========== HEADER FILE src/comb/balanced-ordered-tree-lev-seq.h: ========== class balanced_ordered_tree_lev_seq; // Level sequences for ordered balanced rooted trees. // Lexicographic order. // See OEIS sequences A079500 and A007059. // ========== HEADER FILE src/comb/big-fact2perm.h: ========== // ----- SRCFILE=src/comb/big-fact2perm.cc: ----- void perm2ffact(const ulong *x, ulong n, ulong *fc, left_right_array &LR); // Convert permutation in x[0,...,n-1] into // the (n-1) digit factorial representation in fc[0,...,n-2]. // We have: fc[0]=1), // n == a[0] + a[1] + a[2] + a[3] + ... + a[m]. // Same as: binary Huffman codes (canonical trees) with n terminal nodes, // a[k] is the number of terminal nodes of depth k. // Reversed lexicographic order. // See: // Christian Elsholtz, Clemens Heuberger, Helmut Prodinger: // "The number of Huffman codes, compact trees, and sums of unit fractions", // arXiv:1108.5964 [math.CO], (30-August-2011). // // Cf. OEIS sequence A002572. // ========== HEADER FILE src/comb/binary-necklace.h: ========== class binary_necklace; // Binary necklaces, pre-necklaces, and Lyndon words. // Cf. OEIS sequences A062692 (pre-necklaces), A000031 (necklaces), // and A001037 (Lyndon words). // ========== HEADER FILE src/comb/binary-rot.h: ========== class binary_rot; // Binary strings by rotations of prefixes. // This is the "cooler" order from: // Brett Stevens, Aaron Williams: The coolest order of binary strings, // 6th International Conference on Fun with Algorithms (FUN 2012), // San Servolo, Italy. LNCS 7288, pp.322-333, (2012). // ========== HEADER FILE src/comb/binary-sl-gray.h: ========== class binary_sl_gray; // Binary numbers in a minimal-change order // related so subset-lex order ("SL-Gray" order). // Representation as delta-sets (binary words), in A[]. // Loopless generation, only O(1) data beyond the array of bits. // Successive transitions are mostly adjacent, // and otherwise have distance 3. // Special case of class mixed_radix_sl_gray for base 2. // Cf. OEIS sequence A217262. // See Joerg Arndt, Subset-lex: did we miss an order?, (2014) // http://arxiv.org/abs/1405.6503 // ========== HEADER FILE src/comb/catalan-flat-path-lex.h: ========== class catalan_flat_path_lex; // Catalan paths in lexicographic order, CAT algorithm. // Steps are +1, 0, -1 (up, horizontal, down), // the first and last elements are 0, all elements are non-negative. // ========== HEADER FILE src/comb/catalan-path-lex.h: ========== class catalan_path_lex; // Catalan paths in lexicographic order, CAT algorithm. // Steps are +1, -1 (up, down), // the first and last elements are 0, all elements are non-negative, // and even/odd positions respectively have even/odd entries only. // ========== HEADER FILE src/comb/catalan-rgs-gray.h: ========== class catalan_rgs_gray; // Catalan restricted growth strings (RGS): // strings a[0,1,...,n-1] where a[0]=0 and a[k] <= a[k-1] + 1. // Gray code for parenthesis strings (but not for the RGS). // ========== HEADER FILE src/comb/catalan-rgs-gslex.h: ========== class catalan_rgs_gslex; // Catalan restricted growth strings (RGS): // strings a[0,1,...,n-1] where a[0]=0 and a[k] <= a[k-1] + 1. // Ordering similar to gslex (and subset-lex) order. // Loopless algorithm. // ========== HEADER FILE src/comb/catalan-rgs-subset-lex.h: ========== class catalan_rgs_subset_lex; // Catalan restricted growth strings (RGS): // strings a[0,1,...,n-1] where a[0]=0 and a[k] <= a[k-1] + 1. // Subset-lex order. // ========== HEADER FILE src/comb/catalan-rgs-to-noncrossing-setpart-rgs.h: ========== inline void catalan_rgs_to_noncrossing_setpart_rgs(const ulong *A, ulong n,; ulong *P) // Compute the RGS for a noncrossing set partition from the // Catalan RGS given in A[]. Result is written to P[]. // Complexity is O(n). // Example: // Catalan RGS setpart RGS set partition // 1: [ . . . . ] [ . . . . ] {1, 2, 3, 4} // 2: [ . . . 1 ] [ . . . 1 ] {1, 2, 3}, {4} // 3: [ . . 1 . ] [ . . 1 . ] {1, 2, 4}, {3} // 4: [ . . 1 1 ] [ . . 1 1 ] {1, 2}, {3, 4} // 5: [ . . 1 2 ] [ . . 1 2 ] {1, 2}, {3}, {4} // 6: [ . 1 . . ] [ . 1 . . ] {1, 3, 4}, {2} // 7: [ . 1 . 1 ] [ . 1 . 2 ] {1, 3}, {2}, {4} <--= RGS differ // 8: [ . 1 1 . ] [ . 1 1 . ] {1, 4}, {2, 3} // 9: [ . 1 1 1 ] [ . 1 1 1 ] {1}, {2, 3, 4} // 10: [ . 1 1 2 ] [ . 1 1 2 ] {1}, {2, 3}, {4} // 11: [ . 1 2 . ] [ . 1 2 . ] {1, 4}, {2}, {3} // 12: [ . 1 2 1 ] [ . 1 2 1 ] {1}, {2, 4}, {3} // 13: [ . 1 2 2 ] [ . 1 2 2 ] {1}, {2}, {3, 4} // 14: [ . 1 2 3 ] [ . 1 2 3 ] {1}, {2}, {3}, {4} // Note that the set partitions can also be read as // cycle forms of genus-0 permutations. // ========== HEADER FILE src/comb/catalan-rgs.h: ========== class catalan_rgs; // Catalan restricted growth strings (RGS): // strings a[0,1,...,n-1] where a[0]=0 and a[k] <= a[k-1] + 1. // Lexicographic order. // The number of length-n RGS is (OEIS sequence A000108) // 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, ... // Sequence A239903 gives the RGS. // ========== HEADER FILE src/comb/catalan-step-rgs-colex.h: ========== class catalan_step_rgs_colex; // Catalan step RGS (restricted growth strings), co-lexicographic order. // RGS are a[] such that a[k] >= a[k-1] (weakly ascending) and a[k]<=k. // The RGS describe lattice paths from (0,0) to (n,n) with steps // (+1,0) and (+1,+1) that do not go below the diagonal. // Cf. OEIS sequence A000108. // ========== HEADER FILE src/comb/catalan-step-rgs-lex.h: ========== class catalan_step_rgs_lex; // Catalan step RGS (restricted growth strings), lexicographic order. // The RGS are a[] such that a[k] >= a[k-1] (weakly ascending) and a[k]<=k. // The RGS describe lattice paths from (0,0) to (n,n) with steps // (+1,0) and (+1,+1) that do not go below the diagonal. // Same as: rising factorial numbers where the digits are sorted. // Cf. OEIS sequence A000108. // ========== HEADER FILE src/comb/catalan-step-rgs-subset-lexrev.h: ========== class catalan_step_rgs_subset_lexrev; // Catalan step RGS (restricted growth strings), subset-lexrev order. // RGS are a[] such that a[k] >= a[k-1] (weakly ascending) and a[k]<=k. // The RGS describe lattice paths from (0,0) to (n,n) with steps // (+1,0) and (+1,+1) that do not go below the diagonal. // Same as: rising factorial numbers where the digits are sorted. // See Joerg Arndt, Subset-lex: did we miss an order?, (2014) // http://arxiv.org/abs/1405.6503 // ========== HEADER FILE src/comb/catalan-step-rgs-to-paren-string.h: ========== inline void catalan_step_rgs_to_paren_string(const ulong *rgs, ulong n, char *str); // ========== HEADER FILE src/comb/catalan.h: ========== class catalan; // Catalan restricted growth strings (RGS) // By default in a minimal-change order, i.e. // exactly two symbols in paren string change with each step. // Most changes are adjacent or skip-2 // Non adjacent changes move a bit over ones. // ========== HEADER FILE src/comb/cayley-perm.h: ========== class cayley_perm; // Cayley permutations: Length-n words such that all elements // from 0 to the maximum value occur at least once. // Same as: permutations of the (RGS for) set partitions of n. // Same as: weak orders on n elements (weak orders are // relations that are transitive and complete). // Same as: preferential arrangements of n labeled elements. // Generation such that the major order is by content, and // the minor order is lexicographic. // Cf. OEIS sequence A000670 (Fubini numbers). // ========== HEADER FILE src/comb/change-rgs.h: ========== class change_rgs; // Change sequences (restricted growth strings, RGS), lexicographic order. // A change sequence is a sequence [d(1), d(2), ..., d(n)] where d(1)=0, // d(k)>=0, and d(k) <= 1 + chg([d(1), d(2), ..., d(k-1)]) and chg(.) // counts the number of changes of its argument. // See OEIS sequence A000522. // ========== HEADER FILE src/comb/check-kpermgen.h: ========== class check_kpermgen; // Checking validity of list of k-permutations. // ========== HEADER FILE src/comb/check-mixedradix.h: ========== class check_mixedradix; // Checking validity of list of mixed radix numbers. // ========== HEADER FILE src/comb/check-permgen.h: ========== class check_permgen; // Checking validity of list of permutations. // ========== HEADER FILE src/comb/comb-print.h: ========== // ----- SRCFILE=src/comb/print-set.cc: ----- void print_set(const char *bla, const ulong *x, ulong n, ulong off/*=0*/); // Print x[0,..,n-1] as set, n is the number of elements in the set. // Example: x[]=[0,1,3,4,8] ==> "{0,1,3,4,8}" void print_set_as_deltaset(const char *bla, const ulong *x, ulong n, ulong N, const char *c01/*=0*/); // Print x[0,..,n-1], a subset of {0,1,...,N-1} as delta set, // n is the number of elements in the set. // Example: x[]=[0,1,3,4,8] ==> "11.11...1" void print_set1_as_deltaset(const char *bla, const ulong *x, ulong n, ulong N, const char *c01/*=0*/); // Print x[0,..,n-1], a subset of {1,...,N} as delta set, // n is the number of elements in the set. // Example: x[]=[1,2,4,5,9] ==> "11.11...1" ulong print_deltaset_as_set(const char *bla, const ulong *x, ulong n, int eq/*=0*/); // Print delta set x[0,..,n-1] as set. // Example: x[]=[0,0,1,0,1,1] ==> "{2,4,5}" // if eq!=0 then print spaces for empty positions: // With example above: "{ , , 2, , 4, 5}" // Return number of elements (3 in example). ulong print_deltaset_as_set1(const char *bla, const ulong *x, ulong n, int eq/*=0*/); // Print delta set x[0,..,n-1] as set, lowest element one. // Example: x[]=[0,0,1,0,1,1] ==> "{3,5,6}" // if eq!=0 then print spaces for empty positions: // With example above: "{ , , 3, , 5, 6}" // Return number of elements (3 in example). void print_deltaset(const char *bla, const ulong *x, ulong n, const char *c01/*=0*/); // Print the delta set x[0,..,n-1] // n is the number of elements in the set. // Example: x[]=[1,0,1,1,0,0,0,1,0] ==> "11.11...1." // Example: x[]=[1,0,1,1,0,0,0,1,0] with c01==")(" ==> "(()(()))()" // ----- SRCFILE=src/comb/print-mset.cc: ----- ulong print_multi_deltaset_as_set(const char *bla, const ulong *x, ulong n, bool cq/*=true*/); // Print multi delta set x[0,..,n-1] as set. // Example: x[]=[0,0,1,0,3,0,1] ==> "{2,4,4,4,6}" // Return number of elements (5 in example). // Parameter cq determines whether commas (and spaces) are printed between elements. ulong print_multi_deltaset_as_set_alph(const char *bla, const ulong *x, ulong n, bool cq/*=true*/); // Print multi delta set x[0,..,n-1] as set of letters. // Example: x[]=[0,1,3,0,1] ==> "{b,c,c,c,e}" // Return number of elements (5 in example). // Parameter cq determines whether commas (and spaces) are printed between elements. // ----- SRCFILE=src/comb/print-perm.cc: ----- void print_perm(const char *bla, const ulong *f, ulong n, bool dfz/*=false*/); // Print n-digit permutation in f[]. // If dfz is true then Dots are printed For Zeros. // ----- SRCFILE=src/comb/print-setpart.cc: ----- void print_setpart(const char *bla, const ulong *r, ulong n, ulong ns, ulong off/*=1*/); // Print length-n RGS s[] for set partition as set partition. // Offset off is added to all elements. // ns should be the number of sets, it is computed if given as zero. // ----- SRCFILE=src/comb/print-vec.cc: ----- void print_vec(const char *bla, const ulong *x, ulong n, bool dfz/*=false*/); // Print x[0,..,n-1] as vector, n is the number of elements in the set. // If dfz is true then Dots are printed For Zeros. void print_vec1(const char *bla, const ulong *x, ulong n); // Print x[0,..,n-1] as vector, each element incremented by one, // n is the number of elements in the set. void print_vec_rev(const char *bla, const ulong *x, ulong n, bool dfz/*=false*/); // Print x[0,..,n-1] as vector in reversed order, n is the number of elements in the set. // If dfz is true then Dots are printed For Zeros. void print_sign_vec(const char *bla, const ulong *x, ulong n); // Print x[0,..,n-1] as vector of signs void print_sym_vec(const char *bla, const ulong *x, ulong n); // Print x[0,..,n-1] as vector of symbols where // symbols are 0,1,..,9, A,B...,Z, a,b,...,z // ----- SRCFILE=src/comb/print-mixedradix.cc: ----- void print_mixedradix(const char *bla, const ulong *f, ulong n, bool dfz/*=false*/); // Print n-digit mixed radix number in f[]. // If dfz is true then Dots are printed For Zeros. // ----- SRCFILE=src/comb/print-gray.cc: ----- void print_gray(const ulong *f, ulong n); // Pretty print Gray path void print_gray_delta(const ulong *f, ulong n, ulong lb/*=0*/); // Print delta seqeunce (base-36). // If lg!=0 then break line after lg characters. // ========== HEADER FILE src/comb/combination-chase.h: ========== class combination_chase; // Combinations (n choose k) in a strong minimal-change order. // The delta set is generated. // Algorithm C, "Chase's sequence", TAOCP 4A/1, pp.367. // Phillip J. Chase: Combination generation and graylex ordering, // Congressus Numerantium, vol.69, pp.215-242, (1989) // ========== HEADER FILE src/comb/combination-colex.h: ========== class combination_colex; // Combinations n choose k (co-lexicographic order). // ========== HEADER FILE src/comb/combination-emk.h: ========== class combination_emk; // Combinations in strong minimal-change order (Eades-McKay sequence). // The set (as opposed to delta set) is generated. // Generation via modulo steps counting. // Peter Eades, Brendan McKay: An algorithm for generating subsets // of fixed size with a strong minimal change property, // Information Processing Letters, vol.19, pp.131-133, (19-October-1984). // ========== HEADER FILE src/comb/combination-endo.h: ========== class combination_endo; // Combinations (n choose k) in strong minimal-change order ("Chase's sequence"). // The set (as opposed to delta set) is generated. // Generation via endo/enup counting. // ========== HEADER FILE src/comb/combination-enup.h: ========== class combination_enup; // Combinations in a strong minimal-change order (enup steps). // The set (as opposed to delta set) is generated. // Generation via enup/endo counting. // ========== HEADER FILE src/comb/combination-lex.h: ========== class combination_lex; // Combinations (n choose k) in lexicographic order. // ========== HEADER FILE src/comb/combination-mod.h: ========== class combination_mod; // Combinations in a strong minimal-change order. // The set (as opposed to delta set) is generated. // Generation via modulo steps counting. // Obtained by a slight modification of the Eades-McKay sequence. // ========== HEADER FILE src/comb/combination-pref.h: ========== class combination_pref; // Combinations via prefix shifts ("cool-lex" order) as delta sets. //. // Algorithm as in // Frank Ruskey, Aaron Williams: // "Generating combinations by prefix shifts" // Lecture Notes in Computer Science, vol.3595, 2005. // Extended Abstract for COCOON 2005. // ========== HEADER FILE src/comb/combination-rec.h: ========== class comb_rec; // Combinations in lexicographic, Gray code, // complemented enup, and complemented Eades-McKay order. // Recursive algorithm. // ========== HEADER FILE src/comb/combination-revdoor.h: ========== class combination_revdoor; // Combinations in a minimal-change order. // Algorithm R, "revolving-door combinations", TAOCP 4A/1, pp.363. // W. H. Payne, F. M. Ives: "Combination Generators", // ACM Transactions on Mathematical Software (TOMS), // vol.5, no.2, pp.163-172, (June-1979). // ========== HEADER FILE src/comb/comp2comb.h: ========== // Conversion between combinations and compositions inline void comp2comb_nk(ulong n, ulong k, ulong &N, ulong &K); // A composition P(n,k) of n into (at most) k parts corresponds to // a combination B(N,K) of K=n parts from N=n+k-1 elements: // P(n, k) <--> B(N, K) == B(n+k-1, n) inline void comb2comp_nk(ulong N, ulong K, ulong &n, ulong &k); // A combination B(N,K) of K elements out of N // corresponds to a composition P(n,k) of n into (at most) k parts // where k=N-K+1 and n=K: // B(N, K) <--> P(n, k) == P(K, N-K+1) inline void comp2comb(const ulong *p, ulong k, ulong *b); // Convert composition P(*, k) in p[] to combination in b[] inline void comb2comp(const ulong *b, ulong N, ulong K, ulong *p); // Convert combination B(N, K) in b[] to composition P(*,k) in p[] // Must have: K>=1 inline void reverse_combination(ulong *b, ulong N, ulong K); // Reverse order and complement values in combination b[] // Equivalent to order reversal of the corresponding composition: // B <--> P ==> reverse_combination(B) <--> reverse(P) // ========== HEADER FILE src/comb/composition-colex.h: ========== class composition_colex; // Compositions of n into (at most) k parts (k-compositions of n), // co-lexicographic (colex) order // ========== HEADER FILE src/comb/composition-colex2.h: ========== class composition_colex2; // Compositions of n into (at most) k parts (k-compositions of n), // co-lexicographic (colex) order. // Implementation efficient also with sparse case, i.e. k much greater than n. // Loopless algorithm. // ========== HEADER FILE src/comb/composition-dist-unimodal.h: ========== class composition_dist_unimodal; // Strongly unimodal compositions into distinct parts. // Representation as list of parts in increasing order, // with each part except for the last of 2 sorts. // Cf. OEIS sequence A072706. // ========== HEADER FILE src/comb/composition-ex-colex.h: ========== class composition_ex_colex; // Compositions of n into exactly k parts (k-compositions of n), // co-lexicographic (colex) order. // Must have: n >= k. // ========== HEADER FILE src/comb/composition-ex-lex.h: ========== class composition_ex_lex; // Compositions of n into exactly k parts (k-compositions of n), // lexicographic order. // Must have: n >= k. // ========== HEADER FILE src/comb/composition-nz-binary.h: ========== class composition_nz_binary; // Compositions of n into powers of 2, lexicographic order. // Cf. OEIS sequence A023359. // ========== HEADER FILE src/comb/composition-nz-carlitz.h: ========== class composition_nz_carlitz; // Compositions of n into positive parts, such that // adjacent parts are different. Lexicographic order. // Cf. OEIS sequence A003242. // ========== HEADER FILE src/comb/composition-nz-conj.h: ========== inline ulong composition_nz_conj(const ulong *x, ulong m, ulong *c); // Write conjugate of composition x[] (m non-zero parts) to c[]. // Return number of parts written to c[]. // Conjugation is swapping separators and non-separators // in the "stars and bars" representation. // For example, [5,3,1,2,2] and [1,1,1,1,2,1,3,2,1] are conjugates: // // 5 3 1 2 2 // |* * * * *|* * *|*|* *|* *| // |*|*|*|*|* *|*|* * *|* *|*| // 1 1 1 1 2 1 3 2 1 // // ========== HEADER FILE src/comb/composition-nz-first-max.h: ========== class composition_nz_first_max; // Compositions of n into positive parts where no part is greater than the first. // Lexicographic order. // See OEIS sequences A079500 and A007059. // ========== HEADER FILE src/comb/composition-nz-gray.h: ========== class composition_nz_gray; // Compositions of n into positive parts. // Gray code with moves of only one unit, all moves are one-close or // two-close, two-close moves always cross a part =1 and all moves are // at the end, involving the last element. // Loopless algorithm. // Same as class composition_nz_gray for odd n, reversed list for even n. // First composition has one part for n odd, and two parts for n even. // See Joerg Arndt, Subset-lex: did we miss an order?, (2014) // http://arxiv.org/abs/1405.6503 // ========== HEADER FILE src/comb/composition-nz-gray2.h: ========== class composition_nz_gray2; // Compositions of n into positive parts. // Gray code with moves of only one unit, all moves are one-close or // two-close, two-close moves always cross a part =1 and all moves are // at the end, involving the last element. // Loopless algorithm. // Same as class composition_nz_gray for odd n, reversed list for even n. // First composition has one part for all n. // See Joerg Arndt, Subset-lex: did we miss an order?, (2014) // http://arxiv.org/abs/1405.6503 // ========== HEADER FILE src/comb/composition-nz-i-smooth.h: ========== class composition_nz_i_smooth; // Internally smooth compositions: // consecutive parts differ by at most 1. // Lexicographic order. // See OEIS sequence A034297. // ========== HEADER FILE src/comb/composition-nz-left-2smooth.h: ========== class composition_nz_left_2smooth; // Left-2smooth compositions: // compositions of n with maximal up-step 1, // no consecutive up-steps, and first part 1. // Lexicographic order. // Cf. OEIS sequence A186085. // ========== HEADER FILE src/comb/composition-nz-left-smooth.h: ========== class composition_nz_left_smooth; // Left-smooth compositions: compositions of n // with maximal up-step <= 1 and first part 1. // Lexicographic order. // Same as "fountains of coins", see OEIS sequence A005169. // ========== HEADER FILE src/comb/composition-nz-max.h: ========== class composition_nz_max; // Compositions of n into positive parts <= mx. // Lexicographic order. // ========== HEADER FILE src/comb/composition-nz-min.h: ========== class composition_nz_min; // Compositions of n into positive parts >= mi. // Lexicographic order. // ========== HEADER FILE src/comb/composition-nz-minc.h: ========== class composition_nz_minc; // Compositions of n into positive parts with first part a1 and // each part <= f times its predecessor. // For a1=1 the same as: f-ary Huffman codes (canonical trees) with // (f-1)*n+1 terminal nodes, a[k] is the number of internal nodes of depth k. // Such compositions (for f=2) are treated in // Henryk Minc: "A Problem in Partitions: Enumeration of Elements of a // given Degree in the free commutative entropic cyclic Groupoid", // Proceedings of the Edinburgh Mathematical Society (2), // vol.11, no.4, pp.223-224, (November-1959). // The compositions for f=2 are also called "Cayley compositions", see // George E. Andrews, Peter Paule, Axel Riese, Volker Strehl: // "MacMahon's Partition Analysis V: Bijections, Recursions, and Magic Squares", // in: Algebraic Combinatorics and Applications, proceedings of Euroconference Alcoma 99, // September 12-19, 1999, Goessweinstein, Germany, // A. Betten, A. Kohnert, R. Laue, A. Wassermann eds., Springer-Verlag, pp.1-39, (2001). // See also: // Christian Elsholtz, Clemens Heuberger, Helmut Prodinger: // "The number of Huffman codes, compact trees, and sums of unit fractions", // arXiv:1108.5964 [math.CO], (30-August-2011). // // Cf. OEIS sequences: // f=2: A002572 (a1=1), A002573 (a1=2), A002574 (a1=3), // A049284 (a1=4), A049285 (a1=5). // a1=1: A002572 (f=2), A176485 (f=3), A176503 (f=4), // A194628 (f=5), A194629 (f=6), A194630 (f=7), // A194631 (f=8), A194632 (f=9), A194633 (f=10). // f=2 and a1=1..n: A002843. // ========== HEADER FILE src/comb/composition-nz-numparts.h: ========== class composition_nz_numparts; // Compositions of n into nonzero parts. // Ordering is firstly by number of parts (1, 2, ..., n) // and secondly co-lexicographic (colex). // ========== HEADER FILE src/comb/composition-nz-odd-subset-lex.h: ========== class composition_nz_odd_subset_lex; // Compositions of n into positive odd parts, subset-lex order. // Loopless algorithm. // Cf. OEIS sequence A000045. // See Joerg Arndt, Subset-lex: did we miss an order?, (2014) // http://arxiv.org/abs/1405.6503 // ========== HEADER FILE src/comb/composition-nz-odd.h: ========== class composition_nz_odd; // Compositions of n into positive odd parts, lexicographic order. // Loopless algorithm. // Cf. OEIS sequence A000045. // ========== HEADER FILE src/comb/composition-nz-prefix-cond.h: ========== class composition_nz_prefix_cond; // Compositions of n into positive parts with restricted prefixes. // Lexicographic order. // ========== HEADER FILE src/comb/composition-nz-rank.h: ========== // ----- SRCFILE=src/comb/composition-nz-rank.cc: ----- ulong composition_nz_rank(const ulong *x, ulong m); // Return rank r of composition x[], 0 <= r < 2**(n-1) // where n is the sum of all parts. // For lexicographic order (cf. class composition_nz). ulong composition_nz_unrank(ulong r, ulong *x, ulong n); // Generate composition x[] of n with rank r. // Return number of parts m of generated composition, 1 <= m <= n. // For lexicographic order (cf. class composition_nz). // The rank r is taken modulo 2 ** (n-1). ulong composition_nz_rl_rank(const ulong *x, ulong m); // Return (run-length) rank r of composition x[], 0 <= r < 2**(n-1) // where n is the sum of all parts. // For RL-order (cf. class composition_nz_rl). ulong composition_nz_rl_unrank(ulong r, ulong *x, ulong n); // Generate composition x[] of n with rank r. // Return number of parts m of generated composition, 1 <= m <= n. // For RL-order (cf. class composition_nz_rl). // The rank r is taken modulo 2 ** (n-1). ulong composition_nz_subset_lex_rank(const ulong *x, ulong m, ulong n); // Return rank r of composition x[], 0 <= r < 2**(n-1) // where n is the sum of all parts. // For subset-lex order (cf. class composition_nz_subset_lex). ulong composition_nz_subset_lex_unrank(ulong r, ulong *x, ulong n); // Generate composition x[] of n with rank r. // Return number of parts m of generated composition, 1 <= m <= n. // For subset-lex order (cf. class composition_nz_subset_lex). // The rank r is taken modulo 2 ** (n-1). ulong composition_nz_gray_rank(const ulong *x, ulong m, ulong n); // Return rank r of composition x[], 0 <= r < 2**(n-1) // where n is the sum of all parts. // For Gray code (cf. class composition_nz_gray). ulong composition_nz_gray_unrank(ulong r, ulong *x, ulong n); // Generate composition x[] of n with rank r. // Return number of parts m of generated composition, 0 <= m <= n. // For Gray code (cf. class composition_nz_gray). // The rank r is taken modulo 2 ** (n-1). // ========== HEADER FILE src/comb/composition-nz-rl.h: ========== class composition_nz_rl; // Compositions of n into positive parts, order by run-length rank. // Loopless algorithm. // ========== HEADER FILE src/comb/composition-nz-smooth.h: ========== class composition_nz_smooth; // Smooth compositions: compositions of n with first and last part 1 // and maximal absolute difference 1 between consecutive parts. // Lexicographic order. // Same as "1-dimensional sand piles", see OEIS sequence A186085. // ========== HEADER FILE src/comb/composition-nz-sorts.h: ========== class composition_nz_sorts; // Compositions of n into positive parts of s sorts. // Lexicographic order: major order by sorts, minor by parts, where // comparison proceeds as sort1, part1; sort2, part2; sort3, part3, etc. // Loopless algorithm. // Cf. OEIS sequences (compositions of n into parts of s kinds): // A011782 (s=1), A025192 (s=2), A002001 (s=3), A005054 (s=4), // A052934 (s=5), A055272 (s=6), A055274 (s=7), and A055275 (s=8). // ========== HEADER FILE src/comb/composition-nz-sorts2-pp.h: ========== class composition_nz_sorts2_pp; // Compositions of n into positive parts of s[k] sorts for part (size) k. // Lexicographic order: major order by parts, minor by sorts, where // comparison proceeds as part1, sort1; part2, sort2; part3, sort3, etc. // Loopless algorithm. // Cf. OEIS sequence A088305 // compositions of n into one sort of 1's, two sorts of 2's, ..., k sorts of k's. // Cf. OEIS sequences (compositions of n into (all) parts of s kinds): // A011782 (s=1), A025192 (s=2), A002001 (s=3), A005054 (s=4), // A052934 (s=5), A055272 (s=6), A055274 (s=7), and A055275 (s=8). // ========== HEADER FILE src/comb/composition-nz-sorts2.h: ========== class composition_nz_sorts2; // Compositions of n into positive parts of s sorts. // Lexicographic order: major order by parts, minor by sorts, where // comparison proceeds as part1, sort1; part2, sort2; part3, sort3, etc. // Loopless algorithm. // Cf. OEIS sequences (compositions of n into parts of s kinds): // A011782 (s=1), A025192 (s=2), A002001 (s=3), A005054 (s=4), // A052934 (s=5), A055272 (s=6), A055274 (s=7), and A055275 (s=8). // ========== HEADER FILE src/comb/composition-nz-subdiagonal.h: ========== class composition_nz_subdiagonal; // Subdiagonal compositions: compositions a[1] + a[2] + ... + a[m] = n // such that a[k] <= k. // Lexicographic order. // Cf. OEIS sequence A008930. // ========== HEADER FILE src/comb/composition-nz-subset-lex.h: ========== class composition_nz_subset_lex; // Compositions of n into positive parts. // Gray code such that either two adjacent positions change // or one unit is moved by two positions. // The number of parts changes by one at each transition. // Loopless algorithm. // See Joerg Arndt, Subset-lex: did we miss an order?, (2014) // http://arxiv.org/abs/1405.6503 // ========== HEADER FILE src/comb/composition-nz-superdiagonal.h: ========== class composition_nz_superdiagonal; // Superdiagonal compositions: compositions a[1] + a[2] + ... + a[m] = n // such that a[k] >= k. // Lexicographic order. // Same as: superdiagonal bargraphs, see // Emeric Deutsch, Emanuele Munarini, Simone Rinaldi: // "Skew Dyck paths, area, and superdiagonal bargraphs", // Journal of Statistical Planning and Inference, // vol.140, no.6, pp.1550-1562, (June-2010). // Cf. OEIS sequence A219282. // ========== HEADER FILE src/comb/composition-nz-upstep.h: ========== class composition_nz_upstep; // Compositions of n into positive parts, with limit on up-step. // Lexicographic order. // Cf. OEIS sequences A003116 (max up-step 1) // and A224959 (max up-step 2). // Max up-step 0 gives partitions as weakly descending lists. // ========== HEADER FILE src/comb/composition-nz-weakly-unimodal.h: ========== class composition_nz_weakly_unimodal; // Weakly unimodal compositions, lexicographic order. // Cf. OEIS sequence A001523. // ========== HEADER FILE src/comb/composition-nz.h: ========== class composition_nz; // Compositions of n into positive parts, lexicographic order. // Loopless algorithm for successor. // ========== HEADER FILE src/comb/composition-rank.h: ========== class composition_rank; // Ranking and unranking compositions in // lexicographic, minimal-change, or enup (two-close) order. // The routines rank_*(x,n,k) have complexity k*k. // The routines unrank_*(x,n,k) have complexity k * X // where X is the complexity of unrank_get_el(); // X=n as given but can be reduced to log(n). // Note: the two-close order corresponds to the enup order for combinations. // ========== HEADER FILE src/comb/composition-unimodal.h: ========== class composition_unimodal; // Strongly unimodal compositions. // Representation as list of parts in weakly ascending order, // with each part except for the last of 2 sorts and // no repeated parts of the same sort. // Cf. OEIS sequence A059618. // ========== HEADER FILE src/comb/cyclic-perm-gray.h: ========== class cyclic_perm_gray; // Cyclic permutations in minimal-change order. // CAT algorithm based on mixed radix Gray code // for the factorial number system. // ========== HEADER FILE src/comb/cyclic-words.h: ========== ulong cyclic_lex_min_idx(const Type *W, ulong n); // Return index i such that the word W, read (cyclically) starting at i, // is the lexicographically minimal cyclic shift of W. // In other words: // among all rotations of W, the one shifted by i letters (to the left) is lex-min. //. // Orignal code taken from https://stackoverflow.com/questions/3459509/ // Cleaned up and optimized. bool is_cyclic_lex_min(const Type *W, ulong n); // Return whether W[] is the minimum among all its cyclic rotations. // Equivalently, whether 0 === cyclic_lex_min_idx(W, n), // but faster on average. ulong cyclic_lex_min_word(const Type *W, ulong n, Type *M); // Return index i as in cyclic_lex_min_idx(W, n) and // write the cyclic lex-min word to M. // Must have W != M. bool cyclic_equal_p(const Type * A, const Type * B, ulong n); // Return whether the words A and B are equal up to cyclic shift. // // Algorithm from pp. 363ff, Section 15.4, // "Cyclic equality of words, and Lyndon factorization" // in // Maxime Crochemore, Wojciech Rytter, Text Algorithms, // Oxford University Press, 1994. // // This implementation avoids duplicating the words at start. int cyclic_compare(const Type * A, ulong ai, const Type * B, ulong bi, ulong n); // Compare A[ai, ai+1, ...] and B[bi, bi+1, ...] cyclically (indices taken mod n). // Return +1 if A[] > B[], -1 if A[] < B[], otherwise (A[]==B[]) 0. int cyclic_compare_min(const Type * A, const Type * B, ulong n); // Compare the cyclic minima of the words A[] and B[]: // Let ai and bi be the indices returned by cyclic_lex_min_idx() // for A[] and B[] respectively. // Compare A[ai, ai+1, ...] and B[bi, bi+1, ...] cyclically (indices taken mod n). // Return +1 if A[] > B[], -1 if A[] < B[], otherwise (A[]==B[]) return 0. // ========== HEADER FILE src/comb/debruijn.h: ========== class debruijn : public necklace; // Lexicographic minimal De Bruijn sequence. // ========== HEADER FILE src/comb/delta2gray.h: ========== // ----- SRCFILE=src/comb/delta2gray.cc: ----- void delta2gray(const unsigned char *d, ulong ldn, ulong *g, ulong g0/*=0*/); // Fill into g[0..N-1] (N=2**ldn) the Gray path // corresponding to the delta sequence d[0..N-2]. void gray2delta(ulong ldn, const ulong *g, unsigned char *d); // Inverse of delta2gray(). // ========== HEADER FILE src/comb/descent-rgs.h: ========== class descent_rgs; // Descent sequences (restricted growth strings, RGS), lexicographic order. // A descent sequence is a sequence [d(1), d(2), ..., d(n)] where d(1)=0, // d(k)>=0, and d(k) <= 1 + desc([d(1), d(2), ..., d(k-1)]) and desc(.) // counts the number of descents of its argument. // See OEIS sequence A225588. // ========== HEADER FILE src/comb/dyck-gray.h: ========== class dyck_gray; // Gray code for k-ary Dyck words with homogeneous transitions. // Loopless algorithm following // Dominique Roelants van Baronaigien: // "A Loopless Gray-Code Algorithm for Listing k-ary Trees", // Journal of Algorithms, vol.35, pp.100-107, (2000). // ========== HEADER FILE src/comb/dyck-gray2.h: ========== class dyck_gray2; // Loopless generation of k-ary Dyck words (same as: k-ary trees) // (two-close Gray code with homogeneous moves). // Adapted from: // Vincent Vajnovszki, Timothy R. Walsh: // "A loop-free two-close Gray-code algorithm for listing k-ary Dyck words", // Journal of Discrete Algorithms, vol.4, no.4, pp.633-648, (December-2006) // ========== HEADER FILE src/comb/dyck-pref.h: ========== class dyck_pref; // k-ary Dyck words via prefix shifts. // Representation as delta set. // Algorithm "coolkat" as given (left in figure "Algorithms 1") in // Stephane Durocher, Pak Ching Li, Debajyoti Mondal, Aaron Williams: // "Ranking and Loopless Generation of k-ary Dyck Words in Cool-lex Order", // The 22nd International Workshop on Combinatorial Algorithms, // Victoria, Canada, IWOCA, (2011). // ========== HEADER FILE src/comb/dyck-rgs-subset-lex.h: ========== class dyck_rgs_subset_lex; // Restricted growth strings (RGS) for k-ary Dyck words, that is, // strings a[0,1,...,n-1] where a[0]=0 and a[j] <= a[j-1] + (k-1). // Subset-lex order. // Loopless algorithm for predecessor (method prev()). // See Joerg Arndt, Subset-lex: did we miss an order?, (2014) // http://arxiv.org/abs/1405.6503 // ========== HEADER FILE src/comb/dyck-rgs.h: ========== class dyck_rgs; // Restricted growth strings (RGS) corresponding to k-ary Dyck words (i=k-1): // strings s[0,...,n-1] such that s[j] <= s[j-1] + i // Lexicographic order. // Number of RGS is binomial(i*n,n)/((i-1)*n+1), (Catalan numbers for i=1). // ========== HEADER FILE src/comb/endo-enup.h: ========== static inline ulong next_endo(ulong x, ulong m); // Return next number in endo order // (endo := "Even Numbers DOwn, odd numbers up") // m := max digit // m: endo sequence // 1: 1 0 // 2: 1 2 0 // 3: 1 3 2 0 // 4: 1 3 4 2 0 // 5: 1 3 5 4 2 0 // 6: 1 3 5 6 4 2 0 // 7: 1 3 5 7 6 4 2 0 // 8: 1 3 5 7 8 6 4 2 0 // 9: 1 3 5 7 9 8 6 4 2 0 // The routine computes one for the input zero (wrap around). static inline ulong next_enup(ulong x, ulong m); // Return next number in enup order // (enup := "Even Numbers UP, odd numbers down") // enup order is reversed endo order. // m := max digit // m: enup sequence // 1: 0 1 // 2: 0 2 1 // 3: 0 2 3 1 // 4: 0 2 4 3 1 // 5: 0 2 4 5 3 1 // 6: 0 2 4 6 5 3 1 // 7: 0 2 4 6 7 5 3 1 // 8: 0 2 4 6 8 7 5 3 1 // 9: 0 2 4 6 8 9 7 5 3 1 // The routine computes zero for the input one (wrap around). static inline ulong prev_endo(ulong x, ulong m); // Return previous number in endo order // Inverse of next_endo() static inline ulong prev_enup(ulong x, ulong m); // Return previous number in enup order // Inverse of next_enup() static inline ulong endo_num(ulong x, ulong m); // Return the x-th number in endo order. // m := max digit // For example, with m=5: // x: 0 1 2 3 4 5 // r: 1 3 5 4 2 0 // Must have x<=m. static inline ulong endo_idx(ulong x, ulong m); // Inverse of endo_num() // For example, with m=5: // x: 0 1 2 3 4 5 // r: 5 0 4 1 3 2 // Must have x<=m. static inline ulong enup_num(ulong x, ulong m); // Return the x-th number in enup order. // m := max digit // For example, with m=5: // x: 0 1 2 3 4 5 // r: 0 2 4 5 3 1 // Must have x<=m. static inline ulong enup_idx(ulong x, ulong m); // Inverse of enup_num() // m := max digit // For example, with m=5: // x: 0 1 2 3 4 5 // r: 0 5 1 4 2 3 // Must have x<=m. // ========== HEADER FILE src/comb/fact2num.h: ========== // ----- SRCFILE=src/comb/fact2num.cc: ----- ulong ffact2num(const ulong *fc, ulong n); // Convert (falling) factorial in fc[] to number. // Note: n!-1 must fit into a ulong ==> only good for _tiny_ n bool num2ffact(ulong x, ulong *fc, ulong n); // Convert number x to (falling) factorial in fc[0,...,n-1]. // Return whether x fits into fc[] ulong rfact2num(const ulong *fc, ulong n); // Convert (rising) factorial in fc[] to number. // Note: n!-1 must fit into a ulong ==> only good for _tiny_ n bool num2rfact(ulong x, ulong *fc, ulong n); // Convert number x to (rising) factorial in fc[0,...,n-1]. // Return whether x fits into fc[] // ========== HEADER FILE src/comb/fact2num2perm.h: ========== // all conversions between factorials, permutations, and numbers // ========== HEADER FILE src/comb/fact2perm.h: ========== // ----- SRCFILE=src/comb/fact2perm.cc: ----- void perm2ffact(const ulong *x, ulong n, ulong *fc); // Convert permutation in x[0,...,n-1] into // the (n-1) digit falling factorial representation in fc[0,...,n-2]. // We have: fc[0] k where x[j] < x[k]. void ffact2perm(const ulong *fc, ulong n, ulong *x, bool iq/*=true*/); // Inverse of perm2ffact(): // Convert the (n-1) digit falling factorial representation // in fc[0,...,n-2] into a permutation in x[0,...,n-1]. // Must have: fc[0] x[k]. void rfact2perm(const ulong *fc, ulong n, ulong *x, bool iq/*=true*/); // Inverse of perm2rfact(): // Convert the (n-1) digit rising factorial representation in fc[0,...,n-2]. // into permutation in x[0,...,n-1] // Must have: fc[0]<2, fc[1]<3, ..., fc[n-2]= 2 and 1 <= b_den < b_num. // ========== HEADER FILE src/comb/gray-compare.h: ========== inline int gray_compare(const Type *a, ulong na, const Type *b, ulong nb); // Compare a[] and b[] with respect to Gray code order. // Return +1 if a[] >> b[], -1 if a[] << b[], 0 if a[]==b[]. // ========== HEADER FILE src/comb/gray-cycle-leaders.h: ========== class gray_cycle_leaders; // Generate cycle leaders for Gray permutation // where highest bit is at position ldn. // ========== HEADER FILE src/comb/hilbert-ndim-rec.h: ========== class hilbert_ndim_rec; // Fred Lunnon's recursive algorithm to convert linear coordinate // into coordinates of d-dimensional Hilbert curve. // Note: the iterative version (class hilbert_ndim) is much faster. // ========== HEADER FILE src/comb/hilbert-ndim.h: ========== class hilbert_ndim; // Fred Lunnon's iterative algorithm to convert linear coordinate // into coordinates of d-dimensional Hilbert curve. // ========== HEADER FILE src/comb/id-tree-lev-seq.h: ========== class id_tree_lev_seq; // Level sequences for unordered rooted identity trees. // Cf. OEIS sequence A004111. // ========== HEADER FILE src/comb/involution-zero-map-rgs.h: ========== class involution_zero_map_rgs; // Restricted growth strings (RGS): // each digit a[k] is either zero or a[k] < k, a[a[k]] == 0, // and there is at most one digit a[k] in the RGS. // Same as: maps from {1, 2, 3, ..., n} to {0, 1, 2, 3, ..., n} // such that f(x) < x and f(f(x)) == 0 and there is no t!=x with f(t) = f(x). // Lexicographic order. // Cf. OEIS sequence A000085. // ========== HEADER FILE src/comb/is-arrangement-rgs.h: ========== inline bool is_arrangement_rgs(const ulong *a, ulong n); // Return whether a[] is a valid arrangement RGS: // every digit is at most 1 + the number of nonzero digits in the prefix. // ========== HEADER FILE src/comb/is-ascent-rgs.h: ========== inline bool is_ascent_rgs(const ulong *a, ulong n); // Return whether a[] is a valid ascent sequence. // An ascent sequence is a sequence [d(1), d(2), ..., d(n)] where d(1)=0, // d(k)>=0, and d(k) <= 1 + asc([d(1), d(2), ..., d(k-1)]) and asc(.) // counts the number of ascents of its argument. // See OEIS sequence A022493. inline bool is_weak_ascent_rgs(const ulong *a, ulong n); // Return whether a[] is a valid weak ascent sequence. // An weak ascent sequence is a sequence [d(1), d(2), ..., d(n)] where // d(1)=0, d(k)>=0, and d(k) <= 1 + asc([d(1), d(2), ..., d(k-1)]) // and asc(.) counts the number of weak ascents d(j) >= d(j-1) of its argument. // See OEIS sequence A336070. // ========== HEADER FILE src/comb/is-catalan-path.h: ========== inline bool is_catalan_path(const ulong *x, ulong n2); // Return whether x[0..n] is a valid Catalan path, i.e., // x[0] = 0, abs(x[j]-x[j-1]) == 1, and x[n-1] <= 1. inline bool is_catalan_flat_path(const ulong *x, ulong n2); // Return whether x[0..n] is a valid Catalan (flat) path, i.e., // x[0] = 0, abs(x[j]-x[j-1]) <= 1, and x[n-1] <= 1. // ========== HEADER FILE src/comb/is-catalan-rgs.h: ========== inline bool is_catalan_rgs(const ulong *rgs, ulong n); // Return whether rgs[] is a valid Catalan RGS, that is, // a string a[0,1,...,n-1] where a[0]=0 and a[k] <= a[k-1] + 1. inline bool is_rev_catalan_rgs(const ulong *rgs, ulong n); // Return whether reversed rgs[] is a valid Catalan RGS. // ========== HEADER FILE src/comb/is-catalan-step-rgs.h: ========== inline bool is_catalan_step_rgs(const ulong *rgs, ulong n); // Return whether rgs[] is a valid Catalan (step-)RGS. // The RGS are a[] such that a[k] >= a[k-1] (weakly ascending) and a[k]<=k. // The RGS describe lattice paths from (0,0) to (n,n) with steps // (+1,0) and (+1,+1) that do not go below the diagonal. // Same as: rising factorial numbers where the digits are sorted. // ========== HEADER FILE src/comb/is-cayley-perm.h: ========== inline bool is_cayley_perm(const ulong *a, ulong n, bitarray *B); // Return whether a[] is a valid Cayley permutation: // all elements from 0 to the maximum value occur at least once. // ========== HEADER FILE src/comb/is-change-rgs.h: ========== inline bool is_change_rgs(const ulong *a, ulong n); // Return whether a[] is a valid change sequence. // A change sequence is a sequence [d(1), d(2), ..., d(n)] where d(1)=0, // d(k)>=0, and d(k) <= 1 + chg([d(1), d(2), ..., d(k-1)]) and chg(.) // counts the number of changes of its argument. // See OEIS sequence A000522. // ========== HEADER FILE src/comb/is-composition-nz.h: ========== inline bool is_composition_nz(const ulong *a, ulong m, ulong n); // Return whether a[0, 1, ..., m-1] is a valid composition of n // into non-zero parts. // ========== HEADER FILE src/comb/is-descent-rgs.h: ========== inline bool is_descent_rgs(const ulong *a, ulong n); // Return whether a[] is a valid descent sequence. // A descent sequence is a sequence [d(1), d(2), ..., d(n)] where d(1)=0, // d(k)>=0, and d(k) <= 1 + desc([d(1), d(2), ..., d(k-1)]) and desc(.) // counts the number of descents of its argument. // ========== HEADER FILE src/comb/is-dyck-rgs.h: ========== inline bool is_dyck_rgs(const ulong *rgs, ulong n, ulong i=1); // Return whether rgs[] is a valid (i+1)-ary Dyck word, that is, // a word a[0,1,...,n-1] where a[0]=0 and a[j] <= a[j-1] + i. // ========== HEADER FILE src/comb/is-isoscent-rgs.h: ========== inline bool is_isoscent_rgs(const ulong *a, ulong n); // Return whether a[] is a valid isoscent sequence. // A isoscent sequence is a sequence [d(1), d(2), ..., d(n)] where d(1)=0, // d(k)>=0, and d(k) <= 1 + eq([d(1), d(2), ..., d(k-1)]) and eq(.) // counts the number of isoscents of its argument. // ========== HEADER FILE src/comb/is-mixedradix-num.h: ========== inline bool is_mixedradix_num(const ulong *a, ulong n, const ulong *m1); // Return whether a[j] <= m1[j] for 0<=j= sum(j=k+1..m-1, a[j] ). inline bool is_strongly_decreasing(const Type *a, ulong m); // Return whether a[k] > sum(j=k+1..m-1, a[j] ) inline bool is_nonsquashing_asc(const Type *a, ulong m); // Return whether a[k] >= sum(j=0..k-1, a[j] ) inline bool is_strongly_increasing(const Type *a, ulong m); // Return whether a[k] > sum(j=0..k-1, a[j] ) // ========== HEADER FILE src/comb/is-paren-position-word.h: ========== inline bool is_paren_position_word(const Type *x, ulong n); // Return whether x[] is a valid word of parenthesis positions. // ========== HEADER FILE src/comb/is-paren-string.h: ========== inline bool is_paren_string(const Type *str, ulong n2); // Return whether parenthesis string is valid. // Works for any pair of symbols. inline bool is_paren_string(const bitarray &B); // ========== HEADER FILE src/comb/is-partition-asc.h: ========== inline bool is_partition_asc(const ulong *a, ulong m, ulong n); // Return whether a[0, 1, ..., m-1] is a valid partition of n // represented as a weakly ascending list of parts. // ========== HEADER FILE src/comb/is-partition-desc.h: ========== inline bool is_partition_desc(const ulong *a, ulong m, ulong n); // Return whether a[0, 1, ..., m-1] is a valid partition of n // represented as a weakly descending list of parts. // ========== HEADER FILE src/comb/is-partition-rgs.h: ========== inline bool is_partition_rgs(const Type *f, ulong n, bool dq=true); // Return whether sequence is rgs for partition. // dq determines whether the RGS is for a partition as descending list. // ========== HEADER FILE src/comb/is-schroeder-path.h: ========== inline bool is_schroeder_path(const ulong *x, ulong n2); // Return whether x[0..n2] is a valid Schroeder path, i.e., // whether it is a valid Motzkin path and // all horizontal stretches have even length. // ========== HEADER FILE src/comb/is-schroeder-rgs.h: ========== inline bool is_schroeder_rgs(const ulong *a, ulong n, ulong m0); // Return whether a[] is a valid Schroeder RGS: // a Schroeder RGS is a word a[0,1,2,...,n-1] where // a[k] <= k + 1 (rising factorial numbers), // a[0] <= m0, and a[k] + 1 >= max(j=1..k-1, a[j]) // m0 == 0 ==> little Schroeder numbers, A001003 // m0 == 1 ==> large Schroeder numbers, A006318 // ========== HEADER FILE src/comb/is-setpart-ccf-perm.h: ========== inline bool is_setpart_ccf_perm(ulong const *f, ulong n); // Return whether f[], read as canonical cyle form (CCF) of a permutation // is valid as a set partition of the form // (a1, a2, ..., ai), (b1, b2, ..., bj), (c1, c2, ..., ck), ... // such that ai < bj < ck < ... // and the last element in each group is the minimal element and // the other elements in each group appear in increasing order. // ========== HEADER FILE src/comb/is-setpart-rgs.h: ========== inline bool is_setpart_rgs(const ulong *s, ulong n); // Return whether s[0,1,...,n-1] is a valid RGS of a set partition: // a string s[0, 1, ..., n-1] such that // s[k] <= max(s[0], s[1], ..., s[k-1]) + 1. // ========== HEADER FILE src/comb/is-shifted-young-tab-rgs.h: ========== inline bool is_delayed_young_tab_rgs(const ulong *A, ulong n, ulong h, ulong s=1); // Return whether the first occurence of a digit d is // preceded by at least s+1 occurences of d-1. // Always true for s==0. inline bool is_falling_young_tab_rgs(const ulong *P, ulong h, ulong s=1); // Return whether falling multiplicities with difference at least s. // Same as: allowing only partitions into distinct parts (with diff>=s). // Always true for s==0. inline bool is_shifted_young_tab_rgs(const ulong *A, const ulong *P,; ulong n, ulong h, ulong s=1) // Return whether still valid if row k is shifted to the right // by s positions with respect to row k-1. // Always true for s==0. // ========== HEADER FILE src/comb/is-smooth.h: ========== inline bool is_left_smooth(const ulong *a, ulong n, ulong d=1); // Return whether a[] has maximal up-step <= d. inline bool is_right_smooth(const ulong *a, ulong n, ulong d=1); // Return whether a[] has maximal down-step <= d. inline bool is_smooth(const ulong *a, ulong n, ulong d=1); // Return whether a[] is smooth, that is, abs(a[k] - a[k-1]) <= d inline bool is_left_2smooth(const ulong *a, ulong n); // Return whether a[] is left-2smooth, that is, // the maximal up-step is <= 1, // and there are no consecutive up-steps. // ========== HEADER FILE src/comb/is-sorts-in-runs-sorted.h: ========== inline bool is_sorts_in_runs_sorted_asc(const ulong *A, const ulong *S, ulong m); // For compositions and partitions with parts A[] of sorts S[], // return whether for all runs of equal parts // the sorts of parts are sorted (ascending order). inline bool is_sorts_in_runs_sorted_desc(const ulong *A, const ulong *S, ulong m); // For compositions and partitions with parts A[] of sorts S[], // return whether for all runs of equal parts // the sorts of parts are sorted (descending order). // ========== HEADER FILE src/comb/is-stack-sortable.h: ========== bool is_stack_sortable(const Type *a, ulong n); // Return whether array a[] is stack-sortable. // Routine also works for non-distinct values. // // Among the permutations of n elements the stack-sortable ones are // counted by the Catalan numbers (OEIS sequence A000108), these // are the 231-avoiding permutations. // See: // Mireille Bousquet-Melou: // Sorted and/or sortable permutations, // Discrete Mathematics, vol.225, no.1-3, pp.25-50, (2000). // ========== HEADER FILE src/comb/is-symmetric.h: ========== inline bool is_symmetric(const Type *a, ulong n); // Return whether a[] is symmetric. // ========== HEADER FILE src/comb/is-unimodal.h: ========== inline bool is_weakly_unimodal(const Type *f, ulong n); // Return whether sequence is weakly unimodal. inline bool is_strongly_unimodal(const Type *f, ulong n); // Return whether sequence is strongly unimodal. // ========== HEADER FILE src/comb/is-young-tab-rgs.h: ========== inline bool is_young_tab_rgs(const ulong *x, ulong n, ulong *st, bool cst=false); // Return whether x[0..n-1] is a valid restricted growth strings (RGS) // for a standard Young tableau: the k-th occurrence of a digit d must // precede the k-th occurrence of d-1. // If cst is set then st[] should contain the partition corresponding // to the digit statistics. // Must have st a pointer to (at least) n elements, regardless of cst. // ========== HEADER FILE src/comb/is-zero-map-rgs.h: ========== inline bool is_zero_map_rgs(const ulong *a, ulong n); // Return whether a[] is a zero-map RGS: // each digit a[k] is either zero or the (one-based) index // of a zero in the prefix. // RGS is for set paritions, cf. A000110. inline bool is_zero_map_rgs(const ulong *a, ulong n, ulong s, ulong *t); // Return whether a[] is a zero-map RGS with at most s repeats: // each digit a[k] is either zero or the (one-based) index // of a zero in the prefix and there are at most s digits pointing // to the same zero in the prefix. // ========== HEADER FILE src/comb/isoscent-rgs.h: ========== class isoscent_rgs; // Isoscent sequences (restricted growth strings, RGS). // An isoscent sequence is a sequence [d(1), d(2), ..., d(n)] where // d(1)=0, d(k)>=0, and d(k) <= 1 + eq([d(1), d(2), ..., d(k-1)]) // where eq(.) counts the number of flat steps of its argument. // Lexicographic order. // See OEIS sequence A000110. // ========== HEADER FILE src/comb/kperm-gray.h: ========== class kperm_gray; // Gray code for k-permutations of n elements. // Same as: k-prefixes of permutations of n elements. // Same as: arrangements of k out of n elements. // CAT algorithm based on mixed radix Gray code // for the factorial number system (falling base). // ========== HEADER FILE src/comb/kperm-lex.h: ========== class kperm_lex; // k-permutations of n elements in lexicographic order. // Same as: k-prefixes of permutations of n elements. // Same as: arrangements of k out of n elements. // ========== HEADER FILE src/comb/ksubset-gray.h: ========== class ksubset_gray; // k-subsets (kmin<=k<=kmax) of the set {1,2,...,n} // in minimal-change (Gray code) order. // Algorithm following Jenkyns ("Loopless Gray Code Algorithms") // Limitation: cannot mix calls to next() and prev(). // ========== HEADER FILE src/comb/ksubset-lex.h: ========== class ksubset_lex; // Nonempty subsets of the set {0,1,2,...,n-1} with at most k elements. // Representation as list of parts. // Subset-lex order. // Loopless generation. // See OEIS sequence A117670. // See Joerg Arndt, Subset-lex: did we miss an order?, (2014) // http://arxiv.org/abs/1405.6503 // ========== HEADER FILE src/comb/ksubset-rec.h: ========== class ksubset_rec; // k-subsets where kmin<=k<=kmax in various orders. // Recursive CAT algorithm. // ========== HEADER FILE src/comb/ksubset-twoclose-list-rec.h: ========== class ksubset_twoclose_list_rec; // k-subsets (kmin<=k<=kmax) in a two-close order with homogeneous moves. // Representation as list of elements. // Recursive algorithm. // ========== HEADER FILE src/comb/ksubset-twoclose-list.h: ========== class ksubset_twoclose_list; // k-subsets (0 <= kmin <= k <= kmax <= n) // in a two-close order with homogeneous moves. // Representation as list of elements. // ========== HEADER FILE src/comb/ksubset-twoclose-rec.h: ========== class ksubset_twoclose_rec; // k-subsets (kmin<=k<=kmax) in a two-close order with homogeneous moves. // Recursive algorithm. // ========== HEADER FILE src/comb/ksubset-twoclose.h: ========== class ksubset_twoclose; // k-subsets (0 <= kmin <= k <= kmax <= n) // in a two-close order with homogeneous moves. // ========== HEADER FILE src/comb/lex-compare.h: ========== inline int lex_compare(const Type *a, ulong na, const Type *b, ulong nb); // Compare a[] and b[] lexicographically. // Return +1 if a[] >> b[], -1 if a[] << b[], 0 if a[]==b[]. // ========== HEADER FILE src/comb/lindenmayer-system.h: ========== // ========== HEADER FILE src/comb/lyndon-factorization.h: ========== inline ulong lyndon_factorization(const Type * W, ulong n, ulong * F); // Standard (Chen, Fox, Lyndon)-factorization of the word W. // // Return the number of factors and write to F[] the positions // beyond the ends of the factors. // // Algorithm as in // Jean-Pierre Duval, "Factorizing words over an ordered alphabet", // Journal of Algorithms, vol. 4, no. 4, pp. 363-381, (December-1983). // // Code adapted from JavaScript by Lloyd Allison, see // http://www.allisons.org/ll/AlgDS/Strings/Factors/ ulong max_lyndon_prefix_len(const Type *W, ulong n); // Return the length of the maximal prefix of the word W that is a // Lyndon word. // The code is a specialization of lyndon_factorization(W, n, F) // returning just when the first entry in F would have been made. inline bool is_lyndon_word(const Type *W, ulong n); // Return whether the word W is a Lyndon word. // ========== HEADER FILE src/comb/lyndon-words-prefix-cond.h: ========== class lyndon_words_prefix_cond : private lyndon_words; // Lyndon words up to length n with restricted prefixes. // ========== HEADER FILE src/comb/lyndon-words.h: ========== class lyndon_words; // Lyndon words up to length n. // Duval's algorithm. // ========== HEADER FILE src/comb/map23-rgs.h: ========== class map23_rgs; // Restricted growth strings (RGS) for maps // f: [n] -> [n] with f(x)<=x and f(f(x)) == f(f(f(x))). // Lexicographic order. // Cf. OEIS sequence A187761. // ========== HEADER FILE src/comb/max-subrange-sum.h: ========== inline Type max_subrange_sum(Type * const x, ulong n); // Return largest sum of any (contiguous) subrange. // From: Jon Bentley, Programming pearls, Addison-Wesley, 1984, p. 74. // Cf. https://en.wikipedia.org/wiki/Maximum_subarray_problem#Kadane's_algorithm // Cf. https://leetcode.com/problems/maximum-subarray/discuss/447660/Java-Full-Explanations-DPKadane's-plus-max-subarray-indices-and-Divide-and-Conquer // ========== HEADER FILE src/comb/mixedradix-aux.h: ========== // ----- SRCFILE=src/comb/mixedradix-init.cc: ----- void mixedradix_init(ulong n, ulong mm, const ulong *m, ulong *m1); // aux // Auxiliary function used to initialize vector of nines in mixed radix classes. // ----- SRCFILE=src/comb/mixedradix2num.cc: ----- ulong mixedradix2num(const ulong *x, const ulong *m1, ulong n); // Convert n-digit mixed radix number in x[] to (unsigned) integer. // Radices minus one (that is, "nines") must be given in m1[]. void num2mixedradix(ulong N, ulong *x, const ulong *m1, ulong n); // Convert N to n-digit mixed radix number in x[]. // Radices minus one (that is, "nines") must be given in m1[]. // ========== HEADER FILE src/comb/mixedradix-endo-gray.h: ========== class mixedradix_endo_gray; // Gray code for mixed radix numbers in endo order. // (endo := "Even Numbers Down, Odd (numbers up)") // CAT algorithm. // ========== HEADER FILE src/comb/mixedradix-endo.h: ========== class mixedradix_endo; // Mixed radix counting in endo order. // (endo := "Even Numbers Down, Odd (numbers up)") // ========== HEADER FILE src/comb/mixedradix-fixed-content-lex.h: ========== class mixedradix_fixed_content_lex; // Mixed radix counting, fixed content. // Equivalently, subsets of a multiset with a fixed number of elements. // Lexicographic order. // ========== HEADER FILE src/comb/mixedradix-fixed-content.h: ========== class mixedradix_fixed_content; // Mixed radix numbers with prescribed content (sum of digits s). // Same as: s-combinations of a multiset. // Same as: compositions of s with prescribed maximum at each place. // ========== HEADER FILE src/comb/mixedradix-gray.h: ========== class mixedradix_gray; // Gray code for mixed radix numbers. // CAT algorithm. // ========== HEADER FILE src/comb/mixedradix-gslex-alt.h: ========== class mixedradix_gslex_alt; // Mixed radix numbers in alternative gslex (generalized subset-lex) order. // ========== HEADER FILE src/comb/mixedradix-gslex.h: ========== class mixedradix_gslex; // Mixed radix numbers in gslex (generalized, subset-lexicographic) order. // Loopless generation. // ========== HEADER FILE src/comb/mixedradix-modular-gray.h: ========== class mixedradix_modular_gray; // Modular Gray code for mixed radix numbers. // Constant amortized time (CAT) algorithm. // ========== HEADER FILE src/comb/mixedradix-naf-gray.h: ========== class mixedradix_naf_gray; // Gray code for mixed radix non-adjacent forms (NAF). // ========== HEADER FILE src/comb/mixedradix-naf-subset-lex.h: ========== class mixedradix_naf_subset_lex; // Mixed radix non-adjacent forms (NAF), subset-lex order. // Loopless generation. // ========== HEADER FILE src/comb/mixedradix-naf.h: ========== class mixedradix_naf; // Mixed radix non-adjacent forms (NAF), counting order. // ========== HEADER FILE src/comb/mixedradix-prefix-cond.h: ========== class mixedradix_prefix_cond; // Mixed radix counting with restricted prefixes. // ========== HEADER FILE src/comb/mixedradix-rev.h: ========== class mixedradix_rev; // Mixed radix counting. // Digits in reversed order as in class mixedradix. // ========== HEADER FILE src/comb/mixedradix-sl-gray-compare.h: ========== inline int mixedradix_sl_gray_compare(const Type *a, const Type *b, ulong n,; const ulong *m1) // Compare a[] and b[] with respect to SL-Gray order. // Return +1 if a[] >> b[], -1 if a[] << b[], 0 if a[] == b[]. // m1[] must be the array of nines. // ========== HEADER FILE src/comb/mixedradix-sl-gray-rank.h: ========== class mixedradix_sl_gray_rank; // Ranking and unranking function for SL-Gray order. // ========== HEADER FILE src/comb/mixedradix-sl-gray.h: ========== class mixedradix_sl_gray; // Mixed radix numbers in a minimal-change order // related so subset-lex order ("SL-Gray" order). // See Joerg Arndt, Subset-lex: did we miss an order?, (2014) // http://arxiv.org/abs/1405.6503 // ========== HEADER FILE src/comb/mixedradix-subset-lex-rank.h: ========== class mixedradix_subset_lex_rank; // Ranking and unranking function for subset-lex order. // ========== HEADER FILE src/comb/mixedradix-subset-lex.h: ========== class mixedradix_subset_lex; // Mixed radix numbers in subset-lex order. // Successive numbers differ in at most three digits. // See Joerg Arndt, Subset-lex: did we miss an order?, (2014) // http://arxiv.org/abs/1405.6503 // ========== HEADER FILE src/comb/mixedradix-subset-lexrev.h: ========== class mixedradix_subset_lexrev; // Mixed radix numbers in subset-lexrev order. // Successive numbers differ in at most three digits. // See Joerg Arndt, Subset-lex: did we miss an order?, (2014) // http://arxiv.org/abs/1405.6503 // ========== HEADER FILE src/comb/mixedradix.h: ========== class mixedradix; // Mixed radix counting. // CAT algorithm. // ========== HEADER FILE src/comb/monotonic-gray.h: ========== // ----- SRCFILE=src/comb/monotonic-gray.cc: ----- void monotonic_gray_delta(unsigned char *d, ulong ldn); // Write the delta sequence for the Savage-Winkler monotonic Gray path // into the array d[]. // Algorithm as given in Knuth, TAOCP vol.4 // (exercise 73, fascicle 2A, 7.2.1.1: "Generating all n-tuples"). void monotonic_gray(ulong *g, ulong ldn); // Write the monotonic (Savage-Winkler) Gray path // into g[0..N-1] (N=2**ldn). // ========== HEADER FILE src/comb/motzkin-nonflat-rgs-lex.h: ========== class motzkin_nonflat_rgs_lex; // Motzkin (nonflat) restricted growth strings (RGS), lexicographic order. // Same as: Catalan RGS without flat steps. // Cf. OEIS sequences A086246 and A001006. // The number of length-n RGS is // 1, 1, 1, 2, 4, 9, 21, 51, 127, 323, 835, 2188, 5798, 15511, 41835, ... // G.f. is (1+x-sqrt(1-2*x-3*x^2))/(2*x) // ========== HEADER FILE src/comb/motzkin-path-lex.h: ========== class motzkin_path_lex; // Motzkin paths in lexicographic order, CAT algorithm. // Steps are +1, 0, -1 (up, horizontal, down), // the first and last elements are 0, // and all elements are non-negative. // Cf. OEIS sequence A001006. // ========== HEADER FILE src/comb/motzkin-rgs-lex.h: ========== class motzkin_rgs_lex; // Motzkin restricted growth strings (RGS): // words a[0,1,...,n-1] where a[0] = 0, a_[k] <= a[k-1] + 1, // and there are no two consecutive up-steps. // Lexicographic order. // Cf. OEIS sequence A001006. // ========== HEADER FILE src/comb/motzkin-step-rgs-lex.h: ========== class motzkin_step_rgs_lex; // Motzkin step RGS (restricted growth strings), lexicographic order. // RGS are a[] such that a[k] >= a[k-1] (weakly ascending), a[k]<=k, and // a[k] - a[k-1] != 1 (no increments by 1). // Same as: rising factorial numbers where the digits are sorted // where increments by 1 are disallowed. // Cf. OEIS sequence A001006. // ========== HEADER FILE src/comb/mpartition.h: ========== class mpartition; // Partitions into m parts. // Representation as list of parts in weakly ascending order. // Cf. OEIS sequence A008284. // Same functionality as class mpartition2, which // avoids the auxiliary array s[]. // ========== HEADER FILE src/comb/mpartition2.h: ========== class mpartition2; // Partitions into m parts. // Representation as list of parts in weakly ascending order. // Cf. OEIS sequence A008284. // Same functionality as class mpartition, this // implementation avoids the auxiliary array s[]. // ========== HEADER FILE src/comb/mset-kperm-lex.h: ========== class mset_kperm_lex : public mset_perm_lex; // k-permutations of a multiset in lexicographic order. // ========== HEADER FILE src/comb/mset-perm-gray.h: ========== class mset_perm_gray; // Multiset permutations in minimal-change order (Fred Lunnon's Gray code). //. // Adaptation of Java code by Fred Lunnon. // Original documentation at end of file. // ========== HEADER FILE src/comb/mset-perm-lex-rec.h: ========== class mset_perm_lex_rec; // Multiset permutations in lexicographic order, recursive algorithm. // ========== HEADER FILE src/comb/mset-perm-lex.h: ========== class mset_perm_lex; // Multiset permutations in lexicographic order, iterative algorithm. // ========== HEADER FILE src/comb/mset-perm-pref.h: ========== class mset_perm_pref; // Multiset permutations via prefix shifts ("cool-lex" order). // See // Aaron Williams: Loopless Generation of Multiset Permutations using // a Constant Number of Variables by Prefix Shifts, // ACM-SIAM Symposium on Discrete Algorithms (SODA09), (2009). // ========== HEADER FILE src/comb/msetpart.h: ========== class msetpart; // Multiset partitions. // Knuth's algorithm M, section 7.1.2.5, p.429-430, Vol.4A, TAOCP // OEIS sequences: // A020555: content 2, 2, 2, ..., 2 (n times) // A322487: content 3, 3, 3, ..., 3 (n times) // A358781: content 4, 4, 4, ..., 4 (n times) // A322488: content n, n, n, ..., n (n times) // A317829: content 1, 2, 3, ..., n // A000110: content 1, 1, 1, ..., 1 (n times): set partitions // A000041: content n: integer partitions // ========== HEADER FILE src/comb/necklace.h: ========== class necklace; // Generate necklaces, iterative algorithm. // ========== HEADER FILE src/comb/num-compositions.h: ========== class num_compositions; // Table of number of compositions: nc[n-1][k-1] = binomial(n+k-1, n). // Used by class composition_rank. // ========== HEADER FILE src/comb/num-necklaces.h: ========== // num_necklaces_tab[n] == number of binary n-bit necklaces // num_lyndon_tab[n] == number of binary n-bit Lyndon words // ========== HEADER FILE src/comb/num2perm.h: ========== // ----- SRCFILE=src/comb/num2perm.cc: ----- void num2perm_rfact(ulong x, ulong *f, ulong n); // Create permutation number x according to (rising factorial) unrank. ulong perm2num_rfact(const ulong *f, ulong n); // Inverse of num2perm_rfact() void num2perm_ffact(ulong x, ulong *f, ulong n); // Create permutation number x according to (falling factorial) unrank. ulong perm2num_ffact(const ulong *f, ulong n); // Inverse of num2perm_ffact() void num2perm_swp(ulong x, ulong *f, ulong n); // Create permutation number x according to (rising factorial) unrank by swaps. ulong perm2num_swp(const ulong *f, ulong n); // Inverse of num2perm_swp() ulong permlex2num(const ulong *f, ulong n); // The following function computes the rank of the given permutation // corresponding to lexicographic order: // 1, 2, ..., n-1, n is index 0 // 1, 2, ..., n, n-1 is index 1 // n, n-1, ..., 2, 1 is index n! -1 // The actual values of the elements are immaterial, only the relative // ordering of the values is used. // f[] is the array of elements of length n. // Note 1: complexity is n*n // Note 2: n!-1 must fit into a ulong ==> only good for _tiny_ n // ========== HEADER FILE src/comb/ordered-tree-branches.h: ========== class ordered_tree_branches; // Ordered trees with n non-root nodes by branches: // branch lengths are a composition of n (array a[]) and // branch heights (height of base of branch, array b[]) are such that // b[j] < a[j-1] + b[j-1] for j>=2 (and b[1]=0). // ========== HEADER FILE src/comb/ordered-tree-branching-seq.h: ========== class ordered_tree_branching_seq; // Branching sequences for ordered rooted trees: // words [b(0), b(1), ..., b(n)] with b(n)=0, sum(j=0..n, b(j)) = n, // and sum(j=0..k, b(j)-1 ) >= 0 for k= 1 for k >= 1, // and a[k] <= a[k-1] + 1. // Lexicographic order. // The number of length-n RGS is (OEIS sequence A000108) // 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, ... // ========== HEADER FILE src/comb/paren-gray.h: ========== class paren_gray; // Parentheses strings in a homogeneous minimal-change order. // Algorithm from // Tadao Takaoka, Stephen Violich: // "Combinatorial Generation by Fusing Loopless Algorithms" // In: {Computing: The Australasian Theory Symposium (CATS2006)}, // Hobart, Australia. Conferences in Research and Practice in // Information Technology (CRPIT), vol.~51. // Barry Jay, Joachim Gudmundsson, (eds.), (2006). // ========== HEADER FILE src/comb/paren-lex.h: ========== class paren_lex; // Parentheses strings, lexicographic order. // Representation as list of positions of opening parenthesis. // ========== HEADER FILE src/comb/paren-pref.h: ========== class paren_pref; // All strings of t ones and s zeros (t>=s>0) where the number of // zeros in any prefix does not exceed the number of ones. // For t==s: well-formed parentheses strings by prefix shifts. //. // Loopless algorithm as given in // Frank Ruskey, Aaron Williams: // "Generating Balanced Parentheses and Binary Trees by Prefix Shifts" // CATS 2008, Computing: The Australasian Theory Symposium, // Wollongong, Australia, (2008) // ========== HEADER FILE src/comb/paren-string-to-rgs.h: ========== // ----- SRCFILE=src/comb/paren-string-to-rgs.cc: ----- void rgs_to_paren_string(const ulong *rgs, ulong n, char *str, bool rq=false); // Convert restricted growth string (Catalan-RGS) to paren-string. // If rq is set then the reversed paren string is computed. bool paren_string_to_rgs(const char *str, ulong *rgs); // Convert paren-string to RGS, // return whether parenthesis string is valid. // rgs[j] = number of unclosed open parenthesis when // the j-th opening is found (j>=0). // If rq is set then the RGS for the reversed paren string is computed. void rgs_to_paren_bit_string(const ulong *rgs, ulong n, char *str, bool rq=false); // Convert restricted growth string (Catalan-RGS) to paren-bit-string. // If rq is set then the reversed paren string is computed. bool paren_bit_string_to_rgs(const char *str, ulong *rgs); // Convert paren-bit-string to RGS. // Return whether parenthesis string is valid. // If rq is set then the RGS for the reversed paren string is computed. // ========== HEADER FILE src/comb/paren.h: ========== class paren; // Parentheses strings, co-lexicographic order. // Representation as list of positions of opening parenthesis. // ========== HEADER FILE src/comb/partition-2fall-asc-subset-lex.h: ========== class partition_2fall_asc_subset_lex; // Partitions of n is a partition a[1] + a[2] + ... + a[m] = n // such that a[k] >= 2 * a[k-1]. // Representation as weakly ascending list of parts. // Subset-lex order. // Loopless algorithm. // Cf. OEIS sequence A000929. // Equinumerous to s-partitions (partitions into Mersenne numbers), // cf. class partition_s_desc. // ========== HEADER FILE src/comb/partition-2fall-asc.h: ========== class partition_2fall_asc; // Partitions of n is a partition a[1] + a[2] + ... + a[m] = n // such that a[k] >= 2 * a[k-1]. // Representation as weakly ascending list of parts. // Lexicographic order. // Cf. OEIS sequence A000929. // Equinumerous to s-partitions (partitions into Mersenne numbers), // cf. class partition_s_desc. // ========== HEADER FILE src/comb/partition-2fall-desc.h: ========== class partition_2fall_desc; // Partitions of n is a partition a[1] + a[2] + ... + a[m] = n // such that 2*a[k] <= a[k-1]. // Representation as weakly descending list of parts. // Lexicographic order. // Cf. OEIS sequence A000929. // Equinumerous to s-partitions (partitions into Mersenne numbers), // cf. class partition_s_desc. // ========== HEADER FILE src/comb/partition-asc-2rep-subset-lex.h: ========== class partition_asc_2rep_subset_lex; // Integer partitions where parts have multiplicity at most 2. // Representation as weakly ascending list of parts. // Subset-lex order. // Loopless algorithm. // Cf. OEIS sequence A000726. // ========== HEADER FILE src/comb/partition-asc-2rep.h: ========== class partition_asc_2rep; // Integer partitions where parts have multiplicity at most 2. // Representation as weakly ascending list of parts. // Lexicographic order. // Cf. OEIS sequence A000726. // ========== HEADER FILE src/comb/partition-asc-perim.h: ========== class partition_asc_perim; // Partitions into parts of 2 sorts where sorts are oscillating. // These are conjectured to be equinumerous with // non-empty sets of non-negative integers with perimeter n, // as defined in OEIS sequence A182372. // Representations as weakly ascending lists. // Lexicographic order: major order by sorts, minor by parts. // ========== HEADER FILE src/comb/partition-asc-sorts.h: ========== class partition_asc_sorts; // Partitions into parts of s sorts, as weakly ascending lists. // Lexicographic order: major order by parts, minor by sorts, where // comparison proceeds as sort1, part1; sort2, part2; sort3, part3, etc. // Cf. OEIS sequences (partitions of n into parts of s kinds): // A000041 (s=1), A000712 (s=2), A000716 (s=3), A023003 (s=4), // A023004 (s=5), A023005 (s=6), A023006 (s=7), and A023007 (s=8). // ========== HEADER FILE src/comb/partition-asc-sorts2-pp.h: ========== class partition_asc_sorts2_pp; // Partitions into parts of s[k] sorts for part (size) k. // Representation as weakly ascending lists. // Lexicographic order: major order by parts, minor by sorts, where // comparison proceeds as part1, sort1; part2, sort2; part3, sort3, etc. // Cf. OEIS sequence A000219 (planar partitions). // Cf. OEIS sequences (partitions of n into parts of s kinds): // A000041 (s=1), A000712 (s=2), A000716 (s=3), A023003 (s=4), // A023004 (s=5), A023005 (s=6), A023006 (s=7), and A023007 (s=8). // ========== HEADER FILE src/comb/partition-asc-sorts2.h: ========== class partition_asc_sorts2; // Partitions into parts of s sorts, as weakly ascending lists. // Lexicographic order: major order by parts, minor by sorts, where // comparison proceeds as part1, sort1; part2, sort2; part3, sort3, etc. // Cf. OEIS sequences (partitions of n into parts of s kinds): // A000041 (s=1), A000712 (s=2), A000716 (s=3), A023003 (s=4), // A023004 (s=5), A023005 (s=6), A023006 (s=7), and A023007 (s=8). // ========== HEADER FILE src/comb/partition-asc-subset-lex-csh.h: ========== class partition_asc_subset_lex_csh; // Partitions of n into positive parts as ascending list of parts. // Cyclically shifted subset-lex order: // The length of consecutive partitions changes by at most one. // Only two adjacent positions in a partition at the end change, // with the single exception that one only position changes with // the partition into one part. // Loopless algorithm. // ========== HEADER FILE src/comb/partition-asc-subset-lex.h: ========== class partition_asc_subset_lex; // Partitions of n into positive parts as weakly ascending list of parts. // Subset-lex order. // Only the two last parts at the end are different from the previous partition. // Loopless algorithm. // See Joerg Arndt, Subset-lex: did we miss an order?, (2014) // http://arxiv.org/abs/1405.6503 // ========== HEADER FILE src/comb/partition-asc.h: ========== class partition_asc; // Integer partitions. // Representation as list of parts in weakly ascending order. // Lexicographic order. // Cf. OEIS sequence A000041. // ========== HEADER FILE src/comb/partition-binary-asc.h: ========== class partition_binary_asc; // Binary partitions as weakly ascending list of parts // (the parts are powers of 2). // Lexicographic order. // Cf. OEIS sequences A018819 and A000123. // ========== HEADER FILE src/comb/partition-binary-desc.h: ========== class partition_binary_desc; // Binary partitions as weakly descending list of parts. // Lexicographic order. // Cf. OEIS sequences A018819 and A000123. // ========== HEADER FILE src/comb/partition-boundary.h: ========== static inline ulong partition_asc_perimeter(const ulong *x, ulong m); // Return the perimeter of a partition, that is, // the sum of all elements with at least one non-neighbor. static inline ulong partition_asc_boundary_size(const ulong *x, ulong m); // Return the size of the boundary of a partition, that is, // the number of all elements with at least one non-neighbor. // ========== HEADER FILE src/comb/partition-conj.h: ========== // ----- SRCFILE=src/comb/partition-conj.cc: ----- ulong partition_asc_conj(const ulong *a, ulong m, ulong *b); // Write conjugate partition of a[] // (a weakly ascending list with m parts) into b[]. // Return number of parts in b[]. // The first element in both arrays is at index 0. bool partition_asc_is_conj(const ulong *a, ulong ma, const ulong *b, ulong mb); // Return whether a[] (ma parts) and b[] (mb parts) are mutually conjugate partitions. // Both a[] and b[] must be weakly ascending lists with // the first element at index 0. bool partition_asc_is_self_conj(const ulong *a, ulong m); // Return whether the partition in a[] (m parts) is self-conjugate. ulong partition_desc_conj(const ulong *a, ulong m, ulong *b); // Write conjugate partition of a[] // (a weakly descending list with m parts) into b[]. // Return number of parts in b[]. // The first element in both arrays is at index 0. bool partition_desc_is_conj(const ulong *a, ulong ma, const ulong *b, ulong mb); // Return whether a[] (ma parts) and b[] (mb parts) are mutually conjugate partitions. // Both a[] and b[] must be weakly descending lists with // the first element at index 0. bool partition_desc_is_self_conj(const ulong *a, ulong m); // Return whether the partition in a[] (m parts) is self-conjugate. // ========== HEADER FILE src/comb/partition-desc-bb.h: ========== class partition_desc_bb; // Integer partitions as weakly descending list of parts, // with bounds for size of parts and number of parts. // Lexicographic order. // ========== HEADER FILE src/comb/partition-desc.h: ========== class partition_desc; // Integer partitions. // Representation as list of parts in weakly descending order. // Lexicographic order. // Cf. OEIS sequence A000041. // ========== HEADER FILE src/comb/partition-dist-asc-len.h: ========== class partition_dist_asc_len; // Integer partitions into distinct parts. // Representation as list of parts in increasing order. // Major order by number of parts, minor order lexicographic. // Cf. OEIS sequence A000009. // ========== HEADER FILE src/comb/partition-dist-asc-subset-lex.h: ========== class partition_dist_asc_subset_lex; // Integer partitions into distinct parts. // Representation as list of parts in increasing order. // Subset-lex order. // The length of consecutive partitions changes by at most one. // Only the last two positions in a partition at the end change. // Loopless algorithm. // See Joerg Arndt, Subset-lex: did we miss an order?, (2014) // http://arxiv.org/abs/1405.6503 // ========== HEADER FILE src/comb/partition-dist-asc.h: ========== class partition_dist_asc; // Integer partitions into distinct parts. // Representation as list of parts in increasing order. // Lexicographic order. // Cf. OEIS sequence A000009. // ========== HEADER FILE src/comb/partition-dist-d-asc.h: ========== class partition_dist_d_asc; // Integer partitions such that parts differ by at least d. // Representation as list of parts in increasing order. // Lexicographic order. // Cf. OEIS sequences // A000041 (all partitions; d=0), A000009 (distinct parts; d=1), // A003114 (d=2), A025157 (d=3), A025158 (d=4), A025159 (d=5), // A025160 (d=6), A025161 (d=7), and A025162 (d=8). // ========== HEADER FILE src/comb/partition-dist-desc.h: ========== class partition_dist_desc; // Partitions into distinct parts as decreasing list of parts. // Lexicographic order. // Cf. OEIS sequence A000009. // ========== HEADER FILE src/comb/partition-gen.h: ========== class partition_gen; // Integer partitions into parts pv[0], pv[1], ..., pv[n-1]. // pv[] defaults to [1, 2, 3, ...] (all positive parts). // ========== HEADER FILE src/comb/partition-hook-prod.h: ========== inline Type partition_desc_hook_prod(const ulong *a, ulong m, ulong *b); // Return product of all hook lengths in the partition a[]. // The partition must be a weakly descending list of length m. // b[] is used as scratch space for the conjugate partition. inline Type partition_asc_hook_prod(const ulong *a, ulong m, ulong *b); // Return product of all hook lengths in the partition a[]. // The partition must be a weakly ascending list of length m. // b[] is used as scratch space for the conjugate partition. // ========== HEADER FILE src/comb/partition-nonsquashing-desc.h: ========== class partition_nonsquashing_desc; // Non-squashing partitions as weakly descending list of parts. // A non-squashing partition of n is a partition a[1] + a[2] + ... + a[m] = n // such that a[k] >= sum(j=k+1..m, a[j] ). // With parameter sd = true generate strongly decreasing partitions: // partitions such that a[k] > sum(j=k+1..m, a[j] ). // Lexicographic order. // See: // N. J. A. Sloane, James A. Sellers: "On Non-Squashing Partitions", // arXiv:math/0312418 [math.CO], (22-December-2003). // Cf. OEIS sequences A018819, A000123 (non-squashing), and A040039 (strongly decreasing). // ========== HEADER FILE src/comb/partition-odd-asc-subset-lex-csh.h: ========== class partition_odd_asc_subset_lex_csh; // Integer partitions into odd parts. // Representation as list of parts in weakly ascending order. // Cyclically shifted subset-lex order: // The length of consecutive partitions changes by at most two. // Only two or three adjacent positions in a partition at the end change, // with the single exception that one only position changes with // the partition into one part when n is odd. // Loopless algorithm. // ========== HEADER FILE src/comb/partition-odd-asc-subset-lex.h: ========== class partition_odd_asc_subset_lex; // Integer partitions into odd parts. // Representation as list of parts in weakly ascending order. // Subset-lex order. // Only the two or three last parts at the end are different from the previous partition. // Loopless algorithm. // Cf. OEIS sequence A000009. // See Joerg Arndt, Subset-lex: did we miss an order?, (2014) // http://arxiv.org/abs/1405.6503 // ========== HEADER FILE src/comb/partition-odd-asc.h: ========== class partition_odd_asc; // Integer partitions into odd parts. // Representation as list of parts in weakly ascending order. // Lexicographic order. // Cf. OEIS sequence A000009. // ========== HEADER FILE src/comb/partition-odd-desc.h: ========== class partition_odd_desc; // Integer partitions into odd parts. // Representation as list of parts in weakly descending order. // Lexicographic order. // Cf. OEIS sequence A000009. // ========== HEADER FILE src/comb/partition-odd-nonsquashing-desc.h: ========== class partition_odd_nonsquashing_desc; // Non-squashing partitions into odd parts as weakly descending list of parts. // A non-squashing partition of n is a partition a[1] + a[2] + ... + a[m] = n // such that a[k] >= sum(j=k+1..m, a[j] ). // Lexicographic order. // Cf. OEIS sequence A187821. // ========== HEADER FILE src/comb/partition-odd-to-dist.h: ========== inline ulong partition_asc_odd_to_dist(const ulong *a, ulong ma, ulong *t); // From the partition a[0,1,..,ma-1] into odd parts compute the // corresponding partition t[0,1,...,mt-1] into distinct parts, as // ascending list of parts. Return mt, the number of parts in t[]. // a[] only needs to have all identical parts consecutive. inline ulong partition_asc_dist_to_odd(const ulong *a, ulong ma, ulong *t); // From the partition a[0,1,..,ma-1] into distinct parts compute the // corresponding partition t[0,1,...,mt-1] into odd parts, as weakly // increasing list of parts. Return mt, the number of parts in t[]. inline ulong partition_desc_odd_to_dist(const ulong *a, ulong ma, ulong *t); // From the partition a[0,1,..,ma-1] into odd parts compute the // corresponding partition t[0,1,...,mt-1] into distinct parts, as // descending list of parts. Return mt, the number of parts in t[]. // a[] only needs to have all identical parts consecutive. inline ulong partition_desc_dist_to_odd(const ulong *a, ulong ma, ulong *t); // From the partition a[0,1,..,ma-1] into distinct parts compute the // corresponding partition t[0,1,...,mt-1] into odd parts, as weakly // decreasing list of parts. Return mt, the number of parts in t[]. // ========== HEADER FILE src/comb/partition-rgs-lex.h: ========== class partition_rgs_lex; // Restricted growth strings (RGS) for partitions as descending lists, // lexicographic order. // Same as: least Young tableau (as RGS) with fixed shape (partition). // Cf. OEIS sequence A000041. // ========== HEADER FILE src/comb/partition-s-desc.h: ========== class partition_s_desc; // S-partitions: integer partitions into parts 2^n-1. // Representation as list of parts in weakly descending order. // Lexicographic order. // Cf. OEIS sequence A000929. // Equinumerous to partitions such that 2*a[k] <= a[k-1], // cf. class partition_2fall_desc. // ========== HEADER FILE src/comb/partition-strongly-decr-desc.h: ========== class partition_strongly_decr_desc; // Strongly decreasing partitions as list of parts. // A strongly decreasing partition of n is a partition // a[1] + a[2] + ... + a[m] = n such that a[k] > sum(j=k+1..m, a[j] ). // Lexicographic order. // Cf. OEIS sequences A040039 and A033485. // ========== HEADER FILE src/comb/partition.h: ========== class partition; // Integer partitions. // Order is such that the conjugates are in Abramowitz/Stegun order. // Representation as array of multiplicities of parts. // Cf. OEIS sequence A000041. // ========== HEADER FILE src/comb/peano-ndim.h: ========== class peano_ndim; // n-dimensional Peano curve // ========== HEADER FILE src/comb/perm-colex.h: ========== class perm_colex; // Permutations in co-lexicographic (colex) order. // Generation via rising factorial numbers. // ========== HEADER FILE src/comb/perm-derange.h: ========== class perm_derange; // Permutations in derangement order. // There is no derangement order for n=3 elements. // ========== HEADER FILE src/comb/perm-gray-ffact.h: ========== class perm_gray_ffact; // Gray code for permutations (Trotter/Johnson ordering). // CAT algorithm based on mixed radix Gray code // for the factorial number system (falling base). // ========== HEADER FILE src/comb/perm-gray-lipski.h: ========== class perm_gray_lipski; // Four Gray codes for permutations. // Algorithms following // W. Lipski, Jr.: More on permutation generation methods, // Computing, vol.23, no.4, pp.357-365, December-1979. // ========== HEADER FILE src/comb/perm-gray-rfact.h: ========== class perm_gray_rfact; // Gray code for permutations. // CAT algorithm based on mixed radix Gray code for rising factorial base. // ========== HEADER FILE src/comb/perm-gray-rot1.h: ========== class perm_gray_rot1; // Gray code for permutations. // Let e be the largest even number not greater than n: // the e first elements in the last permutation are a cyclic shift // to the left by one position of the first e elements. // For example, e==6 with n==6 and n==7: // first last // n=6: [ 0 1 2 3 4 5 ] [ 1 2 3 4 5 0 ] // n=7: [ 0 1 2 3 4 5 6 ] [ 1 2 3 4 5 0 6 ] // // CAT algorithm based on mixed radix Gray code for rising factorial base // with last two nines swapped for odd n. // ========== HEADER FILE src/comb/perm-gray-wells.h: ========== class perm_gray_wells; // Three Gray codes for permutations (Wells' order and two variants of it). // Algorithms following // W. Lipski, Jr.: More on permutation generation methods, // Computing, vol.23, no.4, pp.357-365, December-1979. // ========== HEADER FILE src/comb/perm-heap.h: ========== class perm_heap; // Gray code for permutations. // Algorithm following // B. R. Heap: Permutations by Interchanges, // The Computer Journal, vol. 6, pp. 293-294, (1963). // ========== HEADER FILE src/comb/perm-heap2-swaps.h: ========== class perm_heap2_swaps; // Swaps for Gray code for permutations. // Optimized implementation, quite fast. // Algorithm following // B. R. Heap: Permutations by Interchanges, // The Computer Journal, vol. 6, pp. 293-294, (1963). // ========== HEADER FILE src/comb/perm-heap2.h: ========== class perm_heap2; // Gray code for permutations. // Optimized implementation, quite fast. // Algorithm following // B. R. Heap: "Permutations by interchanges" (1963) // ========== HEADER FILE src/comb/perm-involution.h: ========== class perm_involution; // Involutions (self-inverse permutations). // Cf. OEIS sequence A000085. // ========== HEADER FILE src/comb/perm-ives.h: ========== class perm_ives; // Permutation in an order given by Ives. // The permutations are the order c of // F. M. Ives: {Permutation enumeration: four new permutation algorithms}, // Communications of the ACM, vol.19, no.2, pp.68-72, February-1976. // The inverse permutations are Ives' order a. // ========== HEADER FILE src/comb/perm-lex.h: ========== class perm_lex; // Permutations in lexicographic order, with inverse permutations. // Generation via rising factorial numbers. // ========== HEADER FILE src/comb/perm-mv0.h: ========== class perm_mv0; // Inverse permutations corresponding to falling factorial numbers. // CAT algorithm based on mixed radix Gray code // for the factorial number system (falling base). // ========== HEADER FILE src/comb/perm-pref.h: ========== class perm_pref; // Permutations via prefix shifts ("cool-lex" order). // Specialization of class mset_perm_pref. // ========== HEADER FILE src/comb/perm-rec.h: ========== class perm_rec; // Permutations (and cyclic permutations). // Recursive algorithm // ========== HEADER FILE src/comb/perm-rev.h: ========== class perm_rev; // Permutations by reversing prefixes, CAT algorithm. // ========== HEADER FILE src/comb/perm-rot.h: ========== class perm_rot; // All permutations, by rotations (cyclic shifts). // Algorithm of G. G. Langdon Jr., as given by Knuth. // Array x[] unused here (commented out). // ========== HEADER FILE src/comb/perm-st-gray.h: ========== class perm_st_gray; // Gray code for single track permutations: // one transposition per update with odd n, // one extra transposition once in (n-1)! updates with even n (optimal). // ========== HEADER FILE src/comb/perm-st-pref.h: ========== class perm_st_pref; // Permutations in single track order: // all columns are cyclic shifts of the first column. // Swaps of inverse permutation are done in prefix. // ========== HEADER FILE src/comb/perm-st.h: ========== class perm_st; // Permutations in single track order: // all columns are cyclic shifts of the first column. // ========== HEADER FILE src/comb/perm-star-inv.h: ========== class perm_star_inv; // Inverse star transposition permutations // via permutations by prefix reversals. // ========== HEADER FILE src/comb/perm-star-swaps.h: ========== class perm_star_swaps; // Permutations in star-transposition order (a Gray code). // Compute swaps only. // Algorithm by Gideon Ehrlich, as given by Knuth, // TAOCP 4A/1, Algorithm E "Ehrlich swaps", p.337. // Cf. OEIS sequences A123400 and A159880. // ========== HEADER FILE src/comb/perm-star.h: ========== class perm_star; // Permutations in star-transposition order (a Gray code). // Algorithm by Gideon Ehrlich, as given by Knuth, // TAOCP 4A/1, Algorithm E "Ehrlich swaps", p.337. // ========== HEADER FILE src/comb/perm-trotter-lg.h: ========== class perm_trotter_lg; // Gray code for permutations, Johnson/Steinhaus/Trotter algorithm. // Largest element moves most often. // Selmer M. Johnson: Generation of permutations by adjacent transposition, // Mathematics of Computation, vol.~17, no.~83, pp.~282-285, (July-1963). // H. F. Trotter: Algorithm 115: Perm, // Communications of the ACM, vol.5, no.8, pp.434-435, (August-1962). // ========== HEADER FILE src/comb/perm-trotter.h: ========== class perm_trotter; // Gray code for permutations, Johnson/Steinhaus/Trotter algorithm. // Smallest element moves most often. // Selmer M. Johnson: Generation of permutations by adjacent transposition, // Mathematics of Computation, vol.~17, no.~83, pp.~282-285, (July-1963). // H. F. Trotter: Algorithm 115: Perm, // Communications of the ACM, vol.5, no.8, pp.434-435, (August-1962). // ========== HEADER FILE src/comb/perm1-prefix-cond.h: ========== class perm1_prefix_cond; // Generate all permutations (one-based) with restricted prefixes, // in lexicographic order. // Knuth's "Algorithm X", section 7.2.1.2, p.334 in vol.4A/1 of TAOCP. // ========== HEADER FILE src/comb/perm1-topsort.h: ========== class perm1_topsort; // Permutations satisfying some partial order. // Knuth's "Algorithm V", section 7.2.1.2, p.343 in vol.4A/1 of TAOCP. // ========== HEADER FILE src/comb/print-arrangement-rgs-perm.h: ========== // ----- SRCFILE=src/comb/print-arrangement-rgs-perm.cc: ----- void print_arrangement_rgs_perm(const char *bla, const ulong *a, ulong n, ulong *rfc, ulong *p, bool zb/*=false*/); // The positions of nonzero digits determine the subset, and // their values (decreased by 1) are the (left) inversion table // (a rising factorial number) for the permutation. // ========== HEADER FILE src/comb/print-catalan-path-aa.h: ========== // ----- SRCFILE=src/comb/print-catalan-path-aa.cc: ----- void print_catalan_path_vert_aa(const ulong *a_, ulong n_, bool nfs/*=false*/); // Render path as ASCII art (base on vertical axis). void print_catalan_path_horiz_aa(const ulong *a, ulong n2); // Render path as ASCII art (base on horizontal axis). // ========== HEADER FILE src/comb/print-catalan-step-rgs-aa.h: ========== // ----- SRCFILE=src/comb/print-catalan-step-rgs-aa.cc: ----- void catalan_step_rgs_print_aa(const ulong *a, ulong n); // Render the lattice path for the RGS as ASCII art. // The path for the RGS a[] starts at (0, 0)==(0, a[0]), // goes over the points (k, a[k]) for 1 <= k <= n-1, // and ends at (n, n)==(n, a[n]). // Steps are (+1,0) and (+1,+1) and the path does not // go below the diagonal (k, k) for 0 <= k <= n. // Example: [ 0 0 0 1 3 3 4 4 4 4 ] gives // ._____ // ._| // ========== HEADER FILE src/comb/print-composition-aa.h: ========== // ----- SRCFILE=src/comb/print-composition-aa.cc: ----- void print_composition_aa(const ulong *a, ulong m); // Render composition as ASCII art. // Example: [ 1 2 3 4 4 2 3 4 ] gives // oo o // ooo oo // ooooooo // oooooooo void print_fountain_aa(const ulong *a, ulong m); // Render composition as fountain of coin ASCII art. // Example: [ 1 2 3 4 4 2 3 4 ] gives // O O O // O O O O O // O O O O O O O // O O O O O O O O // ========== HEADER FILE src/comb/print-composition-by-sorts.h: ========== // ----- SRCFILE=src/comb/print-composition-by-sorts.cc: ----- void print_composition_with_sorts(const char* bla, const ulong *va, const ulong *vs, ulong m); // Print as vector of pairs P:S (for part:sort). // Example: for va[]=[1, 2, 1, 3, 2] and s[]=[0, 1, 1, 0, 3] // print [ 1:0 2:1 1:1 3:0 2:3 ] void print_rev_composition_with_sorts(const char* bla, const ulong *va, const ulong *vs, ulong m); // Print as vector of pairs P:S (for part:sort), reversed order. // Example: for va[]=[1, 1, 2, 5, 7] and s[]=[0, 1, 1, 0, 3] // print [ 7:3 5:0 2:1 1:1 1:0 ] void print_composition_by_sorts(const char* bla, const ulong *va, const ulong *vs, ulong m); // Print as vector of vectors, one vector for each sort. // Example: for va[]=[1, 2, 1, 3, 2] and s[]=[0, 1, 1, 0, 3] // print [ [ 1 3 ] [ 2 1 ] [ ] [2] ] // ========== HEADER FILE src/comb/print-composition-unimodal.h: ========== // ----- SRCFILE=src/comb/print-composition-unimodal.cc: ----- void print_composition_unimodal(const char *bla, const ulong *va, const ulong *vs, ulong m); // Print a partition where each part (except the greatest) // can be of two sorts as a unimodal composition. // ========== HEADER FILE src/comb/print-partition-aa.h: ========== // ----- SRCFILE=src/comb/print-partition-aa.cc: ----- void print_partition_asc_aa(const ulong *a, ulong m); // Print partition into weakly ascending parts as ASCII art. // Example: [ 2 3 3 6 9 ] gives // oo // ooo // ooo // oooooo // ooooooooo void print_partition_asc_conj_aa(const ulong *a, ulong m); // Print conjugate of partition into weakly ascending parts as ASCII art. // Example: [ 2 3 3 6 9 ] gives // o // o // o // oo // oo // oo // oooo // ooooo // ooooo void print_partition_desc_aa(const ulong *a, ulong m); // Print partition into weakly descending parts as ASCII art. // Example: [ 5 5 3 1 1 1 ] gives // ooooo // ooooo // ooo // o // o // o void print_partition_desc_conj_aa(const ulong *a, ulong m); // Print conjugate of partition into weakly descending parts as ASCII art. // Example: [ 5 5 3 1 1 1 ] gives // oooooo // ooo // ooo // oo // oo // ========== HEADER FILE src/comb/print-partition-conj.h: ========== // ----- SRCFILE=src/comb/print-partition-conj.cc: ----- void print_partition_asc_conj(const char *bla, const ulong *a, ulong m); void print_partition_desc_conj(const char *bla, const ulong *a, ulong m); // ========== HEADER FILE src/comb/print-young-tab-rgs-aa.h: ========== // ----- SRCFILE=src/comb/print-young-tab-rgs-aa.cc: ----- void print_young_tab_rgs_aa(const ulong *A, const ulong *P, ulong n, ulong off/*=1*/); // Render Young tableau as ASCII art. // The value of the upper left element is determined by off. // P must contain the partition (as weakly descending list) // that corresponds to A[]. // Example: for // A[] = [ 0 1 0 2 1 0 ] (and P[] = [ 3 2 1 0 0 0 ]) // the output is // | 1 | 3 | 6 | // | 2 | 5 | // | 4 | // ========== HEADER FILE src/comb/print-zero-map-rgs.h: ========== // ----- SRCFILE=src/comb/print-zero-map-rgs.cc: ----- void print_zero_map_rgs_as_zero_dist_rgs(const char *bla, const ulong *a, ulong n, bool dfz/*=true*/); // Print corresponding zero-dist RGS, // all zeros are replaced by fixed points. void print_zero_map_rgs_as_fp_rgs(const char *bla, const ulong *a, ulong n, bool dfz/*=true*/, bool zb/*=true*/); // Print corresponding fixed-point RGS, // all zeros are replaced by fixed points. // zb determines whether printed elements are zero based. void print_zero_map_rgs_as_fp_dist_rgs(const char *bla, const ulong *a, ulong n, bool dfz/*=true*/, bool zb/*=true*/); // Print corresponding fixed-point-dist RGS, // all zeros are replaced by fixed points. void print_zero_map_rgs_setpart(const char *bla, const ulong *a, ulong n, bool zb/*=false*/, bool iq/*=false*/); // Print set partition corresponding to RGS. // zb determines whether the output is zero-based. // Set iq to use '()', not '{}', (use to print involutions). // ========== HEADER FILE src/comb/reverse-paren-string.h: ========== inline void reverse_paren_string(const Type *str, ulong n2, Type *st2); // Reverse string and swap '(' and ')' // Works for any pair of symbols. // Works in-place if str==0. inline void reverse_paren_string(Type *str, ulong n2); // Reverse string and swap '(' and ')' // Works for any pair of symbols. // Works in-place if str==0. // ========== HEADER FILE src/comb/rgs-fincr.h: ========== class rgs_fincr; // Restricted growth strings (RGS) s[0,...,n-1] so that // s[k] <= F[k]+i where // F[0]=0, F[k+1]=( s[k+1]-s[k]==i ? F[k]+i : F[k] ) // Lexicographic order. // Cf. OEIS sequences // A000110 (i=1), A004211 (i=2), A004212 (i=3), // A004213 (i=4), A005011 (i=5), A005012 (i=6). // ========== HEADER FILE src/comb/rgs-kincr.h: ========== class rgs_kincr; // Restricted growth strings (RGS) s[0,...,n-1] so that s[k] <= s[k-1]+k // Lexicographic order. // Cf. OEIS sequence A107877. // ========== HEADER FILE src/comb/rgs-maxincr.h: ========== class rgs_maxincr; // Restricted growth strings (RGS) s[0,...,n-1] so that // s[k] <= max( j < k, s[j] + i ). // Lexicographic order // OEIS sequences: // i=1 ==> Bell numbers, A000110 // i=2 ==> A080337, see also A080107 // i=3 ==> A189845 // ========== HEADER FILE src/comb/ruler-func-s.h: ========== class ruler_func_s : public composition_nz_sorts; // Ruler function (one-based), s-valuations of s*n: // s=2: 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 ... // cf. OEIS sequence A001511 and A007814 (zero based) // s=3: 1 1 2 1 1 2 1 1 3 1 1 2 1 1 2 1 1 3 1 1 2 1 1 ... // cf. OEIS sequences A051064 and A007949 (zero based) // Loopless algorithm. // ========== HEADER FILE src/comb/ruler-func.h: ========== class ruler_func; // Ruler function (zero-based), 2-valuations of n: // 0 1 0 2 0 1 0 3 0 1 0 2 0 1 0 4 0 1 0 2 0 1 ... // Loopless algorithm (specialization of Knuth's method // for mixed radix Gray code). // Cf. OEIS sequence A007814. // ========== HEADER FILE src/comb/ruler-func1.h: ========== class ruler_func1 : public composition_nz; // Ruler function (one-based), 2-valuations of 2*n: // 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 ... // Loopless algorithm. // Cf. OEIS sequence A001511. // ========== HEADER FILE src/comb/schroeder-path-lex.h: ========== class schroeder_path_lex; // Schroeder paths in lexicographic order, CAT algorithm. // Steps are +1, 0, -1 (up, horizontal, down), // the first and last elements are 0, all elements are non-negative, and // horizontal steps appear consecutively an even number of times. // Cf. OEIS sequence A006318: large Schroeder numbers. // ========== HEADER FILE src/comb/schroeder-rgs-lex.h: ========== class schroeder_rgs_lex; // Schroeder restricted growth strings (RGS): // a Schroeder RGS is a word a[0,1,2,...,n-1] where // a[k] <= k + 1 (rising factorial numbers), // a[0] <= m0 and a[k] + 1 >= max(j=1..k-1, a[j]) // m0 == 0 ==> little Schroeder numbers, A001003 // m0 == 1 ==> large Schroeder numbers, A006318 // Lexicographic order. // Cf. OEIS sequences A001003 and A006318. // ========== HEADER FILE src/comb/score-sequence.h: ========== class score_sequence; // Score sequences: weakly increasing sequences a[0,1,...,n-1] where // sum(j=0..k, a[j]) >= k*(k+1)/2 and sum(j=0..n-1, a[j]) = (n+1)*n/2. // Lexicographic order. // See OEIS sequence A000571. // ========== HEADER FILE src/comb/setpart-ccf-rgs-lex.h: ========== class setpart_ccf_rgs_lex; // Restricted growth strings (RGS) for set partitions: // each digit a[k] < k and a[k-1] != 0 implies a[k] <= a[k-1]. // The RGS correspond to permutations in canonical cycle form (CCF) // that are valid set partitions. // Same as: maps from {1, 2, 3, ..., n} to {0, 1, 2, 3, ..., n} // such that f(x) < x and f(x-1) != 0 implies f(x) <= f(x-1). // Lexicographic order. // ========== HEADER FILE src/comb/setpart-ck-rgs.h: ========== class setpart_ck_rgs; // Restricted growth strings (RGS) for set partitions: // each digit is either a fixed point or a digit from the prefix. // Equivalently: rooted trees of height <= 2. // Lexicographic order. // See // Curtis Cooper, Robert E. Kennedy: // "Patterns, Automata, and Stirling Numbers of the Second Kind", // Mathematics and Computer Education Journal, vol.26, (1992), // where these RGS are called "n-pattern sequences", a term // we will not use because "pattern sequences" better describe // the "usual" RGS for set partitions. Instead we call them // Cooper-Kennedy RGS, abbreviated here as CK-RGS. // ========== HEADER FILE src/comb/setpart-noncrossing-ll.h: ========== class setpart_noncrossing_ll; // Noncrossing set partitions via Catalan restricted growth strings (RGS). // Sets are in the form vector< vector > for easy traversal, // see the print() method. // Lexicographic order for the RGS. // The number of length-n RGS is (OEIS sequence A000108) // 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, ... // ========== HEADER FILE src/comb/setpart-noncrossing-rgs.h: ========== class setpart_noncrossing_rgs; // Noncrossing set partitions of the n-set as restricted growth strings (RGS). // Lexicographic order. // ========== HEADER FILE src/comb/setpart-p-rgs-lex.h: ========== class setpart_p_rgs_lex; // Set partitions of the n-set into p parts (where 2<=p<=n) // as restricted growth strings (RGS). // Lexicographic order. // Cf. OEIS sequence A008277. // ========== HEADER FILE src/comb/setpart-rgs-fixed-content-vec.h: ========== class setpart_rgs_fixed_content_vec; // Set partitions whose restricted growth string (RGS) has fixed content-vector. // For example, the content-vector [3, 2, 3] corresponds to the set partitions // of set with 8 elements into subsets of sizes 3, 2, 3 (in that order). // Lexicographic order. // ========== HEADER FILE src/comb/setpart-rgs-gray.h: ========== class setpart_rgs_gray; // Set partitions of the n-set as restricted growth strings (RGS): // strings s[0, 1, ..., n-1] such that s[k] <= max(s[0], s[1], ..., s[k-1]) + 1. // Minimal-change order for set partitions, // note that the RGS can change in more than one position. // ========== HEADER FILE src/comb/setpart-rgs-lex.h: ========== class setpart_rgs_lex; // Set partitions of the n-set as restricted growth strings (RGS): // strings s[0, 1, ..., n-1] such that s[k] <= max(s[0], s[1], ..., s[k-1]) + 1. // Lexicographic order. // ========== HEADER FILE src/comb/setpart-rgs-subset-lex.h: ========== class setpart_rgs_subset_lex; // Set partitions of the n-set as restricted growth strings (RGS): // strings a[0, 1, ..., n-1] such that a[k] <= max(a[0], a[1], ..., a[k-1]) + 1. // Subset-lex order. // See Joerg Arndt, Subset-lex: did we miss an order?, (2014) // http://arxiv.org/abs/1405.6503 // ========== HEADER FILE src/comb/setpart-s-zero-map-rgs.h: ========== class setpart_s_zero_map_rgs; // Set partitions into sets of size <= s+1 represented as // restricted growth strings (RGS): // each digit a[k] is either zero or the (one-based) index // of a zero in the prefix and there are at most s digits pointing // to the same zero in the prefix. // Same as: maps from {1, 2, 3, ..., n} to {0, 1, 2, 3, ..., n} // such that f(x) < x and f(f(x)) == 0 and there are at most s // values t such that f(t) = f(x). // Lexicographic order. // Cf. OEIS sequences A000085 (for s=1), A001680 (s=2), A001681 (s=3), // A110038 (s=4), and A000110 (for s>=n-1). // ========== HEADER FILE src/comb/setpart-zero-map-rgs.h: ========== class setpart_zero_map_rgs; // Restricted growth strings (RGS) for set partitions: // each digit a[k] is either zero or a[k] < k and a[a[k]] == 0. // Same as: maps from {1, 2, 3, ..., n} to {0, 1, 2, 3, ..., n} // such that f(x) < x and f(f(x)) == 0. // Lexicographic order. // Cf. OEIS sequence A000110. // ========== HEADER FILE src/comb/setpart.h: ========== class setpart; // Set partitions of the set {1,2,3,...,n} // By default in minimal-change order. // ========== HEADER FILE src/comb/signed-perm-gray.h: ========== class signed_perm_gray; // Signed permutations (hyperoctahedral group), Gray code. // Every second signed permutation in the list is a pure rotation. // There are n! * 2^n signed permutations of n elements. // We flip a sign most often, the number of transpositions is minimal, as in // James F. Korsh, Paul S. LaFollette: A loopless Gray code for rooted trees, // ACM Transactions on Algorithms, vol.2, no.2, pp.135-152, (April-2006). // An ordering with a transposition at every step is given in // Yuan Qiu, Aaron Williams: Generating Signed Permutations by // Twisting Two-Sided Ribbons, (2023), https://arxiv.org/abs/2311.06974 // ========== HEADER FILE src/comb/signed-perm.h: ========== class signed_perm; // Signed permutations (hyperoctahedral group). // There are n! * 2^n signed permutations of n elements. // ========== HEADER FILE src/comb/skew-binary.h: ========== class skew_binary; // Skew binary numbers. // Loopless algorithm. // See http://en.wikipedia.org/wiki/Skew_binary_number_system // Cf. OEIS sequence A169683. // ========== HEADER FILE src/comb/smooth-rfact-rgs.h: ========== class smooth_rfact_rgs; // Restricted growth strings (RGS) [d(0), d(1), d(2), ..., d(n-1)] where // 0 <= d(k) <= k and abs(d(k)-d(k-1)) <= 1 (smooth factorial numbers). // Lexicographic order. // Cf. OEIS sequence A005773. // ========== HEADER FILE src/comb/string-subst.h: ========== class string_subst; // String substitution engine (Lindenmayer system, or L-system). // Note: the derived class lindenmayer_system is much easier to use. // ========== HEADER FILE src/comb/subset-debruijn.h: ========== class subset_debruijn; // Subsets of the set {0,1,2,...,n-1} in an order // determined by a De Bruijn sequence. // Note: work per subset is proportional to n. // ========== HEADER FILE src/comb/subset-deltalex.h: ========== class subset_deltalex; // Subsets in lexicographic order for delta sets // ========== HEADER FILE src/comb/subset-gray-delta.h: ========== class subset_gray_delta; // Subsets of the set {0,1,2,...,n-1} in minimal-change (Gray code) order. // Loopless algorithm. // ========== HEADER FILE src/comb/subset-gray.h: ========== class subset_gray; // Subsets of the set {1,2,...,n} in minimal-change (Gray code) order. // Loopless algorithm following Jenkyns ("Loopless Gray Code Algorithms"). // ========== HEADER FILE src/comb/subset-lex-compare.h: ========== inline int subset_lex_compare(const Type *a, const Type *b, ulong n,; bool rlq=false) // Compare a[] and b[] with repect to subset-lex order. // Return +1 if a[] >> b[], -1 if a[] << b[], 0 if a[]==b[]. // ========== HEADER FILE src/comb/subset-lex.h: ========== class subset_lex; // Nonempty subsets of the set {0,1,2,...,n-1} in subset-lex order. // Representation as list of parts. // Loopless generation. // See Joerg Arndt, Subset-lex: did we miss an order?, (2014) // http://arxiv.org/abs/1405.6503 // ========== HEADER FILE src/comb/subset-sl-gray.h: ========== class subset_sl_gray : binary_sl_gray; // Nonempty subsets of the set {0,1,2,...,n-1} in SL-Gray order. // Representation as list of parts. // Elements are inserted/removed either at end or // at the second-last position. // Loopless generation. // See OEIS sequence A217262. // ========== HEADER FILE src/comb/test-gray.h: ========== // ----- SRCFILE=src/comb/test-gray.cc: ----- ulong test_gray_path(const ulong *f, ulong n); // Test whether the sequence f[] is a Gray path. // If so, return zero, else return the index of the second element // of the first pair whose difference is not one bit. bool is_gray_path(const ulong *f, ulong n); // Return true if f[] is a Gray path, // else return false. ulong test_canonical_gray(const ulong *f, ulong n); // Test whether the sequence f[] is canonical. // If so, return zero, else return the index of the second element // of the first pair whose difference is the on wrong track. // Does NOT check that the sequence is a Gray path. bool is_canonical_gray(const ulong *f, ulong n); // Return true if f[] is a Gray path, // else return false. // Does NOT check that the sequence is a Gray path. bool is_monotonic_gray(const ulong *f, ulong n); // Return true if f[] is a monotonic Gray path, // else return false. // Does NOT check that the sequence is a Gray path. bool is_complementary_gray(const ulong *f, ulong n); // Return whether the sequence f[] is complementary. // Does NOT check that the sequence is a Gray path. // ========== HEADER FILE src/comb/tree-lev-seq-aux.h: ========== class tree_lev_seq_aux; // Auxiliary class for classes *tree_lev_seq* // ========== HEADER FILE src/comb/tree-lev-seq.h: ========== class tree_lev_seq; // Level sequences for unordered rooted trees. // Cf. OEIS sequence A000081 // ========== HEADER FILE src/comb/weak-ascent-rgs.h: ========== class weak_ascent_rgs; // Weak ascent sequences (restricted growth strings, RGS), lexicographic order. // A weak ascent sequence is a sequence [d(1), d(2), ..., d(n)] where d(1)=0, d(k)>=0, // and d(k) <= 1 + asc([d(1), d(2), ..., d(k-1)]) and asc(.) counts the // number of weak ascents d(j) >= d(j-1) of its argument. // See OEIS sequences A336070, A369321, A369322. // ========== HEADER FILE src/comb/weakly-unimodal-map-lex.h: ========== class weakly_unimodal_map_lex; // Weakly unimodal maps, lexicographic order. // Cf. OEIS sequences: // A088536: [1..n] -> [1..n]. // A225006: [1..n] -> [1..n+1]. // A000124: [1..n] -> [1,2]. // A223718: [1..n] -> [1,2,3]. // A223659: [1..n] -> [1,2,3,4]. // A002412: [1,2,3] -> [1..n]. // A006324: [1,2,3,4] -> [1..n]. // ========== HEADER FILE src/comb/wfl-hilbert.h: ========== class wfl_cell; // Container used in class wfl_hilbert. class wfl_hilbert; // Fred Lunnon's (second) iterative algorithm to convert linear coordinate // into coordinates of d-dimensional Hilbert curve (and back). // Translated and adapted from Java code by Fred Lunnon. // // See the file wfl-hilbert-doc.txt in the doc/ directory // for Fred Lunnon's explanations of the algorithm. // ========== HEADER FILE src/comb/word-stats.h: ========== class word_stats; // Various statistics for length-n arrays of type ulong. // ========== HEADER FILE src/comb/young-tab-fixed-shape.h: ========== class young_tab_fixed_shape; // Young tableaux with fixed shape. // The underlying driver is class perm1_topsort. // OEIS sequences "Young tableaux of shape [??]: // A000108: [n,n] // A005789: [n,n,n] // A005790: [n,n,n,n] // A039622: [n, n, ..., n] (n times n) // A005118: [n, n-1, n-2, n-3, ..., 1] // A003121: [1, 2, 3, ..., n] // A071724: [n+1, n-1], also [n, 1, n] // A000344: [n+2, n-2], also [n, 1, 1, 1, n] // A000588: [n+3, n-3] // A174687: [2*n, n] // A123555: [n+1, n, n-1] // A368567: [n, floor(n/2)] // with shiftq == true: // A181197: [n, n, n] // A181198: [n, n, n, n] // A181199: [n, n, n, n, n] // ========== HEADER FILE src/comb/young-tab-rgs-descents.h: ========== inline ulong young_tab_rgs_descent_set(const ulong *a, ulong n, ulong *d); // Return the number of descents of the tableau. // Write the set of corresponding positions into d[]. // A descent in a standard Young tableau is a entry i such that i+1 // lies strictly below and weakly left of i. inline ulong young_tab_rgs_major_index(const ulong *a, ulong n); // Return the major index of the tableau. // A descent in a standard Young tableau is a entry i such that i+1 // lies strictly below (and weakly left of) i. The major index is the // sum of all such i. // Return value s in range 0 <= s <= n*(n-1)/2 inline ulong young_tab_rgs_descent_number(const ulong *a, ulong n); // Return the number of descents of the tableau. // A descent in a standard Young tableau is a entry i such that i+1 // lies strictly below and weakly left of i. // ========== HEADER FILE src/comb/young-tab-rgs-subset-lex.h: ========== class young_tab_rgs_subset_lex; // Restricted growth strings (RGS) for standard Young tableaux: // the k-th occurrence of a digit d in the RGS must precede // the k-th occurrence of the digit d+1. // Subset-lex order. // Cf. OEIS sequences A000085 (all tableaux), // A061343 (all shifted tableaux; using condition is_shifted(1)), // A210736 (shifted, height <= 2), A082395 (shifted, height <= 3). // ========== HEADER FILE src/comb/young-tab-rgs.h: ========== class young_tab_rgs; // Restricted growth strings (RGS) for standard Young tableaux: // the k-th occurrence of a digit d in the RGS must precede // the k-th occurrence of the digit d+1. // Lexicographic order. // The strings are also called ballot sequences. // Cf. OEIS sequences A000085 (all tableaux), // A001405 (tableaux with height <= 2, central binomial coefficients) // A001006 (tableaux with height <= 3, Motzkin numbers) // A005817 (height <= 4), A049401 (height <= 5), A007579 (height <= 6) // A007578 (height <= 7), A007580 (height <= 8), A212915 (height <= 9), // A212916 (height <= 10). // A001189 (height <= n-1), // A014495 (height = 2), A217323 (height = 3), A217324 (height = 4), // A217325 (height = 5), A217326 (height = 6), A217327 (height = 7), // A217328 (height = 8). // Cf. A182172 (tableaux of n cells and height <= k). // Cf. OEIS sequences A061343 (all shifted tableaux; using condition is_shifted(1)), // A210736 (shifted, height <= 2), A082395 (shifted, height <= 3). // Cf. OEIS sequences A161125 (descent numbers), A225617 (strict inversions), // and A225618 (weak inversions).