You may want to look at the outputs first.
acgray-out.txt is the output of acgray-demo.cc.
Description:
Adjacent changes (AC) Gray codes for n<=6
The demo uses the functions from
acgray.h (fxt/src/comb/acgray.h)
delta2gray.h (fxt/src/comb/delta2gray.h)
acgray.cc (fxt/src/comb/acgray.cc)
bell-number-out.txt is the output of bell-number-demo.cc.
Description:
Bell numbers.
big-fact2perm-out.txt is the output of big-fact2perm-demo.cc.
Description:
Generate all permutations from mixed radix (factorial) numbers,
using left-right array, so conversion is fast also for large length.
The demo uses the functions from
big-fact2perm.h (fxt/src/comb/big-fact2perm.h)
big-fact2perm.cc (fxt/src/comb/big-fact2perm.cc)
left-right-array.h (fxt/src/ds/left-right-array.h)
binary-debruijn-out.txt is the output of binary-debruijn-demo.cc.
Description:
Generating binary De Bruijn sequences.
The demo uses the functions from
binary-debruijn.h (fxt/src/comb/binary-debruijn.h)
binary-necklace.h (fxt/src/comb/binary-necklace.h)
binary-necklace-out.txt is the output of binary-necklace-demo.cc.
Description:
Binary pre-necklaces, necklaces and Lyndon words: CAT generation.
The demo uses the functions from
binary-necklace.h (fxt/src/comb/binary-necklace.h)
binary-sl-gray-out.txt is the output of binary-sl-gray-demo.cc.
Description:
Binary numbers in a minimal-change order
related so subset-lex order ("SL-Gray" order).
The demo uses the functions from
binary-sl-gray.h (fxt/src/comb/binary-sl-gray.h)
binomial-out.txt is the output of binomial-demo.cc.
Description:
Print the Pascal triangle (binomial coefficients).
The demo uses the functions from
binomial.h (fxt/src/aux0/binomial.h)
catalan-out.txt is the output of catalan-demo.cc.
Description:
Catalan restricted growth strings (RGS) and parentheses strings in minimal-change order.
The demo uses the functions from
catalan.h (fxt/src/comb/catalan.h)
catalan.cc (fxt/src/comb/catalan.cc)
catalan-gray-out.txt is the output of catalan-gray-demo.cc.
Description:
Catalan restricted growth strings (RGS) and parentheses strings
The demo uses the functions from
catalan-gray.h (fxt/src/comb/catalan-gray.h)
paren-string-to-rgs.h (fxt/src/comb/paren-string-to-rgs.h)
catalan-lex-out.txt is the output of catalan-lex-demo.cc.
Description:
Catalan restricted growth strings (RGS) and
parentheses strings in lexicographic order.
The demo uses the functions from
catalan-lex.h (fxt/src/comb/catalan-lex.h)
paren-string-to-rgs.h (fxt/src/comb/paren-string-to-rgs.h)
comb2comp-out.txt is the output of comb2comp-demo.cc.
Description:
Relation between combinations and compositions.
The demo uses the functions from
combination-revdoor.h (fxt/src/comb/combination-revdoor.h)
comp2comb.h (fxt/src/comb/comp2comb.h)
combination-chase-out.txt is the output of combination-chase-demo.cc.
Description:
Combinations in near-perfect minimal-change order (Chase's sequence).
The demo uses the functions from
combination-chase.h (fxt/src/comb/combination-chase.h)
binomial.h (fxt/src/aux0/binomial.h)
combination-colex-out.txt is the output of combination-colex-demo.cc.
Description:
Generating all combinations in co-lexicographic order.
The demo uses the functions from
combination-colex.h (fxt/src/comb/combination-colex.h)
combination-emk-out.txt is the output of combination-emk-demo.cc.
Description:
Combinations in strong minimal-change order (Eades-McKay sequence).
Iterative generation via modulo moves.
The demo uses the functions from
combination-emk.h (fxt/src/comb/combination-emk.h)
combination-emk-rec-out.txt is the output of combination-emk-rec-demo.cc.
Description:
Eades-McKay (strong revolving door) order for combinations
combination-endo-out.txt is the output of combination-endo-demo.cc.
Description:
Strong minimal-change order for combinations (Chase's sequence) via endo steps
The demo uses the functions from
combination-endo.h (fxt/src/comb/combination-endo.h)
combination-enup-out.txt is the output of combination-enup-demo.cc.
Description:
Strong minimal-change order for combinations via enup (endo) steps
The demo uses the functions from
combination-enup.h (fxt/src/comb/combination-enup.h)
combination-enup-rec-out.txt is the output of combination-enup-rec-demo.cc.
Description:
Recursive generation of enup order for combinations (strong minimal-change order).
combination-gray-rec-out.txt is the output of combination-gray-rec-demo.cc.
Description:
Generating all combinations in minimal-change order, recursive implementation.
combination-lam-out.txt is the output of combination-lam-demo.cc.
Description:
Minimal-change order for combinations with k>=2 elements
Good performance for small k
combination-lex-out.txt is the output of combination-lex-demo.cc.
Description:
Generating all combinations in lexicographic order.
The demo uses the functions from
combination-lex.h (fxt/src/comb/combination-lex.h)
combination-mod-out.txt is the output of combination-mod-demo.cc.
Description:
Combinations in strong minimal-change order.
Iterative generation via modulo moves.
The demo uses the functions from
combination-mod.h (fxt/src/comb/combination-mod.h)
combination-pref-out.txt is the output of combination-pref-demo.cc.
Description:
Combinations via prefix shifts ("cool-lex" order)
The demo uses the functions from
combination-pref.h (fxt/src/comb/combination-pref.h)
combination-rank-out.txt is the output of combination-rank-demo.cc.
Description:
Ranking and unranking combinations in near-perfect order
The demo uses the functions from
composition-rank.h (fxt/src/comb/composition-rank.h)
composition-rank.cc (fxt/src/comb/composition-rank.cc)
comp2comb.h (fxt/src/comb/comp2comb.h)
combination-rec-out.txt is the output of combination-rec-demo.cc.
Description:
Combinations in lexicographic, Gray code,
complemented enup, and complemented Eades-McKay order.
The demo uses the functions from
combination-rec.h (fxt/src/comb/combination-rec.h)
combination-rec.cc (fxt/src/comb/combination-rec.cc)
combination-revdoor-out.txt is the output of combination-revdoor-demo.cc.
Description:
Generating all combinations in minimal-change order: revolving door algorithm.
The demo uses the functions from
combination-revdoor.h (fxt/src/comb/combination-revdoor.h)
composition-colex-out.txt is the output of composition-colex-demo.cc.
Description:
Generating all compositions of n into k parts in co-lexicographic (colex) order.
The demo uses the functions from
composition-colex.h (fxt/src/comb/composition-colex.h)
comp2comb.h (fxt/src/comb/comp2comb.h)
composition-colex2-out.txt is the output of composition-colex2-demo.cc.
Description:
Generating all compositions of n into k parts in co-lexicographic (colex) order.
Algorithm efficient also with sparse case, i.e. k much greater than n.
The demo uses the functions from
composition-colex2.h (fxt/src/comb/composition-colex2.h)
comp2comb.h (fxt/src/comb/comp2comb.h)
composition-ex-colex-out.txt is the output of composition-ex-colex-demo.cc.
Description:
Compositions of n into exactly k parts in co-lexicographic (colex) order.
The demo uses the functions from
composition-ex-colex.h (fxt/src/comb/composition-ex-colex.h)
composition-gray-rec-out.txt is the output of composition-gray-rec-demo.cc.
Description:
Generating all compositions of n into k parts in minimal-change order.
The demo uses the functions from
comp2comb.h (fxt/src/comb/comp2comb.h)
comb-print.h (fxt/src/comb/comb-print.h)
composition-nz-out.txt is the output of composition-nz-demo.cc.
Description:
Compositions of n into nonzero parts.
The demo uses the functions from
composition-nz.h (fxt/src/comb/composition-nz.h)
composition-rank-out.txt is the output of composition-rank-demo.cc.
Description:
Ranking and unranking compositions
in lexicographic, Gray, and enup (two-close) order
The demo uses the functions from
composition-rank.h (fxt/src/comb/composition-rank.h)
num-compositions.h (fxt/src/comb/num-compositions.h)
conference-quadres-out.txt is the output of conference-quadres-demo.cc.
Description:
Conference and Hadamard matrices by quadratic residues
The demo uses the functions from
matrix.h (fxt/src/matrix/matrix.h)
copy.h (fxt/src/aux1/copy.h)
cyclic-perm-out.txt is the output of cyclic-perm-demo.cc.
Description:
Generate all cyclic permutations in minimal-change order, CAT algorithm.
The demo uses the functions from
cyclic-perm.h (fxt/src/comb/cyclic-perm.h)
fact2cyclic.cc (fxt/src/comb/fact2cyclic.cc)
mixedradix-gray.h (fxt/src/comb/mixedradix-gray.h)
debruijn-out.txt is the output of debruijn-demo.cc.
Description:
Generating De Bruijn sequences.
The demo uses the functions from
debruijn.h (fxt/src/comb/debruijn.h)
necklace.h (fxt/src/comb/necklace.h)
dyck-gray-out.txt is the output of dyck-gray-demo.cc.
Description:
Gray code for k-ary Dyck words.
Loopless algorithm, all changes are homogeneous.
The demo uses the functions from
dyck-gray.h (fxt/src/comb/dyck-gray.h)
dyck-gray2-out.txt is the output of dyck-gray2-demo.cc.
Description:
Gray code for k-ary Dyck words.
Loopless algorithm, homogeneous two-close changes.
The demo uses the functions from
dyck-gray2.h (fxt/src/comb/dyck-gray2.h)
dyck-pref-out.txt is the output of dyck-pref-demo.cc.
Description:
k-ary Dyck words via prefix shifts.
The demo uses the functions from
dyck-pref.h (fxt/src/comb/dyck-pref.h)
dyck-pref2-out.txt is the output of dyck-pref2-demo.cc.
Description:
k-ary Dyck words via prefix shifts (loopless generation).
The demo uses the functions from
dyck-pref2.h (fxt/src/comb/dyck-pref2.h)
dyck-rgs-out.txt is the output of dyck-rgs-demo.cc.
Description:
All restricted growth strings (RGS) for k-ary Dyck words in lexicographic order:
strings s[0,...,n-1] such that s[k] <= s[k-1]+i (where i=k-1).
The demo uses the functions from
dyck-rgs.h (fxt/src/comb/dyck-rgs.h)
fact2cyclic-out.txt is the output of fact2cyclic-demo.cc.
Description:
Generate all cyclic permutations from mixed radix numbers.
The demo uses the functions from
fact2perm.h (fxt/src/comb/fact2perm.h)
fact2cyclic.cc (fxt/src/comb/fact2cyclic.cc)
mixedradix-modular-gray.h (fxt/src/comb/mixedradix-modular-gray.h)
perminvert.h (fxt/src/perm/perminvert.h)
permq.h (fxt/src/perm/permq.h)
fact2perm-out.txt is the output of fact2perm-demo.cc.
Description:
Generate all permutations from mixed radix (factorial) numbers.
The demo uses the functions from
fact2perm.h (fxt/src/comb/fact2perm.h)
fact2perm.cc (fxt/src/comb/fact2perm.cc)
mixedradix-lex.h (fxt/src/comb/mixedradix-lex.h)
reverse.h (fxt/src/perm/reverse.h)
permcomplement.h (fxt/src/perm/permcomplement.h)
perminvert.h (fxt/src/perm/perminvert.h)
fact2perm-rev-out.txt is the output of fact2perm-rev-demo.cc.
Description:
Generate all permutations from mixed radix (factorial) numbers.
The demo uses the functions from
fact2perm.h (fxt/src/comb/fact2perm.h)
fact2perm-rev.cc (fxt/src/comb/fact2perm-rev.cc)
perminvert.h (fxt/src/perm/perminvert.h)
perminvert.cc (fxt/src/perm/perminvert.cc)
mixedradix-lex.h (fxt/src/comb/mixedradix-lex.h)
fact2perm-rot-out.txt is the output of fact2perm-rot-demo.cc.
Description:
Generate all permutations from mixed radix (factorial) numbers.
The demo uses the functions from
fact2perm.h (fxt/src/comb/fact2perm.h)
fact2perm-rot.cc (fxt/src/comb/fact2perm-rot.cc)
perminvert.h (fxt/src/perm/perminvert.h)
perminvert.cc (fxt/src/perm/perminvert.cc)
mixedradix-lex.h (fxt/src/comb/mixedradix-lex.h)
fact2perm-swp-out.txt is the output of fact2perm-swp-demo.cc.
Description:
Generate all permutations from mixed radix (factorial) numbers.
The demo uses the functions from
fact2perm.h (fxt/src/comb/fact2perm.h)
fact2perm-swp.cc (fxt/src/comb/fact2perm-swp.cc)
perminvert.h (fxt/src/perm/perminvert.h)
perminvert.cc (fxt/src/perm/perminvert.cc)
mixedradix-lex.h (fxt/src/comb/mixedradix-lex.h)
ffact2kperm-out.txt is the output of ffact2kperm-demo.cc.
Description:
Generate all k-permutations of n elements from falling factorial numbers.
The demo uses the functions from
fact2perm.h (fxt/src/comb/fact2perm.h)
fact2perm.cc (fxt/src/comb/fact2perm.cc)
mixedradix-lex.h (fxt/src/comb/mixedradix-lex.h)
fib-alt-gray-out.txt is the output of fib-alt-gray-demo.cc.
Description:
Gray codes for certain ternary words counted by Fibonacci numbers
fibgray-rec-out.txt is the output of fibgray-rec-demo.cc.
Description:
Gray code for Fibonacci words, recursive CAT algorithm
gexz-gray-out.txt is the output of gexz-gray-demo.cc.
Description:
Gray code for r-ary words where digit x is followed by x or more zeros.
hadamard-srs-out.txt is the output of hadamard-srs-demo.cc.
Description:
Hadamard matrices by maximum length shift register sequences (SRS)
The demo uses the functions from
lfsr.h (fxt/src/bpol/lfsr.h)
matrix.h (fxt/src/matrix/matrix.h)
copy.h (fxt/src/aux1/copy.h)
hanoi-rec-out.txt is the output of hanoi-rec-demo.cc.
Description:
Towers of Hanoi, recursive algorithm.
hilbert-ndim-out.txt is the output of hilbert-ndim-demo.cc.
Description:
Lunnon's recursion algorithm for the n-dimensional Hilbert curve
The demo uses the functions from
hilbert-ndim.h (fxt/src/comb/hilbert-ndim.h)
hilbert-ndim-rec-out.txt is the output of hilbert-ndim-rec-demo.cc.
Description:
Lunnon's recursion algorithm for the n-dimensional Hilbert curve
The demo uses the functions from
hilbert-ndim-rec.h (fxt/src/comb/hilbert-ndim-rec.h)
kperm-gray-out.txt is the output of kperm-gray-demo.cc.
Description:
Generate all k-permutations of n elements in minimal-change order
via Gray code for falling factorial numbers, CAT algorithm.
The demo uses the functions from
kperm-gray.h (fxt/src/comb/kperm-gray.h)
kperm-lex-out.txt is the output of kperm-lex-demo.cc.
Description:
Generate all k-permutations of n elements in lexicographic order.
The demo uses the functions from
kperm-lex.h (fxt/src/comb/kperm-lex.h)
kproducts-colex-out.txt is the output of kproducts-colex-demo.cc.
Description:
Generating all k-products of the n smallest primes
via combinations in co-lexicographic order.
The demo uses the functions from
combination-colex.h (fxt/src/comb/combination-colex.h)
primes.h (fxt/src/mod/primes.h)
ksubset-gray-out.txt is the output of ksubset-gray-demo.cc.
Description:
k-subsets (kmin<=k<=kmax) in minimal-change order
The demo uses the functions from
ksubset-gray.h (fxt/src/comb/ksubset-gray.h)
ksubset-rec-out.txt is the output of ksubset-rec-demo.cc.
Description:
k-subsets where kmin<=k<=kmax in various orders.
Recursive CAT algorithm.
The demo uses the functions from
ksubset-rec.h (fxt/src/comb/ksubset-rec.h)
ksubset-rec.cc (fxt/src/comb/ksubset-rec.cc)
ksubset-twoclose-out.txt is the output of ksubset-twoclose-demo.cc.
Description:
k-subsets (kmin<=k<=kmax) in two-close order.
Recursive algorithm.
The demo uses the functions from
ksubset-twoclose.h (fxt/src/comb/ksubset-twoclose.h)
maxrep-gray-out.txt is the output of maxrep-gray-demo.cc.
Description:
Gray code for generalized Fibonacci words, recursive CAT algorithm
mixedradix-endo-out.txt is the output of mixedradix-endo-demo.cc.
Description:
Mixed radix counting: endo sequence
(endo := "Even Numbers DOwn, odd (numbers up)")
The demo uses the functions from
mixedradix-endo.h (fxt/src/comb/mixedradix-endo.h)
endo-enup.h (fxt/src/comb/endo-enup.h)
mixedradix-endo-gray-out.txt is the output of mixedradix-endo-gray-demo.cc.
Description:
Mixed radix counting: endo Gray sequence
(endo := "Even Numbers Down, Odd (numbers up)")
The demo uses the functions from
mixedradix-endo-gray.h (fxt/src/comb/mixedradix-endo-gray.h)
endo-enup.h (fxt/src/comb/endo-enup.h)
mixedradix-gray-out.txt is the output of mixedradix-gray-demo.cc.
Description:
Mixed radix Gray code, CAT algorithm.
The demo uses the functions from
mixedradix-gray.h (fxt/src/comb/mixedradix-gray.h)
mixedradix-gray2-out.txt is the output of mixedradix-gray2-demo.cc.
Description:
Mixed radix Gray code, loopless algorithm.
The demo uses the functions from
mixedradix-gray2.h (fxt/src/comb/mixedradix-gray2.h)
mixedradix-gslex-alt-out.txt is the output of mixedradix-gslex-alt-demo.cc.
Description:
Mixed radix numbers in alternative gslex (generalized subset lex) order.
The demo uses the functions from
mixedradix-gslex-alt.h (fxt/src/comb/mixedradix-gslex-alt.h)
mixedradix-gslex-alt2-out.txt is the output of mixedradix-gslex-alt2-demo.cc.
Description:
Mixed radix numbers in alternative gslex (generalized subset lex) order.
The demo uses the functions from
mixedradix-gslex-alt2.h (fxt/src/comb/mixedradix-gslex-alt2.h)
mixedradix-gslex-out.txt is the output of mixedradix-gslex-demo.cc.
Description:
Mixed radix numbers in gslex (generalized subset lex) order.
The demo uses the functions from
mixedradix-gslex.h (fxt/src/comb/mixedradix-gslex.h)
mixedradix-lex-out.txt is the output of mixedradix-lex-demo.cc.
Description:
Mixed radix counting.
The demo uses the functions from
mixedradix-lex.h (fxt/src/comb/mixedradix-lex.h)
mixedradix-modular-gray-out.txt is the output of mixedradix-modular-gray-demo.cc.
Description:
Modular mixed radix Gray code.
The demo uses the functions from
mixedradix-modular-gray.h (fxt/src/comb/mixedradix-modular-gray.h)
mixedradix-modular-gray2-out.txt is the output of mixedradix-modular-gray2-demo.cc.
Description:
Modular mixed radix Gray code, CAT algorithm.
The demo uses the functions from
mixedradix-modular-gray2.h (fxt/src/comb/mixedradix-modular-gray2.h)
mixedradix-naf-out.txt is the output of mixedradix-naf-demo.cc.
Description:
Mixed radix non-adjacent forms (NAF).
The demo uses the functions from
mixedradix-naf.h (fxt/src/comb/mixedradix-naf.h)
mixedradix-naf-gray-out.txt is the output of mixedradix-naf-gray-demo.cc.
Description:
Gray code for mixed radix non-adjacent forms (NAF).
The demo uses the functions from
mixedradix-naf-gray.h (fxt/src/comb/mixedradix-naf-gray.h)
mixedradix-naf-sl-out.txt is the output of mixedradix-naf-sl-demo.cc.
Description:
Loopless generation of mixed radix non-adjacent forms (NAF) in subset-lex order.
The demo uses the functions from
mixedradix-naf-sl.h (fxt/src/comb/mixedradix-naf-sl.h)
mixedradix-sl-gray-out.txt is the output of mixedradix-sl-gray-demo.cc.
Description:
Mixed radix numbers in a minimal-change order
related so subset-lex order ("SL-Gray" order).
The demo uses the functions from
mixedradix-sl-gray.h (fxt/src/comb/mixedradix-sl-gray.h)
mixedradix-sl-gray-rec-out.txt is the output of mixedradix-sl-gray-rec-demo.cc.
Description:
Recursive generation of mixed radix numbers in a minimal-change order
related so subset-lex order ("SL-Gray" order).
mixedradix-sod-lex-out.txt is the output of mixedradix-sod-lex-demo.cc.
Description:
Mixed radix numbers with fixed sum of digits.
Also: k-subsets (combinations) of a multiset.
The demo uses the functions from
mixedradix-sod-lex.h (fxt/src/comb/mixedradix-sod-lex.h)
mixedradix-subset-lex-out.txt is the output of mixedradix-subset-lex-demo.cc.
Description:
Mixed radix numbers in subset-lexicographic order.
The demo uses the functions from
mixedradix-subset-lex.h (fxt/src/comb/mixedradix-subset-lex.h)
monotonicgray-out.txt is the output of monotonicgray-demo.cc.
Description:
Monotonic Gray path (Savage/Winkler), as given by Knuth.
The demo uses the functions from
monotonic-gray.h (fxt/src/comb/monotonic-gray.h)
monotonic-gray.cc (fxt/src/comb/monotonic-gray.cc)
mpartition-out.txt is the output of mpartition-demo.cc.
Description:
Integer partitions of n into m parts
The demo uses the functions from
mpartition.h (fxt/src/comb/mpartition.h)
mset-ksubset-out.txt is the output of mset-ksubset-demo.cc.
Description:
k-subsets (combinations) of a multiset.
Essentially the same as mixed radix numbers with fixed sum of digits.
The demo uses the functions from
mixedradix-sod-lex.h (fxt/src/comb/mixedradix-sod-lex.h)
mset-lex-out.txt is the output of mset-lex-demo.cc.
Description:
Subsets of a multiset in lexicographic order with respect to subsets,
generated as (multi-)delta-sets (that is, mixed radix numbers).
The demo uses the functions from
mixedradix-subset-lex.h (fxt/src/comb/mixedradix-subset-lex.h)
mset-perm-gray-out.txt is the output of mset-perm-gray-demo.cc.
Description:
All multiset permutations in minimal-change order (Lunnon's Gray code).
Same as: all strings with fixed content.
The demo uses the functions from
mset-perm-gray.h (fxt/src/comb/mset-perm-gray.h)
mset-perm-2invtab.h (fxt/src/comb/mset-perm-2invtab.h)
mset-perm-lex-out.txt is the output of mset-perm-lex-demo.cc.
Description:
All multiset permutations in lexicographic order, iterative generation.
Same as: all strings with fixed content.
The demo uses the functions from
mset-perm-lex.h (fxt/src/comb/mset-perm-lex.h)
mset-perm-2invtab.h (fxt/src/comb/mset-perm-2invtab.h)
mset-perm-lex-rec-out.txt is the output of mset-perm-lex-rec-demo.cc.
Description:
All multiset permutations in lexicographic order, recursive generation.
Same as: all strings with fixed content.
mset-perm-lex-rec2-out.txt is the output of mset-perm-lex-rec2-demo.cc.
Description:
All multiset permutations in lexicographic order.
Recursive generation using a linked list.
Same as: all strings with fixed content.
The demo uses the functions from
mset-perm-lex-rec.h (fxt/src/comb/mset-perm-lex-rec.h)
mset-perm-lex-rec.cc (fxt/src/comb/mset-perm-lex-rec.cc)
mset-perm-pref-out.txt is the output of mset-perm-pref-demo.cc.
Description:
All multiset permutations via prefix shifts ("cool-lex" order)
Same as: all strings with fixed content.
The demo uses the functions from
mset-perm-pref.h (fxt/src/comb/mset-perm-pref.h)
mset-perm-2invtab.h (fxt/src/comb/mset-perm-2invtab.h)
naf-gray-rec-out.txt is the output of naf-gray-rec-demo.cc.
Description:
Gray code for sparse signed binary representation (nonadjacent form, NAF).
Recursive CAT algorithm.
naf-pos-rec-out.txt is the output of naf-pos-rec-demo.cc.
Description:
Near Gray code for sparse signed binary representations (nonadjacent form, NAF)
of the positive numbers. Recursive CAT algorithm.
necklace-cat-out.txt is the output of necklace-cat-demo.cc.
Description:
Generate pre-necklaces as described by Cattell, Ruskey, Sawada, Miers, Serra.
Recursive CAT algorithm.
necklace-out.txt is the output of necklace-demo.cc.
Description:
Generate all pre-necklaces.
The demo uses the functions from
necklace.h (fxt/src/comb/necklace.h)
necklace-fkm-out.txt is the output of necklace-fkm-demo.cc.
Description:
Fredericksen, Kessler, Maiorana (FKM) algorithm for generating necklaces.
necklace-gray-out.txt is the output of necklace-gray-demo.cc.
Description:
Generate binary Lyndon words ordered so that only few changes
between successive elements occur (note: in general not a Gray code).
Recursive CAT algorithm.
necklace-gray3-out.txt is the output of necklace-gray3-demo.cc.
Description:
Generate Gray code (max 3 changes per update) for necklaces
necklace-sigma-tau-out.txt is the output of necklace-sigma-tau-demo.cc.
Description:
necklaces via cyclic shifts and complements (sigma-tau search)
The demo uses the functions from
bitrotate.h (fxt/src/bits/bitrotate.h)
bitcyclic-minmax.h (fxt/src/bits/bitcyclic-minmax.h)
print-bin.h (fxt/src/bits/print-bin.h)
necklaces-via-gray-leaders-out.txt is the output of necklaces-via-gray-leaders-demo.cc.
Description:
Cycle leaders for gray permutation converted to necklaces
The demo uses the functions from
gray-cycle-leaders.h (fxt/src/comb/gray-cycle-leaders.h)
bittransforms.h (fxt/src/bits/bittransforms.h)
bitcyclic-period.h (fxt/src/bits/bitcyclic-period.h)
no111-gray-out.txt is the output of no111-gray-demo.cc.
Description:
Gray code for binary words with no substring 111, recursive CAT algorithm
no1111-gray-out.txt is the output of no1111-gray-demo.cc.
Description:
Gray code for binary words with no substring 1111, recursive CAT algorithm
no1x1-gray-out.txt is the output of no1x1-gray-demo.cc.
Description:
Gray code for binary words with no substring 1x1, recursive CAT algorithm
no1xy1-gray-out.txt is the output of no1xy1-gray-demo.cc.
Description:
Gray code for binary words with no substring 1xy1, recursive CAT algorithm
ntnz-gray-out.txt is the output of ntnz-gray-demo.cc.
Description:
Gray code for strings with no two consecutive nonzero digits.
These are non-adjacent forms (NAF).
ntz-gray-out.txt is the output of ntz-gray-demo.cc.
Description:
Gray code for words without two consecutive zeros, recursive CAT algorithm
num-partitions-out.txt is the output of num-partitions-demo.cc.
Description:
Number of integer partitions.
paren-out.txt is the output of paren-demo.cc.
Description:
Generate all well-formed pairs of parentheses in co-lexicographic order.
The demo uses the functions from
paren.h (fxt/src/comb/paren.h)
paren-gray-out.txt is the output of paren-gray-demo.cc.
Description:
Parentheses strings in minimal-change order (Xiang, Ushijima)
The demo uses the functions from
paren-gray.h (fxt/src/comb/paren-gray.h)
paren-gray-rec-out.txt is the output of paren-gray-rec-demo.cc.
Description:
Gray code for paren strings via restricted growth strings (RGS), recursive algorithm.
paren-pref-out.txt is the output of paren-pref-demo.cc.
Description:
Generate all well-formed pairs of parentheses by prefix shifts
The demo uses the functions from
paren-pref.h (fxt/src/comb/paren-pref.h)
partition-out.txt is the output of partition-demo.cc.
Description:
Generate all integer partitions, iterative algorithm.
The demo uses the functions from
partition.h (fxt/src/comb/partition.h)
partition-dist-lex-rec-out.txt is the output of partition-dist-lex-rec-demo.cc.
Description:
Generate all integer partitions into distinct part in lexicographic order, recursive algorithm.
partition-gen-out.txt is the output of partition-gen-demo.cc.
Description:
Generate all integer partitions, with parts repeated at most r times.
The demo uses the functions from
partition-gen.h (fxt/src/comb/partition-gen.h)
partition-lex-rec-out.txt is the output of partition-lex-rec-demo.cc.
Description:
Generate all integer partitions in lexicographic order, recursive algorithm.
partition-refined-out.txt is the output of partition-refined-demo.cc.
Description:
Generate all maximally refined partitions.
See http://oeis.org/A179009 for the definition of a maximally refined partition.
pascal-out.txt is the output of pascal-demo.cc.
Description:
Pascal triangle.
pellgen-gray-out.txt is the output of pellgen-gray-demo.cc.
Description:
Gray code for generalized Pell words, recursive CAT algorithm
pellgray-rec-out.txt is the output of pellgray-rec-demo.cc.
Description:
Gray code for Pell words, recursive CAT algorithm
perm-colex-out.txt is the output of perm-colex-demo.cc.
Description:
Generate all permutations in co-lexicographic (colex) order
The demo uses the functions from
perm-colex.h (fxt/src/comb/perm-colex.h)
perm-derange-out.txt is the output of perm-derange-demo.cc.
Description:
Generate all permutations in derangement order.
The demo uses the functions from
perm-derange.h (fxt/src/comb/perm-derange.h)
perm-trotter.h (fxt/src/comb/perm-trotter.h)
perm-dist1-gray-out.txt is the output of perm-dist1-gray-demo.cc.
Description:
Gray code for permutations where i-1<=p(i)<=i+1 for all i, generated via
Gray code for falling factorial numbers that are Fibonacci numbers
The demo uses the functions from
fact2perm.h (fxt/src/comb/fact2perm.h)
perminvert.h (fxt/src/perm/perminvert.h)
reverse.h (fxt/src/perm/reverse.h)
perm-genus-out.txt is the output of perm-genus-demo.cc.
Description:
Genus of all permutations of n elements.
Print parenthesis strings for permutations of genus zero.
The demo uses the functions from
perm-genus.h (fxt/src/perm/perm-genus.h)
perm-lex-inv.h (fxt/src/comb/perm-lex-inv.h)
perm-gray-ffact-out.txt is the output of perm-gray-ffact-demo.cc.
Description:
Generate all permutations in minimal-change order
via Gray code for falling factorial numbers, CAT algorithm.
The demo uses the functions from
perm-gray-ffact.h (fxt/src/comb/perm-gray-ffact.h)
perm-gray-ffact2-out.txt is the output of perm-gray-ffact2-demo.cc.
Description:
Generate all permutations in minimal-change order
via Gray code for falling factorial numbers, loopless algorithm.
The demo uses the functions from
perm-gray-ffact2.h (fxt/src/comb/perm-gray-ffact2.h)
mixedradix-gray2.h (fxt/src/comb/mixedradix-gray2.h)
perm-gray-lipski-out.txt is the output of perm-gray-lipski-demo.cc.
Description:
Four Gray codes for permutations, CAT algorithm.
The demo uses the functions from
perm-gray-lipski.h (fxt/src/comb/perm-gray-lipski.h)
perm-gray-rfact-out.txt is the output of perm-gray-rfact-demo.cc.
Description:
Generate all permutations in minimal-change order
via Gray code for rising factorial numbers, CAT algorithm.
The demo uses the functions from
perm-gray-rfact.h (fxt/src/comb/perm-gray-rfact.h)
mixedradix-gray.h (fxt/src/comb/mixedradix-gray.h)
perm-gray-rot1-out.txt is the output of perm-gray-rot1-demo.cc.
Description:
Generate all permutations in minimal-change order such that
in the last permutations the first e elements are cyclically
rotated by one where e is the greatest even number <=n.
The demo uses the functions from
perm-gray-rot1.h (fxt/src/comb/perm-gray-rot1.h)
mixedradix-gray.h (fxt/src/comb/mixedradix-gray.h)
perm-gray-wells-out.txt is the output of perm-gray-wells-demo.cc.
Description:
Two Gray codes for permutations (Wells' order and a variant of it), CAT algorithm.
The demo uses the functions from
perm-gray-wells.h (fxt/src/comb/perm-gray-wells.h)
perm-heap-out.txt is the output of perm-heap-demo.cc.
Description:
Gray code for permutations, CAT algorithm.
Algorithm following B.R.Heap (1963)
The demo uses the functions from
perm-heap.h (fxt/src/comb/perm-heap.h)
fact2perm.h (fxt/src/comb/fact2perm.h)
perm-heap2-out.txt is the output of perm-heap2-demo.cc.
Description:
Gray code for permutations, CAT algorithm, optimized version.
Algorithm following B.R.Heap (1963)
The demo uses the functions from
perm-heap2.h (fxt/src/comb/perm-heap2.h)
perm-heap2-swaps-out.txt is the output of perm-heap2-swaps-demo.cc.
Description:
Swaps for Gray code for permutations, CAT algorithm, optimized version.
Algorithm following B.R.Heap (1963)
The demo uses the functions from
perm-heap2-swaps.h (fxt/src/comb/perm-heap2-swaps.h)
perm-involution-out.txt is the output of perm-involution-demo.cc.
Description:
Generate all involutions (self-inverse permutations).
The demo uses the functions from
perm-involution.h (fxt/src/comb/perm-involution.h)
perm-involution-naf-out.txt is the output of perm-involution-naf-demo.cc.
Description:
Self-inverse permutations (involutions) from falling factorial numbers
that are non-adjacent forms (NAF).
The demo uses the functions from
mixedradix-naf.h (fxt/src/comb/mixedradix-naf.h)
perm-ives-out.txt is the output of perm-ives-demo.cc.
Description:
Permutations in the order c by Ives (inverse permutations are Ives' order a).
The demo uses the functions from
perm-ives.h (fxt/src/comb/perm-ives.h)
perm-l1r2-gray-out.txt is the output of perm-l1r2-gray-demo.cc.
Description:
Gray code for permutations where i-1<=p(i)<=i+2 for all i, generated via
Gray code for falling factorial numbers that are tribonacci numbers
The demo uses the functions from
fact2perm.h (fxt/src/comb/fact2perm.h)
perminvert.h (fxt/src/perm/perminvert.h)
reverse.h (fxt/src/perm/reverse.h)
perm-lex-cycles-out.txt is the output of perm-lex-cycles-demo.cc.
Description:
Generate all permutations in lexicographic order, show cycles and inversion tables.
The demo uses the functions from
perm-lex.h (fxt/src/comb/perm-lex.h)
printcycles.h (fxt/src/perm/printcycles.h)
fact2perm.h (fxt/src/comb/fact2perm.h)
perm-lex-out.txt is the output of perm-lex-demo.cc.
Description:
Generate all permutations in lexicographic order.
The demo uses the functions from
perm-lex.h (fxt/src/comb/perm-lex.h)
perm-lex-inv-out.txt is the output of perm-lex-inv-demo.cc.
Description:
Generate all permutations in lexicographic order.
The demo uses the functions from
perm-lex-inv.h (fxt/src/comb/perm-lex-inv.h)
perm-lex2-out.txt is the output of perm-lex2-demo.cc.
Description:
Generate all permutations in lexicographic order
The demo uses the functions from
perm-lex2.h (fxt/src/comb/perm-lex2.h)
perm-mv0-out.txt is the output of perm-mv0-demo.cc.
Description:
Generate all inverse permutations with falling factorial numbers, CAT algorithm.
The demo uses the functions from
perm-mv0.h (fxt/src/comb/perm-mv0.h)
perm-pref-out.txt is the output of perm-pref-demo.cc.
Description:
All permutations via prefix shifts ("cool-lex" order)
The demo uses the functions from
perm-pref.h (fxt/src/comb/perm-pref.h)
perm-rec-out.txt is the output of perm-rec-demo.cc.
Description:
All cyclic permutations by an recursive algorithm.
The demo uses the functions from
perm-rec.h (fxt/src/comb/perm-rec.h)
fact2perm.h (fxt/src/comb/fact2perm.h)
perm-restrpref-out.txt is the output of perm-restrpref-demo.cc.
Description:
Permutations with restricted prefixes
The demo uses the functions from
perm-restrpref.h (fxt/src/comb/perm-restrpref.h)
perm-rev-out.txt is the output of perm-rev-demo.cc.
Description:
Permutations by prefix reversals, CAT algorithm.
The demo uses the functions from
perm-rev.h (fxt/src/comb/perm-rev.h)
perm-rev2-out.txt is the output of perm-rev2-demo.cc.
Description:
Permutations by prefix reversals, CAT algorithm.
The demo uses the functions from
perm-rev2.h (fxt/src/comb/perm-rev2.h)
perm-right1-gray-out.txt is the output of perm-right1-gray-demo.cc.
Description:
Gray code for permutations where p(i)<=i+1 for all i, generated via
Gray code for falling factorial numbers where digit x is followed by x or more zeros.
The demo uses the functions from
fact2perm.h (fxt/src/comb/fact2perm.h)
perminvert.h (fxt/src/perm/perminvert.h)
reverse.h (fxt/src/perm/reverse.h)
perm-rot-out.txt is the output of perm-rot-demo.cc.
Description:
All permutations, by rotations (cyclic shifts).
The demo uses the functions from
perm-rot.h (fxt/src/comb/perm-rot.h)
perminvert.h (fxt/src/perm/perminvert.h)
perminvert.cc (fxt/src/perm/perminvert.cc)
perm-rot-unrank-out.txt is the output of perm-rot-unrank-demo.cc.
Description:
Unranking for permutations by rotations (cyclic shifts).
The demo uses the functions from
mixedradix-lex.h (fxt/src/comb/mixedradix-lex.h)
rotate.h (fxt/src/perm/rotate.h)
perminvert.h (fxt/src/perm/perminvert.h)
perminvert.cc (fxt/src/perm/perminvert.cc)
perm-st-out.txt is the output of perm-st-demo.cc.
Description:
Single track ordering for permutations, CAT algorithm.
The demo uses the functions from
perm-st.h (fxt/src/comb/perm-st.h)
endo-enup.h (fxt/src/comb/endo-enup.h)
perm-st-gray-out.txt is the output of perm-st-gray-demo.cc.
Description:
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).
The demo uses the functions from
perm-st-gray.h (fxt/src/comb/perm-st-gray.h)
perm-gray-rot1.h (fxt/src/comb/perm-gray-rot1.h)
mixedradix-gray.h (fxt/src/comb/mixedradix-gray.h)
perm-st-pref-out.txt is the output of perm-st-pref-demo.cc.
Description:
Single track ordering for permutations, swaps in prefix, CAT algorithm.
The demo uses the functions from
perm-st-pref.h (fxt/src/comb/perm-st-pref.h)
endo-enup.h (fxt/src/comb/endo-enup.h)
perm-star-out.txt is the output of perm-star-demo.cc.
Description:
Generate all permutations in star-transposition order.
The demo uses the functions from
perm-star.h (fxt/src/comb/perm-star.h)
perm-star-inv-out.txt is the output of perm-star-inv-demo.cc.
Description:
Inverse star transposition permutations via permutations by prefix reversals.
The demo uses the functions from
perm-rev2.h (fxt/src/comb/perm-rev2.h)
perm-star-swaps-out.txt is the output of perm-star-swaps-demo.cc.
Description:
Generate swaps for permutations in star-transpostion order.
The demo uses the functions from
perm-star-swaps.h (fxt/src/comb/perm-star-swaps.h)
perm-trotter-out.txt is the output of perm-trotter-demo.cc.
Description:
Generate all permutations in strong minimal-change order using Trotter's algorithm.
Smallest element moves most often.
The demo uses the functions from
perm-trotter.h (fxt/src/comb/perm-trotter.h)
perm-trotter-lg-out.txt is the output of perm-trotter-lg-demo.cc.
Description:
Generate all permutations in strong minimal-change order using Trotter's algorithm.
Largest element moves most often.
The demo uses the functions from
perm-trotter-lg.h (fxt/src/comb/perm-trotter-lg.h)
perm2fact-out.txt is the output of perm2fact-demo.cc.
Description:
Show factorial representations (Lehmer, rev, rot, and swap) of permutations.
The demo uses the functions from
fact2perm.h (fxt/src/comb/fact2perm.h)
fact2perm.cc (fxt/src/comb/fact2perm.cc)
fact2perm-rev.cc (fxt/src/comb/fact2perm-rev.cc)
fact2perm-rot.cc (fxt/src/comb/fact2perm-rot.cc)
fact2perm-swp.cc (fxt/src/comb/fact2perm-swp.cc)
rgs-fincr-out.txt is the output of rgs-fincr-demo.cc.
Description:
All restricted growth strings (RGS) s[0,...,n-1]
so that s[k] <= F[j]+i where
F[0]=i, F[j+1]=( a[j+1]-a[j]==i ? F[j]+i : F[j] )
Lexicographic order
The demo uses the functions from
rgs-fincr.h (fxt/src/comb/rgs-fincr.h)
rgs-kincr-out.txt is the output of rgs-kincr-demo.cc.
Description:
All Restricted growth strings (RGS) s[0,...,n-1] so that s[k] <= s[k-1]+k
Lexicographic order.
The demo uses the functions from
rgs-kincr.h (fxt/src/comb/rgs-kincr.h)
rgs-maxincr-out.txt is the output of rgs-maxincr-demo.cc.
Description:
All restricted growth strings (RGS) s[0,...,n-1]
so that s[k] <= max( j < k, s[j] + i )
Lexicographic order
The demo uses the functions from
rgs-maxincr.h (fxt/src/comb/rgs-maxincr.h)
rll-rec-out.txt is the output of rll-rec-demo.cc.
Description:
Run length limited (RLL) words (at most 2 identical consecutive bits),
recursive CAT algorithm.
root-sums-out.txt is the output of root-sums-demo.cc.
Description:
Zero-sums of roots of unity.
The demo uses the functions from
binary-necklace.h (fxt/src/comb/binary-necklace.h)
ruler-func-out.txt is the output of ruler-func-demo.cc.
Description:
Ruler function sequence.
The demo uses the functions from
ruler-func.h (fxt/src/comb/ruler-func.h)
schroeder-tree-out.txt is the output of schroeder-tree-demo.cc.
Description:
Generates all Schroeder trees with m-leaf nodes
setpart-out.txt is the output of setpart-demo.cc.
Description:
Set partitions.
The demo uses the functions from
setpart.h (fxt/src/comb/setpart.h)
setpart.cc (fxt/src/comb/setpart.cc)
setpart-p-rgs-lex-out.txt is the output of setpart-p-rgs-lex-demo.cc.
Description:
Set partitions into p parts as restricted growth strings (RGS).
The demo uses the functions from
setpart-p-rgs-lex.h (fxt/src/comb/setpart-p-rgs-lex.h)
setpart-rgs-gray-out.txt is the output of setpart-rgs-gray-demo.cc.
Description:
Set partitions as restricted growth strings (RGS).
The demo uses the functions from
setpart-rgs-gray.h (fxt/src/comb/setpart-rgs-gray.h)
setpart-rgs-lex-out.txt is the output of setpart-rgs-lex-demo.cc.
Description:
Set partitions as restricted growth strings (RGS).
The demo uses the functions from
setpart-rgs-lex.h (fxt/src/comb/setpart-rgs-lex.h)
shift-subsets-out.txt is the output of shift-subsets-demo.cc.
Description:
Shifts-order for subsets of a binary word.
stirling1-out.txt is the output of stirling1-demo.cc.
Description:
Stirling numbers of the first kind (Stirling cycle numbers).
stirling2-out.txt is the output of stirling2-demo.cc.
Description:
Stirling numbers of the second kind (set numbers) and Bell numbers.
stringsubst-out.txt is the output of stringsubst-demo.cc.
Description:
String substitution engine (Lindenmayer system, or L-system).
The demo uses the functions from
stringsubst.h (fxt/src/comb/stringsubst.h)
stringsubst-hilbert3d-out.txt is the output of stringsubst-hilbert3d-demo.cc.
Description:
Hilbert's (3-dimensional) space filling curve generated by string substitution.
The demo uses the functions from
stringsubst.h (fxt/src/comb/stringsubst.h)
subset-debruijn-out.txt is the output of subset-debruijn-demo.cc.
Description:
Generate all subsets in De Bruijn order.
The demo uses the functions from
subset-debruijn.h (fxt/src/comb/subset-debruijn.h)
debruijn.h (fxt/src/comb/debruijn.h)
necklace.h (fxt/src/comb/necklace.h)
subset-deltalex-out.txt is the output of subset-deltalex-demo.cc.
Description:
All subsets in lexicographic order with respect to delta sets.
The demo uses the functions from
subset-deltalex.h (fxt/src/comb/subset-deltalex.h)
comb-print.h (fxt/src/comb/comb-print.h)
subset-gray-delta-out.txt is the output of subset-gray-delta-demo.cc.
Description:
Generate all subsets (as delta sets) in minimal-change order.
The demo uses the functions from
subset-gray-delta.h (fxt/src/comb/subset-gray-delta.h)
subset-gray-out.txt is the output of subset-gray-demo.cc.
Description:
Generate all subsets in minimal-change order.
The demo uses the functions from
subset-gray.h (fxt/src/comb/subset-gray.h)
subset-lex-out.txt is the output of subset-lex-demo.cc.
Description:
Generate all subsets in lexicographic order.
The demo uses the functions from
subset-lex.h (fxt/src/comb/subset-lex.h)
subset-monotone-out.txt is the output of subset-monotone-demo.cc.
Description:
Generate all subsets in monotone order.
The demo uses the functions from
subset-monotone.h (fxt/src/comb/subset-monotone.h)