// -*- 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/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] "{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] ==> "11.11...1" // ----- 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-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_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 strong minimal-change order. // The delta set is generated. // "Chase's sequence", algorithm as given by Knuth. // ========== 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. // ========== 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 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 (lexicographic order) // ========== HEADER FILE src/comb/combination-mod.h: ========== class combination_mod; // Combinations in 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 (n choose k) in minimal-change order. // "Revolving door" algorithm following Knuth. // See: // 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. // ========== 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-nz.h: ========== class composition_nz; // Compositions of n into nonzero parts. // Ordering is firstly by number of parts (n, n-1, ..., 1) // and secondly co-lexicographic (colex). // ========== HEADER FILE src/comb/composition-rank.h: ========== class composition_rank : public num_compositions; // 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/cyclic-perm.h: ========== class cyclic_perm; // Cyclic permutations in minimal-change order. // CAT algorithm based on mixed radix Gray code // for the factorial number system. // ========== 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/dyck-gray.h: ========== class dyck_gray; // Gray code for k-ary Dyck words with all transitions homogenous. // 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 // 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-pref2.h: ========== class dyck_pref2; // k-ary Dyck words // Algorithm "coolKat" as given (right 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, subset-lex order. // ========== HEADER FILE src/comb/dyck-rgs.h: ========== class dyck_rgs; // Restricted growth strings (RGS) corresponding to k-ary Dyck words (k=i+1): // s[0,...,n-1] such that s[k] <= s[k-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); // 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); // 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^32] // 64 bit: n<=93 F(93)=12200160415121876738 [F(94) > 2^64] inline void fibonacci_pair(ulong n, ulong &f0, ulong &f1); // Set f0 to F(n), the n-th Fibonacci number, and // f1 to the F(n-1). // Limitation: F(n) must fit into ulong // 32 bit: n<=47, F(47)=2971215073 [F(48)=4807526976 > 2^32] // 64 bit: n<=93 F(93)=12200160415121876738 [F(94) > 2^64] // ========== 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; // 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; // Lunnon's iterative algorithm to convert linear coordinate // into coordinates of d-dimensional Hilbert curve. // ========== HEADER FILE src/comb/is-motzkin-path.h: ========== // ----- SRCFILE=src/comb/is-motzkin-path.cc: ----- bool is_motzkin_path(const ulong *x, ulong n); // Return whether x[] is a valid Motzkin path, i.e., // x[0] = 0, abs(x[j]-x[j-1]) <= 1, and x[n-1] <= 1. // ========== 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. // 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. // ========== 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-rec.h: ========== class ksubset_rec; // k-subsets where kmin<=k<=kmax in various orders. // Recursive CAT algorithm. // ========== HEADER FILE src/comb/ksubset-twoclose.h: ========== class ksubset_twoclose; // k-subsets (kmin<=k<=kmax) in a two-close order with homogeneous moves. // Recursive algorithm. // ========== 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-gray.h: ========== class mixedradix_gray; // Gray code for mixed radix numbers. // CAT algorithm. // ========== HEADER FILE src/comb/mixedradix-gray2.h: ========== class mixedradix_gray2; // Gray code for mixed radix numbers. // Loopless algorithm. Implementation following Knuth. // ========== 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-alt2.h: ========== class mixedradix_gslex_alt2; // 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. // ========== HEADER FILE src/comb/mixedradix-lex.h: ========== class mixedradix_lex; // Mixed radix counting. // ========== HEADER FILE src/comb/mixedradix-modular-gray.h: ========== class mixedradix_modular_gray; // Modular Gray code for mixed radix numbers. // Implementation following Knuth (loopless algorithm). // ========== HEADER FILE src/comb/mixedradix-modular-gray2.h: ========== class mixedradix_modular_gray2; // 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-sl.h: ========== class mixedradix_naf_sl; // 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-sl-gray.h: ========== class mixedradix_sl_gray; // Mixed radix numbers in a minimal-change order // related so subset-lex order ("SL-Gray" order). // ========== HEADER FILE src/comb/mixedradix-sod-lex.h: ========== class mixedradix_sod_lex; // Mixed radix numbers with prescribed sum of digits s, in lexicographic order. // Same as: s-combinations of a multiset. // Same as: compositions of s with prescribed maximum at each place. // ========== HEADER FILE src/comb/mixedradix-subset-lex.h: ========== class mixedradix_subset_lex; // Mixed radix numbers in subset-lexicographic order. // Successive numbers differ in at most three digits. // ========== HEADER FILE src/comb/mixedradix.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[]. ulong product(const ulong *x, ulong n); ulong product_p1(const ulong *m1, ulong n); // ========== HEADER FILE src/comb/monotonic-gray.h: ========== // ----- SRCFILE=src/comb/monotonic-gray.cc: ----- void monotonic_gray_delta(unsigned char *d, ulong ldn); // Write into the array d[] the delta sequence for the // Savage-Winkler monotonic Gray path. // 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); // Fill into g[0..N-1] (N=2**ldn) // the monotonic (Savage-Winkler) Gray path. // ========== HEADER FILE src/comb/motzkin-path-lex.h: ========== class motzkin_path_lex; // Motzkin paths in lexicographic order, CAT algorithm. // ========== HEADER FILE src/comb/mpartition.h: ========== class mpartition; // Integer partitions of n into m parts // ========== HEADER FILE src/comb/mset-perm-2invtab.h: ========== void msetperm2rinvtab(const Type *ms, ulong n, ulong *t); // Compute (right) inversion table of multiset permutation ms[]: // t[k] := number of elements ms[j] right of position k // (i.e. j>k) and less than ms[k]. // Must have: n>=1. void msetperm2linvtab(const Type *ms, ulong n, ulong *t); // Compute (left) inversion table of multiset permutation ms[]: // t[k-1] := number of elements ms[j] left of position k // (i.e. j=1. // ========== HEADER FILE src/comb/mset-perm-gray.h: ========== class mset_perm_gray; // Multiset permutations in minimal-change order (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 by prefix shifts" // Symposium on Discrete Algorithms, New York, 2009. // ========== 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(ulong x, ulong *f, ulong n); // Create permutation number x according to (factorial) unrank. ulong perm2num(const ulong *f, ulong n); // Inverse of num2perm() 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/paren-gray.h: ========== class paren_gray; // Parentheses strings in a homogeneous minimal-change order. // ========== 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" // ========== 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, bool rq/*=false*/); // 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. bool is_catalan_rgs(const ulong *rgs, ulong n); // Return whether rgs[] is a valid Catalan RGS. // ========== HEADER FILE src/comb/paren.h: ========== class paren; // Parentheses strings by a modified comb_colex procedure // ========== HEADER FILE src/comb/partition-gen.h: ========== class partition_gen; // Integer partitions of x into supplied values pv[0],...,pv[n-1]. // pv[] defaults to [1,2,3,...,x] // ========== HEADER FILE src/comb/partition.h: ========== class partition; // Integer partitions // ========== 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-ffact2.h: ========== class perm_gray_ffact2; // Gray code for permutations (Trotter/Johnson ordering). // Loopless algorithm based on mixed radix Gray code // for the factorial number system. // ========== 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" (1963) // ========== HEADER FILE src/comb/perm-heap2-swaps.h: ========== class perm_heap2_swaps; // Swaps for Gray code for permutations. // Algorithm following B.R.Heap "Permutations by interchanges" (1963) // Optimized implementation, very fast. // ========== HEADER FILE src/comb/perm-heap2.h: ========== class perm_heap2; // Gray code for permutations. // Algorithm following B.R.Heap "Permutations by interchanges" (1963) // Optimized implementation, very fast. // ========== HEADER FILE src/comb/perm-involution.h: ========== class perm_involution; // Involutions (self-inverse permutations) // ========== 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-inv.h: ========== class perm_lex_inv; // Permutations in lexicographic order, with inverse permutations. // Generation via rising factorial numbers. // ========== HEADER FILE src/comb/perm-lex.h: ========== class perm_lex; // Permutations in lexicographic order // ========== HEADER FILE src/comb/perm-lex2.h: ========== class perm_lex2; // Permutations in lexicographic order. // 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-restrpref.h: ========== class perm_restrpref; // Generate all permutations with restricted prefixes, // in lexicographic order. // Algorithm as given by Knuth. // ========== HEADER FILE src/comb/perm-rev.h: ========== class perm_rev; // Permutations by reversing prefixes, CAT algorithm // ========== HEADER FILE src/comb/perm-rev2.h: ========== class perm_rev2; // Permutations by reversing prefixes, CAT algorithm. // Optimized version. // ========== HEADER FILE src/comb/perm-rot.h: ========== class perm_rot; // All permutations, by rotations (cyclic shifts). // Algorithm of G.G.Langdon Jr., as given in 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-swaps.h: ========== class perm_star_swaps; // Permutations in star-transposition order (a Gray code). // Compute swaps only. // Algorithm of Gideon Ehrlich, as given by Knuth // ========== HEADER FILE src/comb/perm-star.h: ========== class perm_star; // Permutations in star-transposition order (a Gray code). // Algorithm of Gideon Ehrlich, as given by Knuth // ========== HEADER FILE src/comb/perm-trotter-lg.h: ========== class perm_trotter_lg; // Gray code for permutations // Trotter/Johnson algorithm. // Largest element moves most often. // ========== HEADER FILE src/comb/perm-trotter.h: ========== class perm_trotter; // Gray code for permutations, Trotter/Johnson algorithm. // Smalles element moves most often. // ========== 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 // ========== 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. // The number of length-n RGS is // 1, 2, 7, 37, 268, 2496, 28612, 391189, (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