You may want to look at the outputs first.
acgray-out.txt is the output of acgray-demo.cc.
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)
acyclic-map-out.txt is the output of acyclic-map-demo.cc.
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.
The demo uses the functions from
acyclic-map.h (fxt/src/comb/acyclic-map.h)
arrangement-lex-out.txt is the output of arrangement-lex-demo.cc.
Arrangements (all permutations of all subsets).
Lexicographic order.
Cf. OEIS sequence A000522.
The demo uses the functions from
arrangement-lex.h (fxt/src/comb/arrangement-lex.h)
arrangement-rgs-out.txt is the output of arrangement-rgs-demo.cc.
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.
The demo uses the functions from
arrangement-rgs.h (fxt/src/comb/arrangement-rgs.h)
print-arrangement-rgs-perm.h (fxt/src/comb/print-arrangement-rgs-perm.h)
ascent-alt-rgs-out.txt is the output of ascent-alt-rgs-demo.cc.
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.
Cf. OEIS sequence A022493.
The demo uses the functions from
ascent-alt-rgs.h (fxt/src/comb/ascent-alt-rgs.h)
ascent-nonflat-rgs-out.txt is the output of ascent-nonflat-rgs-demo.cc.
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) <= asc([d(1), d(2), ..., d(k-1)]) and asc(.) counts the number
of ascents of its argument.
Cf. OEIS sequence A138265.
The demo uses the functions from
ascent-nonflat-rgs.h (fxt/src/comb/ascent-nonflat-rgs.h)
ascent-rgs-out.txt is the output of ascent-rgs-demo.cc.
Ascent sequences (restricted growth strings, RGS).
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.
Lexicographic order.
Cf. OEIS sequence A022493.
The demo uses the functions from
ascent-rgs.h (fxt/src/comb/ascent-rgs.h)
ascent-rgs-stats-out.txt is the output of ascent-rgs-stats-demo.cc.
Statistics for ascent sequences.
Cf. the following OEIS sequences:
A218577:
triangle, length-n ascent sequences with maximal element k-1.
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.
A137251: ascent sequences with k ascents.
A175579: ascent sequences with k zeros.
A218579: ascent sequences with position of last zero at index k-1.
A218580: ascent sequences with position of first occurrence of maximal value at index k-1.
A218581: ascent sequences with position of last occurrence of maximal value at index k-1.
The demo uses the functions from
ascent-rgs.h (fxt/src/comb/ascent-rgs.h)
word-stats.h (fxt/src/comb/word-stats.h)
ascent-rgs-subset-lex-out.txt is the output of ascent-rgs-subset-lex-demo.cc.
Ascent sequences (restricted growth strings, RGS) in 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.
Cf. OEIS sequence A022493.
The demo uses the functions from
ascent-rgs-subset-lex.h (fxt/src/comb/ascent-rgs-subset-lex.h)
balanced-ordered-tree-lev-seq-out.txt is the output of balanced-ordered-tree-lev-seq-demo.cc.
Level sequences for ordered balanced rooted trees.
Lexicographic order.
See OEIS sequences A079500 and A007059.
The demo uses the functions from
balanced-ordered-tree-lev-seq.h (fxt/src/comb/balanced-ordered-tree-lev-seq.h)
balanced-ordered-tree-lev-seq-stats-out.txt is the output of balanced-ordered-tree-lev-seq-stats-demo.cc.
Statistics for (level sequences of) ordered balanced rooted trees.
Cf. the following OEIS sequences:
A079500 and A007059: all trees.
A048887: trees by height.
The demo uses the functions from
balanced-ordered-tree-lev-seq.h (fxt/src/comb/balanced-ordered-tree-lev-seq.h)
word-stats.h (fxt/src/comb/word-stats.h)
ballot-seq-stats-out.txt is the output of ballot-seq-stats-demo.cc.
Statistics for ballot sequences (and standard Young tableaux):
Cf. the following OEIS sequences:
A161126, A238121, A238123, A238125, A238128, and A238129.
The demo uses the functions from
young-tab-rgs.h (fxt/src/comb/young-tab-rgs.h)
word-stats.h (fxt/src/comb/word-stats.h)
young-tab-rgs-descents.h (fxt/src/comb/young-tab-rgs-descents.h)
bell-number-out.txt is the output of bell-number-demo.cc.
Aitken's array and Bell numbers.
Cf. OEIS sequence A011971: Aitken's array,
also called Bell triangle or Peirce triangle.
big-fact2perm-out.txt is the output of big-fact2perm-demo.cc.
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.
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-huffman-out.txt is the output of binary-huffman-demo.cc.
Partitions of 1 into n powers of 1/2:
1 == a[0]/1 + a[1]/2 + a[2]/4 + a[3]/8 + ... a[m]/(2^m) (for n>=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.
The demo uses the functions from
binary-huffman.h (fxt/src/comb/binary-huffman.h)
binary-necklace-out.txt is the output of binary-necklace-demo.cc.
Binary pre-necklaces, necklaces, and Lyndon words: CAT generation.
Cf. OEIS sequences A062692 (pre-necklaces), A000031 (necklaces),
and A001037 (Lyndon words).
The demo uses the functions from
binary-necklace.h (fxt/src/comb/binary-necklace.h)
binary-rot-out.txt is the output of binary-rot-demo.cc.
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).
The demo uses the functions from
binary-rot.h (fxt/src/comb/binary-rot.h)
rotate.h (fxt/src/perm/rotate.h)
comb-print.h (fxt/src/comb/comb-print.h)
binary-sl-gray-out.txt is the output of binary-sl-gray-demo.cc.
Binary numbers in a minimal-change order
related so subset-lex order ("SL-Gray" order).
Representation as delta-sets (binary words).
Loopless generation, only O(1) data beyond the array of bits.
Cf. OEIS sequence A217262.
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.
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.
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)
is-catalan-rgs.h (fxt/src/comb/is-catalan-rgs.h)
catalan-flat-path-lex-out.txt is the output of catalan-flat-path-lex-demo.cc.
Catalan paths allowing flat steps, lexicographic order, CAT algorithm.
The demo uses the functions from
catalan-flat-path-lex.h (fxt/src/comb/catalan-flat-path-lex.h)
catalan-number-out.txt is the output of catalan-number-demo.cc.
Catalan numbers and ballot numbers.
Cf. OEIS sequences A009766 (Catalan's triangle) and A033184.
catalan-path-lex-out.txt is the output of catalan-path-lex-demo.cc.
Catalan paths in lexicographic order, CAT algorithm.
The demo uses the functions from
catalan-path-lex.h (fxt/src/comb/catalan-path-lex.h)
catalan-rgs-out.txt is the output of catalan-rgs-demo.cc.
Catalan restricted growth strings (RGS):
strings a[0,1,...,n-1] where a[0]=0 and a[k] <= a[k-1] + 1.
Lexicographic order.
See OEIS sequences A000108 (Catalan numbers) and A239903 (Catalan RGS).
The demo uses the functions from
catalan-rgs.h (fxt/src/comb/catalan-rgs.h)
paren-string-to-rgs.h (fxt/src/comb/paren-string-to-rgs.h)
paren-string-to-rgs.cc (fxt/src/comb/paren-string-to-rgs.cc)
catalan-rgs-gray-out.txt is the output of catalan-rgs-gray-demo.cc.
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).
The demo uses the functions from
catalan-rgs-gray.h (fxt/src/comb/catalan-rgs-gray.h)
paren-string-to-rgs.h (fxt/src/comb/paren-string-to-rgs.h)
catalan-rgs-gslex-out.txt is the output of catalan-rgs-gslex-demo.cc.
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.
The demo uses the functions from
catalan-rgs-gslex.h (fxt/src/comb/catalan-rgs-gslex.h)
catalan-rgs-subset-lex-out.txt is the output of catalan-rgs-subset-lex-demo.cc.
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.
The demo uses the functions from
catalan-rgs-subset-lex.h (fxt/src/comb/catalan-rgs-subset-lex.h)
catalan-rgs-to-noncrossing-setpart-rgs-out.txt is the output of catalan-rgs-to-noncrossing-setpart-rgs-demo.cc.
Compute RGS for noncrossing set partitions from Catalan RGS.
Lexicographic order.
The demo uses the functions from
catalan-rgs-to-noncrossing-setpart-rgs.h (fxt/src/comb/catalan-rgs-to-noncrossing-setpart-rgs.h)
is-noncrossing-setpart-rgs.h (fxt/src/comb/is-noncrossing-setpart-rgs.h)
catalan-rgs.h (fxt/src/comb/catalan-rgs.h)
catalan-step-rgs-colex-out.txt is the output of catalan-step-rgs-colex-demo.cc.
Catalan (step-)RGS for lattice paths from (0,0) to (n,n)
that do not go below the diagonal (k, k) for 0 <= k <= n.
Co-lexicographic order.
Cf. OEIS sequence A000108.
The demo uses the functions from
catalan-step-rgs-colex.h (fxt/src/comb/catalan-step-rgs-colex.h)
is-catalan-step-rgs.h (fxt/src/comb/is-catalan-step-rgs.h)
catalan-step-rgs-lex-out.txt is the output of catalan-step-rgs-lex-demo.cc.
Catalan (step-)RGS for lattice paths from (0,0) to (n,n)
that do not go below the diagonal (k, k) for 0 <= k <= n.
Lexicographic order.
Cf. OEIS sequence A000108.
The demo uses the functions from
catalan-step-rgs-lex.h (fxt/src/comb/catalan-step-rgs-lex.h)
is-catalan-step-rgs.h (fxt/src/comb/is-catalan-step-rgs.h)
catalan-step-rgs-to-paren-string.h (fxt/src/comb/catalan-step-rgs-to-paren-string.h)
catalan-step-rgs-subset-lexrev-out.txt is the output of catalan-step-rgs-subset-lexrev-demo.cc.
Catalan (step-)RGS for lattice paths from (0,0) to (n,n)
that do not go below the diagonal (k, k) for 0 <= k <= n.
Subset-lexrev order.
See Joerg Arndt, Subset-lex: did we miss an order?, (2014)
http://arxiv.org/abs/1405.6503
The demo uses the functions from
catalan-step-rgs-subset-lexrev.h (fxt/src/comb/catalan-step-rgs-subset-lexrev.h)
is-catalan-step-rgs.h (fxt/src/comb/is-catalan-step-rgs.h)
cayley-perm-out.txt is the output of cayley-perm-demo.cc.
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 minor order lexicographic.
Cf. OEIS sequence A000670 (Fubini numbers).
The demo uses the functions from
cayley-perm.h (fxt/src/comb/cayley-perm.h)
cayley-perm-stats-out.txt is the output of cayley-perm-stats-demo.cc.
Statistics for Cayley permutations.
Cf. the following OEIS sequences:
A090665: Cayley permutations by first element.
A131689: Cayley permutations by max element.
A154921: Cayley permutations by number of zeros (size of first block).
The demo uses the functions from
cayley-perm.h (fxt/src/comb/cayley-perm.h)
word-stats.h (fxt/src/comb/word-stats.h)
change-rgs-out.txt is the output of change-rgs-demo.cc.
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.
The demo uses the functions from
change-rgs.h (fxt/src/comb/change-rgs.h)
comb2comp-out.txt is the output of comb2comp-demo.cc.
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.
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)
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.
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.
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).
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.
Eades-McKay (strong revolving door) order for combinations
combination-endo-out.txt is the output of combination-endo-demo.cc.
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.
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.
Combinations in a strong minimal-change order (enup steps).
The set (as opposed to delta set) is generated.
Generation via enup/endo counting.
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.
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.
Generating all combinations in minimal-change order, recursive implementation.
combination-lex-out.txt is the output of combination-lex-demo.cc.
Combinations (n choose k) 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.
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.
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.
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.
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.
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.
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).
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.
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.
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-dist-unimodal-out.txt is the output of composition-dist-unimodal-demo.cc.
Strongly unimodal compositions into distinct parts.
Internal representation as list of parts in increasing order,
with each part except for the last of 2 sorts.
Cf. OEIS sequence A072706.
The demo uses the functions from
composition-dist-unimodal.h (fxt/src/comb/composition-dist-unimodal.h)
composition-ex-colex-out.txt is the output of composition-ex-colex-demo.cc.
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-ex-lex-out.txt is the output of composition-ex-lex-demo.cc.
Compositions of n into exactly k parts in lexicographic order.
The demo uses the functions from
composition-ex-lex.h (fxt/src/comb/composition-ex-lex.h)
composition-gray-rec-out.txt is the output of composition-gray-rec-demo.cc.
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-binary-out.txt is the output of composition-nz-binary-demo.cc.
Compositions of n into powers of 2, lexicographic order.
Cf. OEIS sequence A023359.
The demo uses the functions from
composition-nz-binary.h (fxt/src/comb/composition-nz-binary.h)
composition-nz-carlitz-out.txt is the output of composition-nz-carlitz-demo.cc.
Compositions of n into positive parts such that
adjacent parts are different (Carlitz compositions).
Cf. OEIS sequence A003242.
The demo uses the functions from
composition-nz-carlitz.h (fxt/src/comb/composition-nz-carlitz.h)
composition-nz-out.txt is the output of composition-nz-demo.cc.
Compositions of n into positive parts.
The demo uses the functions from
composition-nz.h (fxt/src/comb/composition-nz.h)
composition-nz-rank.h (fxt/src/comb/composition-nz-rank.h)
composition-nz-first-max-out.txt is the output of composition-nz-first-max-demo.cc.
Compositions of n into positive parts where no part is greater than the first.
Lexicographic order.
See OEIS sequencs A079500 and A007059.
The demo uses the functions from
composition-nz-first-max.h (fxt/src/comb/composition-nz-first-max.h)
composition-nz-gray-out.txt is the output of composition-nz-gray-demo.cc.
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.
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
The demo uses the functions from
composition-nz-gray.h (fxt/src/comb/composition-nz-gray.h)
composition-nz-gray-rec-out.txt is the output of composition-nz-gray-rec-demo.cc.
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.
Recursive algorithm.
composition-nz-gray2-out.txt is the output of composition-nz-gray2-demo.cc.
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.
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
The demo uses the functions from
composition-nz-gray2.h (fxt/src/comb/composition-nz-gray2.h)
composition-nz-i-smooth-out.txt is the output of composition-nz-i-smooth-demo.cc.
Internally smooth compositions:
consecutive parts differ by at most 1.
Lexicographic order.
See OEIS sequence A034297.
The demo uses the functions from
composition-nz-i-smooth.h (fxt/src/comb/composition-nz-i-smooth.h)
composition-nz-left-2smooth-out.txt is the output of composition-nz-left-2smooth-demo.cc.
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.
The demo uses the functions from
composition-nz-left-2smooth.h (fxt/src/comb/composition-nz-left-2smooth.h)
composition-nz-left-smooth-out.txt is the output of composition-nz-left-smooth-demo.cc.
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.
The demo uses the functions from
composition-nz-left-smooth.h (fxt/src/comb/composition-nz-left-smooth.h)
composition-nz-max-out.txt is the output of composition-nz-max-demo.cc.
Compositions of n into positive parts <= mx.
Lexicographic order.
The demo uses the functions from
composition-nz-max.h (fxt/src/comb/composition-nz-max.h)
composition-nz-rank.h (fxt/src/comb/composition-nz-rank.h)
composition-nz-min-out.txt is the output of composition-nz-min-demo.cc.
Compositions of n into positive parts >= mi.
Lexicographic order.
The demo uses the functions from
composition-nz-min.h (fxt/src/comb/composition-nz-min.h)
composition-nz-rank.h (fxt/src/comb/composition-nz-rank.h)
composition-nz-minc-out.txt is the output of composition-nz-minc-demo.cc.
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.
The demo uses the functions from
composition-nz-minc.h (fxt/src/comb/composition-nz-minc.h)
composition-nz-numparts-out.txt is the output of composition-nz-numparts-demo.cc.
Compositions of n into non-zero parts.
Ordering is firstly by number of parts (1, 2, ..., n)
and secondly co-lexicographic (colex).
The demo uses the functions from
composition-nz-numparts.h (fxt/src/comb/composition-nz-numparts.h)
composition-nz-odd-out.txt is the output of composition-nz-odd-demo.cc.
Compositions of n into positive odd parts, lexicographic order.
Loopless algorithm.
Cf. OEIS sequence A000045.
The demo uses the functions from
composition-nz-odd.h (fxt/src/comb/composition-nz-odd.h)
composition-nz-odd-subset-lex-out.txt is the output of composition-nz-odd-subset-lex-demo.cc.
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
The demo uses the functions from
composition-nz-odd-subset-lex.h (fxt/src/comb/composition-nz-odd-subset-lex.h)
composition-nz-prefix-cond-out.txt is the output of composition-nz-prefix-cond-demo.cc.
Compositions of n into positive parts with restricted prefixes.
Lexicographic order.
The demo uses the functions from
composition-nz-prefix-cond.h (fxt/src/comb/composition-nz-prefix-cond.h)
composition-nz-rl-out.txt is the output of composition-nz-rl-demo.cc.
Compositions of n into positive parts, run-length order.
Loopless algorithm.
The demo uses the functions from
composition-nz-rl.h (fxt/src/comb/composition-nz-rl.h)
composition-nz-rank.h (fxt/src/comb/composition-nz-rank.h)
composition-nz-smooth-out.txt is the output of composition-nz-smooth-demo.cc.
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.
The demo uses the functions from
composition-nz-smooth.h (fxt/src/comb/composition-nz-smooth.h)
composition-nz-sorts-out.txt is the output of composition-nz-sorts-demo.cc.
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).
The demo uses the functions from
composition-nz-sorts.h (fxt/src/comb/composition-nz-sorts.h)
composition-nz-sorts2-out.txt is the output of composition-nz-sorts2-demo.cc.
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).
The demo uses the functions from
composition-nz-sorts2.h (fxt/src/comb/composition-nz-sorts2.h)
composition-nz-sorts2-pp-out.txt is the output of composition-nz-sorts2-pp-demo.cc.
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).
The demo uses the functions from
composition-nz-sorts2-pp.h (fxt/src/comb/composition-nz-sorts2-pp.h)
composition-nz-stats-out.txt is the output of composition-nz-stats-demo.cc.
Statistics for compositions into non-zero parts.
Cf. the following OEIS sequences:
A048004: Compositions by value of largest part.
A105147: compositions by value of smallest part.
A119473: compositions by number of even values.
A100749: compositions by number of odd values.
A105422: compositions by number of ones
A106356: compositions by number of flat steps
A238130: compositions by number of non-flat steps
A225084: compositions by max ascent
The demo uses the functions from
composition-nz.h (fxt/src/comb/composition-nz.h)
word-stats.h (fxt/src/comb/word-stats.h)
composition-nz-subdiagonal-out.txt is the output of composition-nz-subdiagonal-demo.cc.
Subdiagonal compositions: compositions a[1] + a[2] + ... + a[m] = n
such that a[k] <= k.
Lexicographic order.
Cf. OEIS sequence A008930.
The demo uses the functions from
composition-nz-subdiagonal.h (fxt/src/comb/composition-nz-subdiagonal.h)
composition-nz-subset-lex-out.txt is the output of composition-nz-subset-lex-demo.cc.
Compositions of n into positive parts, subset-lex order.
Loopless generation.
See Joerg Arndt, Subset-lex: did we miss an order?, (2014)
http://arxiv.org/abs/1405.6503
The demo uses the functions from
composition-nz-subset-lex.h (fxt/src/comb/composition-nz-subset-lex.h)
composition-nz-subset-lex-rec-out.txt is the output of composition-nz-subset-lex-rec-demo.cc.
Compositions of n into positive parts, subset-lex order.
Recursive algorithm.
composition-nz-superdiagonal-out.txt is the output of composition-nz-superdiagonal-demo.cc.
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.
The demo uses the functions from
composition-nz-superdiagonal.h (fxt/src/comb/composition-nz-superdiagonal.h)
composition-nz-upstep-out.txt is the output of composition-nz-upstep-demo.cc.
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.
The demo uses the functions from
composition-nz-upstep.h (fxt/src/comb/composition-nz-upstep.h)
composition-nz-weakly-unimodal-out.txt is the output of composition-nz-weakly-unimodal-demo.cc.
Weakly unimodal compositions, lexicographic order.
Cf. OEIS sequence A001523.
The demo uses the functions from
composition-nz-weakly-unimodal.h (fxt/src/comb/composition-nz-weakly-unimodal.h)
composition-rank-out.txt is the output of composition-rank-demo.cc.
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)
composition-unimodal-out.txt is the output of composition-unimodal-demo.cc.
Strongly unimodal compositions.
Internal 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.
The demo uses the functions from
composition-unimodal.h (fxt/src/comb/composition-unimodal.h)
conference-quadres-out.txt is the output of conference-quadres-demo.cc.
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-gray-out.txt is the output of cyclic-perm-gray-demo.cc.
Generate all cyclic permutations in minimal-change order, CAT algorithm.
The demo uses the functions from
cyclic-perm-gray.h (fxt/src/comb/cyclic-perm-gray.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.
Generating De Bruijn sequences.
The demo uses the functions from
debruijn.h (fxt/src/comb/debruijn.h)
necklace.h (fxt/src/comb/necklace.h)
descent-rgs-out.txt is the output of descent-rgs-demo.cc.
Descent sequences (restricted growth strings, RGS).
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.
Lexicographic order.
See OEIS sequence A225588.
The demo uses the functions from
descent-rgs.h (fxt/src/comb/descent-rgs.h)
descent-rgs-stats-out.txt is the output of descent-rgs-stats-demo.cc.
Statistics for descent sequences.
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.
Cf. the following OEIS sequences:
A225624: triangle, length-n descent sequences with k-1 descents.
The demo uses the functions from
descent-rgs.h (fxt/src/comb/descent-rgs.h)
word-stats.h (fxt/src/comb/word-stats.h)
dyck-gray-out.txt is the output of dyck-gray-demo.cc.
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).
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.
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.
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 demo uses the functions from
dyck-pref.h (fxt/src/comb/dyck-pref.h)
dyck-rgs-out.txt is the output of dyck-rgs-demo.cc.
Restricted growth strings (RGS) for k-ary Dyck words:
strings s[0,...,n-1] such that s[j] <= s[j-1] + i (where i=k-1).
Lexicographic order.
Number of RGS is binomial(i*n,n)/((i-1)*n+1), (Catalan numbers for i=1).
The demo uses the functions from
dyck-rgs.h (fxt/src/comb/dyck-rgs.h)
dyck-rgs-subset-lex-out.txt is the output of dyck-rgs-subset-lex-demo.cc.
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.
See Joerg Arndt, Subset-lex: did we miss an order?, (2014)
http://arxiv.org/abs/1405.6503
The demo uses the functions from
dyck-rgs-subset-lex.h (fxt/src/comb/dyck-rgs-subset-lex.h)
is-dyck-rgs.h (fxt/src/comb/is-dyck-rgs.h)
fact2cyclic-out.txt is the output of fact2cyclic-demo.cc.
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.
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.h (fxt/src/comb/mixedradix.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.
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.h (fxt/src/comb/mixedradix.h)
fact2perm-rot-out.txt is the output of fact2perm-rot-demo.cc.
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.h (fxt/src/comb/mixedradix.h)
fact2perm-swp-out.txt is the output of fact2perm-swp-demo.cc.
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.h (fxt/src/comb/mixedradix.h)
ffact2kperm-out.txt is the output of ffact2kperm-demo.cc.
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.h (fxt/src/comb/mixedradix.h)
fib-alt-gray-out.txt is the output of fib-alt-gray-demo.cc.
Gray codes for certain ternary words counted by Fibonacci numbers
fibgray-rec-out.txt is the output of fibgray-rec-demo.cc.
Gray code for Fibonacci words, recursive CAT algorithm
fractional-base-number-out.txt is the output of fractional-base-number-demo.cc.
Numbers with fractional base b_num / b_den.
Special case b_den == 1 gives the usual base - b_num numbers.
Must have b_num >= 2 and 1 <= b_den < b_num.
The demo uses the functions from
fractional-base-number.h (fxt/src/comb/fractional-base-number.h)
gexz-gray-out.txt is the output of gexz-gray-demo.cc.
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.
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.
Towers of Hanoi, recursive algorithm.
hilbert-ndim-out.txt is the output of hilbert-ndim-demo.cc.
Fred Lunnon's iterative 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.
Fred Lunnon's recursive algorithm for the n-dimensional Hilbert curve
The demo uses the functions from
hilbert-ndim-rec.h (fxt/src/comb/hilbert-ndim-rec.h)
id-tree-lev-seq-out.txt is the output of id-tree-lev-seq-demo.cc.
Level sequences for unordered rooted identity trees.
Cf. OEIS sequence A004111.
The demo uses the functions from
id-tree-lev-seq.h (fxt/src/comb/id-tree-lev-seq.h)
tree-lev-seq-aux.h (fxt/src/comb/tree-lev-seq-aux.h)
id-tree-lev-seq-stats-out.txt is the output of id-tree-lev-seq-stats-demo.cc.
Statistics for (level sequences of) unordered rooted identity trees.
Cf. the following OEIS sequences:
A004111: all identity trees.
A227819: identity trees by height.
A055327: identity trees by number of descents.
A227774: identity trees by number of ones.
A244523: identity trees by maximal branching number (out-degree).
The demo uses the functions from
id-tree-lev-seq.h (fxt/src/comb/id-tree-lev-seq.h)
word-stats.h (fxt/src/comb/word-stats.h)
involution-stats-out.txt is the output of involution-stats-demo.cc.
Statistics for involutions (self-inverse permutations):
Cf. the following OEIS sequences:
A099174, A161126, A238889, and A239145.
The demo uses the functions from
perm-involution.h (fxt/src/comb/perm-involution.h)
word-stats.h (fxt/src/comb/word-stats.h)
involution-zero-map-rgs-out.txt is the output of involution-zero-map-rgs-demo.cc.
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.
The demo uses the functions from
involution-zero-map-rgs.h (fxt/src/comb/involution-zero-map-rgs.h)
is-zero-map-rgs.h (fxt/src/comb/is-zero-map-rgs.h)
isoscent-rgs-out.txt is the output of isoscent-rgs-demo.cc.
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.
The demo uses the functions from
isoscent-rgs.h (fxt/src/comb/isoscent-rgs.h)
isoscent-rgs-stats-out.txt is the output of isoscent-rgs-stats-demo.cc.
Statistics for isoscent sequences.
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.
The demo uses the functions from
isoscent-rgs.h (fxt/src/comb/isoscent-rgs.h)
word-stats.h (fxt/src/comb/word-stats.h)
kperm-gray-out.txt is the output of kperm-gray-demo.cc.
Generate all k-permutations of n elements in minimal-change order
via Gray code for falling factorial numbers, CAT algorithm.
Same as: k-prefixes of permutations of n elements.
Same as: arrangements of k out of n elements.
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.
Generate all 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.
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.
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.
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-lex-out.txt is the output of ksubset-lex-demo.cc.
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
The demo uses the functions from
ksubset-lex.h (fxt/src/comb/ksubset-lex.h)
ksubset-rec-out.txt is the output of ksubset-rec-demo.cc.
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.
k-subsets (kmin<=k<=kmax) in two-close order with homogeneous moves.
The demo uses the functions from
ksubset-twoclose.h (fxt/src/comb/ksubset-twoclose.h)
ksubset-twoclose-list-out.txt is the output of ksubset-twoclose-list-demo.cc.
k-subsets (kmin<=k<=kmax) in two-close order with homogeneous moves.
Representation as list of elements.
The demo uses the functions from
ksubset-twoclose-list.h (fxt/src/comb/ksubset-twoclose-list.h)
ksubset-twoclose-list-rec-out.txt is the output of ksubset-twoclose-list-rec-demo.cc.
k-subsets (kmin<=k<=kmax) in two-close order with homogeneous moves.
Representation as list of elements.
Recursive algorithm.
The demo uses the functions from
ksubset-twoclose-list-rec.h (fxt/src/comb/ksubset-twoclose-list-rec.h)
ksubset-twoclose-rec-out.txt is the output of ksubset-twoclose-rec-demo.cc.
k-subsets (kmin<=k<=kmax) in two-close order with homogeneous moves.
Recursive algorithm.
The demo uses the functions from
ksubset-twoclose-rec.h (fxt/src/comb/ksubset-twoclose-rec.h)
lyndon-factorization-out.txt is the output of lyndon-factorization-demo.cc.
Standard (Chen, Fox, Lyndon)-factorization of the word W.
The demo uses the functions from
lyndon-factorization.h (fxt/src/comb/lyndon-factorization.h)
mixedradix-rev.h (fxt/src/comb/mixedradix-rev.h)
lyndon-words-out.txt is the output of lyndon-words-demo.cc.
All Lyndon words up to length n. Duval's algorithm.
The demo uses the functions from
lyndon-words.h (fxt/src/comb/lyndon-words.h)
lyndon-words-prefix-cond-out.txt is the output of lyndon-words-prefix-cond-demo.cc.
Lyndon words up to length n with restricted prefixes.
The demo uses the functions from
lyndon-words-prefix-cond.h (fxt/src/comb/lyndon-words-prefix-cond.h)
lyndon-words.h (fxt/src/comb/lyndon-words.h)
map23-rgs-out.txt is the output of map23-rgs-demo.cc.
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.
The demo uses the functions from
map23-rgs.h (fxt/src/comb/map23-rgs.h)
maxrep-gray-out.txt is the output of maxrep-gray-demo.cc.
Gray code for generalized Fibonacci words, recursive CAT algorithm
mixedradix-out.txt is the output of mixedradix-demo.cc.
Mixed radix counting.
The demo uses the functions from
mixedradix.h (fxt/src/comb/mixedradix.h)
mixedradix-endo-out.txt is the output of mixedradix-endo-demo.cc.
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.
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-fixed-content-out.txt is the output of mixedradix-fixed-content-demo.cc.
Mixed radix numbers with fixed sum of digits.
Also: k-subsets (combinations) of a multiset.
The demo uses the functions from
mixedradix-fixed-content.h (fxt/src/comb/mixedradix-fixed-content.h)
mixedradix-fixed-content-lex-out.txt is the output of mixedradix-fixed-content-lex-demo.cc.
Mixed radix counting, fixed content.
Equivalently, subsets of a multiset with a fixed number of elements.
Lexicographic order.
The demo uses the functions from
mixedradix-fixed-content-lex.h (fxt/src/comb/mixedradix-fixed-content-lex.h)
mixedradix-gray-out.txt is the output of mixedradix-gray-demo.cc.
Mixed radix Gray code, CAT algorithm.
The demo uses the functions from
mixedradix-gray.h (fxt/src/comb/mixedradix-gray.h)
mixedradix-gslex-alt-out.txt is the output of mixedradix-gslex-alt-demo.cc.
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-out.txt is the output of mixedradix-gslex-demo.cc.
Mixed radix numbers in gslex (generalized subset lex) order.
Loopless algorithm.
The demo uses the functions from
mixedradix-gslex.h (fxt/src/comb/mixedradix-gslex.h)
mixedradix-modular-gray-out.txt is the output of mixedradix-modular-gray-demo.cc.
Modular mixed radix Gray code, CAT algorithm.
The demo uses the functions from
mixedradix-modular-gray.h (fxt/src/comb/mixedradix-modular-gray.h)
mixedradix-naf-out.txt is the output of mixedradix-naf-demo.cc.
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.
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-subset-lex-out.txt is the output of mixedradix-naf-subset-lex-demo.cc.
Mixed radix non-adjacent forms (NAF) in subset-lex order.
Loopless generation.
The demo uses the functions from
mixedradix-naf-subset-lex.h (fxt/src/comb/mixedradix-naf-subset-lex.h)
mixedradix-prefix-cond-out.txt is the output of mixedradix-prefix-cond-demo.cc.
Mixed radix counting with restricted prefixes.
The demo uses the functions from
mixedradix-prefix-cond.h (fxt/src/comb/mixedradix-prefix-cond.h)
mixedradix-rev-out.txt is the output of mixedradix-rev-demo.cc.
Mixed radix counting.
Digits in reversed order as in class mixedradix.
The demo uses the functions from
mixedradix-rev.h (fxt/src/comb/mixedradix-rev.h)
mixedradix-sl-gray-out.txt is the output of mixedradix-sl-gray-demo.cc.
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
The demo uses the functions from
mixedradix-sl-gray.h (fxt/src/comb/mixedradix-sl-gray.h)
mixedradix-sl-gray-rank.h (fxt/src/comb/mixedradix-sl-gray-rank.h)
mixedradix-sl-gray-rec-out.txt is the output of mixedradix-sl-gray-rec-demo.cc.
Recursive generation of mixed radix numbers in a minimal-change order
related so subset-lex order ("SL-Gray" order).
mixedradix-subset-lex-out.txt is the output of mixedradix-subset-lex-demo.cc.
Mixed radix numbers in subset-lex order.
See Joerg Arndt, Subset-lex: did we miss an order?, (2014)
http://arxiv.org/abs/1405.6503
The demo uses the functions from
mixedradix-subset-lex.h (fxt/src/comb/mixedradix-subset-lex.h)
mixedradix-subset-lex-rank.h (fxt/src/comb/mixedradix-subset-lex-rank.h)
mixedradix-subset-lexrev-out.txt is the output of mixedradix-subset-lexrev-demo.cc.
Mixed radix numbers in subset-lexrev order.
See Joerg Arndt, Subset-lex: did we miss an order?, (2014)
http://arxiv.org/abs/1405.6503
The demo uses the functions from
mixedradix-subset-lexrev.h (fxt/src/comb/mixedradix-subset-lexrev.h)
monotonicgray-out.txt is the output of monotonicgray-demo.cc.
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)
motzkin-nonflat-rgs-lex-out.txt is the output of motzkin-nonflat-rgs-lex-demo.cc.
Motzkin (nonflat) restricted growth strings (RGS).
Same as: Catalan RGS with no flat steps.
Cf. OEIS sequences A086246 and A001006.
The demo uses the functions from
motzkin-nonflat-rgs-lex.h (fxt/src/comb/motzkin-nonflat-rgs-lex.h)
motzkin-path-lex-out.txt is the output of motzkin-path-lex-demo.cc.
Motzkin paths in lexicographic order, CAT algorithm.
Cf. OEIS sequence A001006.
The demo uses the functions from
motzkin-path-lex.h (fxt/src/comb/motzkin-path-lex.h)
is-motzkin-path.h (fxt/src/comb/is-motzkin-path.h)
motzkin-rgs-lex-out.txt is the output of motzkin-rgs-lex-demo.cc.
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.
The demo uses the functions from
motzkin-rgs-lex.h (fxt/src/comb/motzkin-rgs-lex.h)
paren-string-to-rgs.h (fxt/src/comb/paren-string-to-rgs.h)
motzkin-step-rgs-lex-out.txt is the output of motzkin-step-rgs-lex-demo.cc.
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.
The demo uses the functions from
motzkin-step-rgs-lex.h (fxt/src/comb/motzkin-step-rgs-lex.h)
is-motzkin-step-rgs.h (fxt/src/comb/is-motzkin-step-rgs.h)
mpartition-out.txt is the output of mpartition-demo.cc.
Integer partitions of n into m parts.
Representation as list of parts in weakly ascending order.
Cf. OEIS sequence A008284.
The demo uses the functions from
mpartition.h (fxt/src/comb/mpartition.h)
mpartition2-out.txt is the output of mpartition2-demo.cc.
Integer partitions of n into m parts.
Representation as list of parts in weakly ascending order.
Same functionality as class mpartition, this
implementation avoids the auxiliary array s[].
Cf. OEIS sequence A008284.
The demo uses the functions from
mpartition2.h (fxt/src/comb/mpartition2.h)
mset-kperm-lex-out.txt is the output of mset-kperm-lex-demo.cc.
All k-permutations of a multiset in lexicographic order.
The demo uses the functions from
mset-kperm-lex.h (fxt/src/comb/mset-kperm-lex.h)
mset-perm-lex.h (fxt/src/comb/mset-perm-lex.h)
mset-ksubset-out.txt is the output of mset-ksubset-demo.cc.
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-fixed-content.h (fxt/src/comb/mixedradix-fixed-content.h)
mset-perm-gray-out.txt is the output of mset-perm-gray-demo.cc.
All multiset permutations in minimal-change order (Fred 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-lex-out.txt is the output of mset-perm-lex-demo.cc.
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-lex-rec-out.txt is the output of mset-perm-lex-rec-demo.cc.
All multiset permutations in lexicographic order, recursive generation.
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-rec2-out.txt is the output of mset-perm-lex-rec2-demo.cc.
All multiset permutations in lexicographic order, recursive generation.
Same as: all strings with fixed content.
mset-perm-pref-out.txt is the output of mset-perm-pref-demo.cc.
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).
The demo uses the functions from
mset-perm-pref.h (fxt/src/comb/mset-perm-pref.h)
mset-subset-lex-out.txt is the output of mset-subset-lex-demo.cc.
Subsets of a multiset in lexicographic order with respect to subsets,
generated as (multi-)delta sets (that is, mixed radix numbers).
See Joerg Arndt, Subset-lex: did we miss an order?, (2014)
http://arxiv.org/abs/1405.6503
The demo uses the functions from
mixedradix-subset-lex.h (fxt/src/comb/mixedradix-subset-lex.h)
msetpart-out.txt is the output of msetpart-demo.cc.
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
The demo uses the functions from
msetpart.h (fxt/src/comb/msetpart.h)
naf-gray-rec-out.txt is the output of naf-gray-rec-demo.cc.
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.
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.
Generate pre-necklaces as described by Cattell, Ruskey, Sawada, Miers, Serra.
Recursive CAT algorithm.
necklace-out.txt is the output of necklace-demo.cc.
Generate all pre-necklaces, necklaces, and Lyndon words with a given number of colors.
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.
Fredericksen, Kessler, Maiorana (FKM) algorithm for generating necklaces.
necklace-gray-out.txt is the output of necklace-gray-demo.cc.
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.
Generate Gray code (max 3 changes per update) for necklaces
necklace-sigma-tau-out.txt is the output of necklace-sigma-tau-demo.cc.
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.
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.
Gray code for binary words with no substring 111, recursive CAT algorithm
no1111-gray-out.txt is the output of no1111-gray-demo.cc.
Gray code for binary words with no substring 1111, recursive CAT algorithm
no1x1-gray-out.txt is the output of no1x1-gray-demo.cc.
Gray code for binary words with no substring 1x1, recursive CAT algorithm
no1xy1-gray-out.txt is the output of no1xy1-gray-demo.cc.
Gray code for binary words with no substring 1xy1, recursive CAT algorithm
ntnz-gray-out.txt is the output of ntnz-gray-demo.cc.
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.
Gray code for words without two consecutive zeros, recursive CAT algorithm
num-partitions-out.txt is the output of num-partitions-demo.cc.
Number of integer partitions.
ordered-tree-branches-out.txt is the output of ordered-tree-branches-demo.cc.
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).
The demo uses the functions from
ordered-tree-branches.h (fxt/src/comb/ordered-tree-branches.h)
ordered-tree-branching-seq-out.txt is the output of ordered-tree-branching-seq-demo.cc.
Branching sequences for ordered rooted trees:
words [s(0), s(1), ..., s(n)] with s(n)=0, sum(j=0..n, s(j)) = n,
sum(j=0..k, s(j)-1 ) >= 0 for k
The demo uses the functions from
ordered-tree-branching-seq.h (fxt/src/comb/ordered-tree-branching-seq.h)
ordered-tree-lev-seq-out.txt is the output of ordered-tree-lev-seq-demo.cc.
Level sequences for ordered rooted trees.
Cf. OEIS sequence A000108.
The demo uses the functions from
ordered-tree-lev-seq.h (fxt/src/comb/ordered-tree-lev-seq.h)
tree-lev-seq-aux.h (fxt/src/comb/tree-lev-seq-aux.h)
ordered-tree-lev-seq-stats-out.txt is the output of ordered-tree-lev-seq-stats-demo.cc.
Statistics for (level sequences of) ordered rooted trees.
Cf. the following OEIS sequences:
A000108: all trees.
A080936: trees by height.
A001263: trees by number of ascents.
A091894: trees by number of descents.
A033184: trees by number of ones.
A152879: trees by number of max levels.
A078391: trees by position of last 1.
A091869: trees by number of flat steps.
A116424: trees by number of peaks.
A203717: trees by max branching number (out-degree).
The demo uses the functions from
ordered-tree-lev-seq.h (fxt/src/comb/ordered-tree-lev-seq.h)
word-stats.h (fxt/src/comb/word-stats.h)
paren-out.txt is the output of paren-demo.cc.
Parentheses strings, co-lexicographic order.
Representation as list of positions of opening parenthesis.
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.
Parentheses strings in a homogeneous minimal-change order.
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.
Gray code for paren strings via restricted growth strings (RGS), recursive algorithm.
paren-lex-out.txt is the output of paren-lex-demo.cc.
Parentheses strings, lexicographic order.
Representation as list of positions of opening parenthesis.
The demo uses the functions from
paren-lex.h (fxt/src/comb/paren-lex.h)
is-paren-string.h (fxt/src/comb/is-paren-string.h)
paren-pref-out.txt is the output of paren-pref-demo.cc.
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-2fall-asc-out.txt is the output of partition-2fall-asc-demo.cc.
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.
The demo uses the functions from
partition-2fall-asc.h (fxt/src/comb/partition-2fall-asc.h)
partition-2fall-asc-subset-lex-out.txt is the output of partition-2fall-asc-subset-lex-demo.cc.
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.
The demo uses the functions from
partition-2fall-asc-subset-lex.h (fxt/src/comb/partition-2fall-asc-subset-lex.h)
partition-2fall-desc-out.txt is the output of partition-2fall-desc-demo.cc.
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.
The demo uses the functions from
partition-2fall-desc.h (fxt/src/comb/partition-2fall-desc.h)
partition-asc-2rep-out.txt is the output of partition-asc-2rep-demo.cc.
Integer partitions where parts have multiplicity at most 2.
Representation as weakly ascending list of parts.
Lexicographic order.
Cf. OEIS sequence A000726.
The demo uses the functions from
partition-asc-2rep.h (fxt/src/comb/partition-asc-2rep.h)
partition-asc-2rep-subset-lex-out.txt is the output of partition-asc-2rep-subset-lex-demo.cc.
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.
The demo uses the functions from
partition-asc-2rep-subset-lex.h (fxt/src/comb/partition-asc-2rep-subset-lex.h)
partition-asc-out.txt is the output of partition-asc-demo.cc.
Integer partitions as weakly ascending list of parts.
Lexicographic order.
Cf. OEIS sequence A000041.
The demo uses the functions from
partition-asc.h (fxt/src/comb/partition-asc.h)
partition-asc-perim-out.txt is the output of partition-asc-perim-demo.cc.
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.
The demo uses the functions from
partition-asc-perim.h (fxt/src/comb/partition-asc-perim.h)
partition-asc-sorts-out.txt is the output of partition-asc-sorts-demo.cc.
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).
The demo uses the functions from
partition-asc-sorts.h (fxt/src/comb/partition-asc-sorts.h)
partition-asc-sorts2-out.txt is the output of partition-asc-sorts2-demo.cc.
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).
The demo uses the functions from
partition-asc-sorts2.h (fxt/src/comb/partition-asc-sorts2.h)
partition-asc-sorts2-pp-out.txt is the output of partition-asc-sorts2-pp-demo.cc.
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).
The demo uses the functions from
partition-asc-sorts2-pp.h (fxt/src/comb/partition-asc-sorts2-pp.h)
partition-asc-stats-out.txt is the output of partition-asc-stats-demo.cc.
Statistics for partitions (as weakly ascending lists of parts).
Cf. the following OEIS sequences:
A008284: partitions by value of largest part.
A026794: partitions by value of smallest part.
A116482: partitions by number of even values.
A103919: partitions by number of odd values.
A116598: partitions by number of ones
A133121: partitions by number of flat steps
A116608: partitions by number of non-flat steps (ascents)
The demo uses the functions from
partition-asc.h (fxt/src/comb/partition-asc.h)
word-stats.h (fxt/src/comb/word-stats.h)
partition-asc-subset-lex-csh-out.txt is the output of partition-asc-subset-lex-csh-demo.cc.
Partitions of n into positive parts, cyclically shifted subset-lex order.
Loopless algorithm.
The demo uses the functions from
partition-asc-subset-lex-csh.h (fxt/src/comb/partition-asc-subset-lex-csh.h)
partition-asc-subset-lex-out.txt is the output of partition-asc-subset-lex-demo.cc.
Partitions of n into positive parts as ascending list of parts.
Subset-lex order.
Loopless algorithm.
See Joerg Arndt, Subset-lex: did we miss an order?, (2014)
http://arxiv.org/abs/1405.6503
The demo uses the functions from
partition-asc-subset-lex.h (fxt/src/comb/partition-asc-subset-lex.h)
partition-binary-asc-out.txt is the output of partition-binary-asc-demo.cc.
Binary partitions as weakly ascending list of parts.
Lexicographic order.
Cf. OEIS sequences A018819 and A000123.
The demo uses the functions from
partition-binary-asc.h (fxt/src/comb/partition-binary-asc.h)
partition-binary-desc-out.txt is the output of partition-binary-desc-demo.cc.
Binary partitions as weakly descending list of parts.
Lexicographic order.
Cf. OEIS sequences A018819 and A000123.
The demo uses the functions from
partition-binary-desc.h (fxt/src/comb/partition-binary-desc.h)
partition-out.txt is the output of partition-demo.cc.
Generate all integer partitions, iterative algorithm.
The demo uses the functions from
partition.h (fxt/src/comb/partition.h)
partition-desc-bb-out.txt is the output of partition-desc-bb-demo.cc.
Integer partitions as weakly descending list of parts,
with bounds for size of parts and number of parts.
Lexicographic order.
The demo uses the functions from
partition-desc-bb.h (fxt/src/comb/partition-desc-bb.h)
partition-desc-out.txt is the output of partition-desc-demo.cc.
Integer partitions as weakly descending list of parts.
Cf. OEIS sequence A000041.
The demo uses the functions from
partition-desc.h (fxt/src/comb/partition-desc.h)
partition-dist-asc-out.txt is the output of partition-dist-asc-demo.cc.
Integer partitions into distinct parts as ascending list of parts,
lexicographic order.
Cf. OEIS sequence A000009.
The demo uses the functions from
partition-dist-asc.h (fxt/src/comb/partition-dist-asc.h)
partition-dist-asc-len-out.txt is the output of partition-dist-asc-len-demo.cc.
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.
The demo uses the functions from
partition-dist-asc-len.h (fxt/src/comb/partition-dist-asc-len.h)
partition-dist-asc-stats-out.txt is the output of partition-dist-asc-stats-demo.cc.
Statistics for partitions into distinct parts (as ascending lists of parts).
Cf. the following OEIS sequences:
A026836, A026821, A060016, A116679, and A116675
The demo uses the functions from
partition-dist-asc.h (fxt/src/comb/partition-dist-asc.h)
word-stats.h (fxt/src/comb/word-stats.h)
partition-dist-asc-subset-lex-out.txt is the output of partition-dist-asc-subset-lex-demo.cc.
Integer partitions into distinct parts.
Representation as list of parts in increasing order.
Subset-lex order.
Only the last two positions in a partition at the end change.
Loopless algorithm.
Cf. OEIS sequence A000009.
See Joerg Arndt, Subset-lex: did we miss an order?, (2014)
http://arxiv.org/abs/1405.6503
The demo uses the functions from
partition-dist-asc-subset-lex.h (fxt/src/comb/partition-dist-asc-subset-lex.h)
partition-dist-d-asc-out.txt is the output of partition-dist-d-asc-demo.cc.
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).
The demo uses the functions from
partition-dist-d-asc.h (fxt/src/comb/partition-dist-d-asc.h)
partition-dist-desc-out.txt is the output of partition-dist-desc-demo.cc.
Partitions into distinct parts as decreasing list of parts.
Lexicographic order.
Cf. OEIS sequence A000009.
The demo uses the functions from
partition-dist-desc.h (fxt/src/comb/partition-dist-desc.h)
partition-gen-out.txt is the output of partition-gen-demo.cc.
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-nonsquashing-desc-out.txt is the output of partition-nonsquashing-desc-demo.cc.
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] ).
Lexicographic order.
With parameter sd = true generate strongly decreasing partitions:
partitions such that a[k] > sum(j=k+1..m, a[j] ).
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).
The demo uses the functions from
partition-nonsquashing-desc.h (fxt/src/comb/partition-nonsquashing-desc.h)
partition-odd-asc-out.txt is the output of partition-odd-asc-demo.cc.
Integer partitions into odd parts as weakly ascending list of parts.
Cf. OEIS sequence A000009.
The demo uses the functions from
partition-odd-asc.h (fxt/src/comb/partition-odd-asc.h)
partition-odd-asc-stats-out.txt is the output of partition-odd-asc-stats-demo.cc.
Statistics for partitions into odd parts (as weakly ascending lists of parts).
Cf. the following OEIS sequences:
A152140, A097304, A116799, A116856, A117408, A115604,
A116663, and A115604
The demo uses the functions from
partition-odd-asc.h (fxt/src/comb/partition-odd-asc.h)
word-stats.h (fxt/src/comb/word-stats.h)
partition-odd-asc-subset-lex-csh-out.txt is the output of partition-odd-asc-subset-lex-csh-demo.cc.
Partitions of n into odd parts, cyclically shifted subset-lex order.
Loopless algorithm.
The demo uses the functions from
partition-odd-asc-subset-lex-csh.h (fxt/src/comb/partition-odd-asc-subset-lex-csh.h)
partition-odd-asc-subset-lex-out.txt is the output of partition-odd-asc-subset-lex-demo.cc.
Partitions of n into odd parts, subset-lex order.
Loopless algorithm.
Cf. OEIS sequence A000009.
See Joerg Arndt, Subset-lex: did we miss an order?, (2014)
http://arxiv.org/abs/1405.6503
The demo uses the functions from
partition-odd-asc-subset-lex.h (fxt/src/comb/partition-odd-asc-subset-lex.h)
partition-odd-desc-out.txt is the output of partition-odd-desc-demo.cc.
Integer partitions into odd parts as weakly descending list of parts.
Cf. OEIS sequence A000009.
The demo uses the functions from
partition-odd-desc.h (fxt/src/comb/partition-odd-desc.h)
partition-odd-nonsquashing-desc-out.txt is the output of partition-odd-nonsquashing-desc-demo.cc.
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 (non-squashing) and A272187 (strongly decreasing).
The demo uses the functions from
partition-odd-nonsquashing-desc.h (fxt/src/comb/partition-odd-nonsquashing-desc.h)
partition-rgs-lex-out.txt is the output of partition-rgs-lex-demo.cc.
Restricted growth strings (RGS) for partitions as descending lists,
lexicographic order.
Same as: least Young tableaux (as RGS) with fixed shape (partition).
Cf. OEIS sequence A000041.
The demo uses the functions from
partition-rgs-lex.h (fxt/src/comb/partition-rgs-lex.h)
is-partition-rgs.h (fxt/src/comb/is-partition-rgs.h)
partition-s-desc-out.txt is the output of partition-s-desc-demo.cc.
S-partitions: integer partitions into parts 2^n-1.
Representation as weakly descending list of parts.
Cf. OEIS sequence A000929.
The demo uses the functions from
partition-s-desc.h (fxt/src/comb/partition-s-desc.h)
partition-strongly-decr-desc-out.txt is the output of partition-strongly-decr-desc-demo.cc.
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.
The demo uses the functions from
partition-strongly-decr-desc.h (fxt/src/comb/partition-strongly-decr-desc.h)
pascal-out.txt is the output of pascal-demo.cc.
Pascal triangle.
Cf. OEIS sequence A007318.
peano-ndim-out.txt is the output of peano-ndim-demo.cc.
n-dimensional Peano curve
The demo uses the functions from
peano-ndim.h (fxt/src/comb/peano-ndim.h)
mixedradix-gray.h (fxt/src/comb/mixedradix-gray.h)
pellgen-gray-out.txt is the output of pellgen-gray-demo.cc.
Gray code for generalized Pell words, recursive CAT algorithm
pellgray-rec-out.txt is the output of pellgray-rec-demo.cc.
Gray code for Pell words, recursive CAT algorithm
perm-colex-out.txt is the output of perm-colex-demo.cc.
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.
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.
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.
Genus of all permutations of n elements.
Print parenthesis strings for permutations of genus zero.
Cf. OEIS sequence A177267.
The demo uses the functions from
perm-genus.h (fxt/src/perm/perm-genus.h)
perm-lex.h (fxt/src/comb/perm-lex.h)
perm-gray-ffact-out.txt is the output of perm-gray-ffact-demo.cc.
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-lipski-out.txt is the output of perm-gray-lipski-demo.cc.
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.
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.
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.
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.
Gray code for permutations, CAT algorithm.
Algorithm following
B. R. Heap: Permutations by Interchanges,
The Computer Journal, vol. 6, pp. 293-294, (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.
Gray code for permutations, CAT algorithm, optimized version.
Optimized implementation, quite fast.
Algorithm following
B. R. Heap: Permutations by Interchanges,
The Computer Journal, vol. 6, pp. 293-294, (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.
Swaps for Gray code for permutations, CAT algorithm, optimized version.
Optimized implementation, quite fast.
Algorithm following
B. R. Heap: Permutations by Interchanges,
The Computer Journal, vol. 6, pp. 293-294, (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.
Involutions (self-inverse permutations).
Cf. OEIS sequence A000085.
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.
Self-inverse permutations (involutions) from falling factorial numbers
that are non-adjacent forms (NAF).
Cf. OEIS sequence A000085.
The demo uses the functions from
mixedradix-naf-gray.h (fxt/src/comb/mixedradix-naf-gray.h)
perm-ives-out.txt is the output of perm-ives-demo.cc.
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.
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.
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.
Generate all permutations in lexicographic order.
The demo uses the functions from
perm-lex.h (fxt/src/comb/perm-lex.h)
perm-mv0-out.txt is the output of perm-mv0-demo.cc.
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.
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.
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-rev-out.txt is the output of perm-rev-demo.cc.
Permutations by reversing prefixes, CAT algorithm via prefix reversals.
The demo uses the functions from
perm-rev.h (fxt/src/comb/perm-rev.h)
perm-right1-gray-out.txt is the output of perm-right1-gray-demo.cc.
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.
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.
Unranking for permutations by rotations (cyclic shifts).
The demo uses the functions from
mixedradix.h (fxt/src/comb/mixedradix.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.
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.
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.
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.
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.
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.
Inverse star transposition permutations
via permutations by prefix reversals.
The demo uses the functions from
perm-star-inv.h (fxt/src/comb/perm-star-inv.h)
perm-rev.h (fxt/src/comb/perm-rev.h)
perm-star-swaps-out.txt is the output of perm-star-swaps-demo.cc.
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.
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.
Generate all permutations in strong minimal-change order using Trotter's algorithm.
Smallest element moves most often.
The demo uses the functions from
jjassert.h (fxt/src/jjassert.h)
perm-trotter-lg-out.txt is the output of perm-trotter-lg-demo.cc.
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)
perm1-prefix-cond-out.txt is the output of perm1-prefix-cond-demo.cc.
Permutations with restricted prefixes.
Knuth's "Algorithm X", section 7.2.1.2, p.334 in vol.4A1 of TAOCP.
The demo uses the functions from
perm1-prefix-cond.h (fxt/src/comb/perm1-prefix-cond.h)
perm1-topsort-out.txt is the output of perm1-topsort-demo.cc.
Young tableaux of given shape.
The underlying driver is class perm1_topsort which is
Knuth's "Algorithm V", section 7.2.1.2, p.343 in vol.4A/1 of TAOCP.
The demo uses the functions from
perm1-topsort.h (fxt/src/comb/perm1-topsort.h)
young-tab-fixed-shape.h (fxt/src/comb/young-tab-fixed-shape.h)
perm2fact-out.txt is the output of perm2fact-demo.cc.
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.
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.
Cf. OEIS sequences
A000110 (i=1), A004211 (i=2), A004212 (i=3),
A004213 (i=4), A005011 (i=5), A005012 (i=6).
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.
All Restricted growth strings (RGS) s[0,...,n-1] so that s[k] <= s[k-1] + k
Lexicographic order.
Cf. OEIS sequence A107877.
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.
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
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.
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.
Zero-sums of roots of unity.
Cf. OEIS sequence A164896.
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.
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.
The demo uses the functions from
ruler-func.h (fxt/src/comb/ruler-func.h)
ruler-func-s-out.txt is the output of ruler-func-s-demo.cc.
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.
The demo uses the functions from
ruler-func-s.h (fxt/src/comb/ruler-func-s.h)
composition-nz-sorts.h (fxt/src/comb/composition-nz-sorts.h)
ruler-func1-out.txt is the output of ruler-func1-demo.cc.
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.
The demo uses the functions from
ruler-func1.h (fxt/src/comb/ruler-func1.h)
composition-nz.h (fxt/src/comb/composition-nz.h)
schroeder-path-lex-out.txt is the output of schroeder-path-lex-demo.cc.
Schroeder paths in lexicographic order, CAT algorithm.
Cf. OEIS sequence A006318: large Schroeder numbers.
The demo uses the functions from
schroeder-path-lex.h (fxt/src/comb/schroeder-path-lex.h)
schroeder-rgs-lex-out.txt is the output of schroeder-rgs-lex-demo.cc.
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.
The demo uses the functions from
schroeder-rgs-lex.h (fxt/src/comb/schroeder-rgs-lex.h)
is-schroeder-rgs.h (fxt/src/comb/is-schroeder-rgs.h)
schroeder-tree-out.txt is the output of schroeder-tree-demo.cc.
Generate all Schroeder trees with m-leaf nodes, loopless algorithm.
score-sequence-out.txt is the output of score-sequence-demo.cc.
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.
The demo uses the functions from
score-sequence.h (fxt/src/comb/score-sequence.h)
setpart-ccf-rgs-lex-out.txt is the output of setpart-ccf-rgs-lex-demo.cc.
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).
The demo uses the functions from
setpart-ccf-rgs-lex.h (fxt/src/comb/setpart-ccf-rgs-lex.h)
is-setpart-ccf-perm.h (fxt/src/comb/is-setpart-ccf-perm.h)
setpart-ck-rgs-out.txt is the output of setpart-ck-rgs-demo.cc.
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.
The demo uses the functions from
setpart-ck-rgs.h (fxt/src/comb/setpart-ck-rgs.h)
setpart-out.txt is the output of setpart-demo.cc.
Set partitions.
The demo uses the functions from
setpart.h (fxt/src/comb/setpart.h)
setpart.cc (fxt/src/comb/setpart.cc)
setpart-noncrossing-ll-out.txt is the output of setpart-noncrossing-ll-demo.cc.
Noncrossing set partitions via Catalan restricted growth strings (RGS).
Sets are in the form vector< vector
The demo uses the functions from
setpart-noncrossing-ll.h (fxt/src/comb/setpart-noncrossing-ll.h)
setpart-noncrossing-rgs-out.txt is the output of setpart-noncrossing-rgs-demo.cc.
Noncrossing set partitions of the n-set as restricted growth strings (RGS).
Lexicographic order.
The demo uses the functions from
setpart-noncrossing-rgs.h (fxt/src/comb/setpart-noncrossing-rgs.h)
setpart-p-rgs-lex-out.txt is the output of setpart-p-rgs-lex-demo.cc.
Set partitions of the n-set into p parts as restricted growth strings (RGS).
Counted by the Stirling numbers of second kind S(n,p).
Cf. OEIS sequence A008277.
The demo uses the functions from
setpart-p-rgs-lex.h (fxt/src/comb/setpart-p-rgs-lex.h)
setpart-rgs-fixed-content-vec-out.txt is the output of setpart-rgs-fixed-content-vec-demo.cc.
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.
The demo uses the functions from
setpart-rgs-fixed-content-vec.h (fxt/src/comb/setpart-rgs-fixed-content-vec.h)
setpart-rgs-gray-out.txt is the output of setpart-rgs-gray-demo.cc.
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.
The demo uses the functions from
setpart-rgs-gray.h (fxt/src/comb/setpart-rgs-gray.h)
setpart-rgs-gray.cc (fxt/src/comb/setpart-rgs-gray.cc)
setpart-rgs-lex-out.txt is the output of setpart-rgs-lex-demo.cc.
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.
The demo uses the functions from
setpart-rgs-lex.h (fxt/src/comb/setpart-rgs-lex.h)
setpart-rgs-subset-lex-out.txt is the output of setpart-rgs-subset-lex-demo.cc.
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.
Subset-lex order.
See Joerg Arndt, Subset-lex: did we miss an order?, (2014)
http://arxiv.org/abs/1405.6503
The demo uses the functions from
setpart-rgs-subset-lex.h (fxt/src/comb/setpart-rgs-subset-lex.h)
setpart-s-zero-map-rgs-out.txt is the output of setpart-s-zero-map-rgs-demo.cc.
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).
The demo uses the functions from
setpart-s-zero-map-rgs.h (fxt/src/comb/setpart-s-zero-map-rgs.h)
is-zero-map-rgs.h (fxt/src/comb/is-zero-map-rgs.h)
print-zero-map-rgs.h (fxt/src/comb/print-zero-map-rgs.h)
setpart-zero-map-rgs-out.txt is the output of setpart-zero-map-rgs-demo.cc.
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.
Cf. OEIS sequence A000110.
The demo uses the functions from
setpart-zero-map-rgs.h (fxt/src/comb/setpart-zero-map-rgs.h)
is-zero-map-rgs.h (fxt/src/comb/is-zero-map-rgs.h)
print-zero-map-rgs.h (fxt/src/comb/print-zero-map-rgs.h)
shift-subsets-out.txt is the output of shift-subsets-demo.cc.
Shifts-order for subsets of a binary word.
signed-perm-out.txt is the output of signed-perm-demo.cc.
Signed permutations (hyperoctahedral group).
The demo uses the functions from
signed-perm.h (fxt/src/comb/signed-perm.h)
perm-trotter.h (fxt/src/comb/perm-trotter.h)
ruler-func.h (fxt/src/comb/ruler-func.h)
signed-perm-gray-out.txt is the output of signed-perm-gray-demo.cc.
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).
The demo uses the functions from
signed-perm-gray.h (fxt/src/comb/signed-perm-gray.h)
perm-trotter.h (fxt/src/comb/perm-trotter.h)
ruler-func.h (fxt/src/comb/ruler-func.h)
skew-binary-out.txt is the output of skew-binary-demo.cc.
Skew binary numbers.
Loopless algorithm.
See http://en.wikipedia.org/wiki/Skew_binary_number_system
Cf. OEIS sequence A169683.
The demo uses the functions from
skew-binary.h (fxt/src/comb/skew-binary.h)
smooth-rfact-rgs-out.txt is the output of smooth-rfact-rgs-demo.cc.
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).
Cf. OEIS sequence A005773.
The demo uses the functions from
smooth-rfact-rgs.h (fxt/src/comb/smooth-rfact-rgs.h)
stirling1-out.txt is the output of stirling1-demo.cc.
Stirling numbers of the first kind (Stirling cycle numbers).
stirling2-out.txt is the output of stirling2-demo.cc.
Stirling numbers of the second kind (set numbers) and Bell numbers.
string-subst-out.txt is the output of string-subst-demo.cc.
String substitution engine (Lindenmayer system, or L-system).
The demo uses the functions from
string-subst.h (fxt/src/comb/string-subst.h)
string-subst-hilbert3d-out.txt is the output of string-subst-hilbert3d-demo.cc.
3-dimensional Hilbert curve generated by an L-system.
The demo uses the functions from
string-subst.h (fxt/src/comb/string-subst.h)
lindenmayer-system.h (fxt/src/comb/lindenmayer-system.h)
subset-debruijn-out.txt is the output of subset-debruijn-demo.cc.
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.
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.
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.
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.
Nonempty subsets of the set {0,1,2,...,n-1} in (subset-)lexicographic order.
Representation as list of parts.
Loopless generation.
Cf. OEIS sequence A108918
See Joerg Arndt, Subset-lex: did we miss an order?, (2014)
http://arxiv.org/abs/1405.6503
The demo uses the functions from
subset-lex.h (fxt/src/comb/subset-lex.h)
subset-sl-gray-out.txt is the output of subset-sl-gray-demo.cc.
Nonempty subsets of the set {0,1,2,...,n-1} in SL-Gray order.
Representation as list of parts.
Loopless generation.
See OEIS sequence A217262.
The demo uses the functions from
subset-sl-gray.h (fxt/src/comb/subset-sl-gray.h)
tree-lev-seq-out.txt is the output of tree-lev-seq-demo.cc.
Level sequences for unordered rooted trees.
Cf. OEIS sequence A000081.
The demo uses the functions from
tree-lev-seq.h (fxt/src/comb/tree-lev-seq.h)
tree-lev-seq-aux.h (fxt/src/comb/tree-lev-seq-aux.h)
tree-lev-seq-stats-out.txt is the output of tree-lev-seq-stats-demo.cc.
Statistics for (level sequences of) unordered rooted trees.
Cf. the following OEIS sequences:
A000081: all trees.
A034781: trees by height.
A033185: forests by number of trees.
A244372: trees by max branching number (out-degree).
A244454: trees by min branching number (out-degree) of non-leaf nodes.
The demo uses the functions from
tree-lev-seq.h (fxt/src/comb/tree-lev-seq.h)
word-stats.h (fxt/src/comb/word-stats.h)
weak-ascent-rgs-out.txt is the output of weak-ascent-rgs-demo.cc.
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.
The demo uses the functions from
weak-ascent-rgs.h (fxt/src/comb/weak-ascent-rgs.h)
weakly-unimodal-map-lex-out.txt is the output of weakly-unimodal-map-lex-demo.cc.
Weakly unimodal map, 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].
The demo uses the functions from
weakly-unimodal-map-lex.h (fxt/src/comb/weakly-unimodal-map-lex.h)
is-unimodal.h (fxt/src/comb/is-unimodal.h)
wfl-hilbert-out.txt is the output of wfl-hilbert-demo.cc.
Fred Lunnon's (second) iterative algorithm to convert linear coordinate
into coordinates of d-dimensional Hilbert curve (and back).
The demo uses the functions from
wfl-hilbert.h (fxt/src/comb/wfl-hilbert.h)
young-tab-rgs-out.txt is the output of young-tab-rgs-demo.cc.
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).
The demo uses the functions from
young-tab-rgs.h (fxt/src/comb/young-tab-rgs.h)
print-young-tab-rgs-aa.cc (fxt/src/comb/print-young-tab-rgs-aa.cc)
is-shifted-young-tab-rgs.h (fxt/src/comb/is-shifted-young-tab-rgs.h)
young-tab-rgs-subset-lex-out.txt is the output of young-tab-rgs-subset-lex-demo.cc.
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).
The demo uses the functions from
young-tab-rgs-subset-lex.h (fxt/src/comb/young-tab-rgs-subset-lex.h)
print-young-tab-rgs-aa.cc (fxt/src/comb/print-young-tab-rgs-aa.cc)