combo
combo,
a MATLAB code which
ranks, unranks, enumerates, lists and
randomly selects balanced sequences, cycles, graphs, Gray codes,
subsets, partitions, permutations, restricted growth functions,
Pruefer codes and trees.
The objects include:

BAL, balanced sequences, included nested parentheses,
Dyck lattice paths, ballot paths;

CYCLE, permutations of the first N integers in cycle form;

GRAPH, graphs stored as a list of edges.

GRAY, Gray codes;

KNAPSACK, optimally filling a knapsack of given size using
a set of smaller objects;

KSUBSET, subsets of size exactly K from a set of N objects;

NPART, partitions of an integer having exactly N parts;

PART, partitions of an integer;

PERM, permutations of the first N integers in standard form;

PRUEFER, Pruefer codes;

RGF, restricted growth functions;

SETPART, partitions of a set;

SUBSET, subsets of a set of N objects;

TABLEAU, tableaus;

TREE, trees;
Some of these sets of objects can be ordered in several different
ways, and in some cases, a separate set of ranking, unranking, and
successor routines are available for the various orderings
(lexical, colexical, revolving door, TrotterJohnson).
Kreher and Stinson provide C sourcecode for the routines,
as well as other information, at
their web site.
Licensing:
The information on this web page is distributed under the MIT license.
Languages:
combo is available in
a C version and
a C++ version and
a Fortran77 version and
a Fortran90 version and
a MATLAB version and
an Octave version and
a Python version.
Related Data and Programs:
combo_test
floyd,
a MATLAB code which
implements Floyd's algorithm for finding the shortest distance between
pairs of nodes on a directed graph.
gray_code_display,
a MATLAB code which
computes the Hamming distance tables for both the binary and gray codes,
and displays 3d plots that illustrate how the gray code does a better job
of providing nearby representations for nearby numbers.
matlab_combinatorics,
a MATLAB code which
considers a variety of problems in combinatorics involving
counting, combinations, permutations, and so on.
monomial,
a MATLAB code which
enumerates, lists, ranks, unranks and randomizes multivariate monomials
in a space of m dimensions, with total degree less than n,
equal to n, or lying within a given range.
polynomial,
a MATLAB code which
adds, multiplies, differentiates, evaluates and prints multivariate
polynomials in a space of m dimensions.
polynomial_multiply,
a MATLAB code which
multiplies two polynomials p(x) and q(x).
set_theory,
a MATLAB code which
demonstrates MATLAB commands that implement various set theoretic operations.
subset,
a MATLAB code which
generates, ranks and unranks various combinatorial objects.
toms515,
a MATLAB code which
can select subsets of size k from a set of size n.
This is a version of ACM TOMS algorithm 515,
by Bill Buckles, Matthew Lybanon.
unicycle,
a MATLAB code which
considers permutations containing a single cycle, sometimes called
cyclic permutations.
Reference:

Donald Kreher, Douglas Simpson,
Combinatorial Algorithms,
CRC Press, 1998,
ISBN: 084933988X,
LC: QA164.K73.
Source Code:

backtrack.m,
supervises a backtrack search.

bal_seq_check.m,
checks a balanced sequence.

bal_seq_enum.m,
enumerates the balanced sequences.

bal_seq_random.m,
randomly selects a balanced sequence.

bal_seq_rank.m,
ranks a balanced sequence.

bal_seq_successor.m,
returns the successor of a balanced sequence.

bal_seq_to_tableau.m,
converts a balanced sequence to a tableau.

bal_seq_unrank.m,
unranks a balanced sequence.

bell_numbers.m,
computes the Bell numbers.

bell_values.m,
returns some values of the Bell numbers.

cycle_check.m,
checks a permutation in cycle form.

cycle_to_perm.m,
converts a permutation from cycle to array form.

dist_enum.m,
enumerates the number of distributions of indistinguishable objects.

dist_next.m,
returns the next distribution of indistinguishable objects.

edge_check.m,
checks a graph described by an edge list.

edge_degree.m,
returns the degree of each node in a graph described by an edge list.

edge_enum.m,
enumerates the maximum number of edges in a graph with a given
number of nodes.

gamma_log_values.m,
returns selected values of the logarithm of the Gamma function.

gray_code_check.m,
checks a Gray code element.

gray_code_enum.m,
enumerates the Gray codes on N digits.

gray_code_random.m,
returns a random Gray code of N digits.

gray_code_rank.m,
computes the rank of a Gray code element.

gray_code_successor.m,
computes the binary reflected Gray code successor.

gray_code_unrank.m,
computes the Gray code element of given rank.

i4_fall.m,
evaluates the falling factorial function.

i4_fall_values.m,
returns some values of the falling factorial function.

i4_uniform_ab.m,
returns a pseudorandom I4 in a given range;

i4mat_print.m,
prints an I4MAT;

i4mat_print_some.m,
prints some of an I4MAT;

i4vec_backtrack.m,
supervises a backtrack search for an I4VEC.

i4vec_dot_product.m,
computes the dot product of two I4VEC's.

i4vec_indicator1.m,
sets an I4VEC to the indicator1 vector.

i4vec_part1.m,
partitions an integer N into NPART parts.

i4vec_part2.m,
partitions an integer N into NPART nearly equal parts.

i4vec_print.m,
prints an I4VEC.

i4vec_reverse.m,
reverses the order of the entries of an I4VEC;

i4vec_search_binary_a.m,
searches the ascending sorted I4VEC for a value.

i4vec_search_binary_d.m,
searches the descending sorted I4VEC for a value.

i4vec_sort_insert_a.m,
uses an ascending insertion sort on an I4VEC.

i4vec_sort_insert_d.m,
uses a descending insertion sort on an I4VEC.

i4vec_transpose_print.m,
prints an I4VEC "transposed";

i4vec_uniform_ab.m,
fills an I4VEC with uniform random integers between A and B.

knapsack_01.m,
solves the 0,1 knapsack problem.

knapsack_rational.m,
solves the rational knapsack problem.

knapsack_reorder.m,
reorders the knapsack data by "profit density".

ksubset_colex_check.m,
checks a K subset in colex form.

ksubset_colex_rank.m,
computes the colex rank of a K subset.

ksubset_colex_successor.m,
computes the K subset colex successor.

ksubset_colex_unrank.m,
computes the K subset of given colex rank.

ksubset_enum.m,
enumerates the K element subsets of an N set.

ksubset_lex_check.m,
checks a K subset in lex form.

ksubset_lex_rank.m,
computes the lexicographic rank of a K subset.

ksubset_lex_successor.m,
computes the K subset lexicographic successor.

ksubset_lex_unrank.m,
computes the K subset of given lexicographic rank.

ksubset_random.m,
returns a random K subset of an N set.

ksubset_revdoor_rank.m,
computes the revolving door rank of a K subset.

ksubset_revdoor_successor.m,
computes the K subset revolving door successor.

ksubset_revdoor_unrank.m,
computes the K subset of given revolving door rank.

marriage.m,
finds a stable set of marriages for given preferences.

mountain.m,
enumerates the mountains.

npart_enum.m,
enumerates the number of partitions of N with NPART parts.

npart_rsf_lex_random.m,
returns a random RSF NPART partition.

npart_rsf_lex_rank.m,
computes the lex rank of an RSF NPART partition.

npart_rsf_lex_successor.m,
computes the RSF lex successor for NPART partitions.

npart_rsf_lex_unrank.m,
unranks an RSF NPART partition in the lex ordering.

npart_sf_lex_successor.m,
computes SF NPART partition.

npart_table.m,
tabulates the number of partitions of N having NPART parts.

part_enum.m,
enumerates the partitions of an integer.

part_rsf_check.m,
checks a reverse standard form partition of an integer.

part_sf_check.m,
checks a standard form partition of an integer.

part_sf_conjugate.m,
computes the conjugate of a partition.

part_sf_majorize.m,
determines if partition A majorizes partition B.

part_successor.m,
computes the lexicographic partition successor.

part_table.m,
tabulates the number of partitions of N.

partition_greedy.m,
attacks the partition problem with a greedy algorithm.

partn_enum.m,
enumerates the partitions of N with maximum element NMAX.

partn_sf_check.m,
checks an SF partition of an integer with largest entry NMAX.

partn_successor.m,
computes partitions whose largest part is NMAX.

perm_check.m,
checks that a vector represents a permutation.

perm_enum.m,
enumerates the permutations on N digits.

perm_inv.m,
computes the inverse of a permutation.

perm_lex_rank.m,
computes the lexicographic rank of a permutation.

perm_lex_successor.m,
computes the lexicographic permutation successor.

perm_lex_unrank.m,
computes the permutation of given lexicographic rank.

perm_mul.m,
computes the product of two permutations.

perm_parity.m,
computes the parity of a permutation.

perm_print.m,
prints a permutation.

perm_random.m,
returns a random permutation.

perm_tj_rank.m,
computes the TrotterJohnson rank of a permutation.

perm_tj_successor.m,
computes the TrotterJohnson permutation successor.

perm_tj_unrank.m,
computes the permutation of given TrotterJohnson rank.

perm_to_cycle.m,
converts a permutation from array to cycle form.

pivot_sequence_check.m,
checks a pivot sequence.

pivot_sequence_enum.m,
enumerates pivot sequences.

pivot_sequence_random.m,
returns a random pivot sequence.

pivot_sequence_successor.m,
computes the pivot sequence successor.

pruefer_check.m,
checks a Pruefer code.

pruefer_enum.m,
enumerates the Pruefer codes on N2 digits.

pruefer_random.m,
returns a random Pruefer code on N2 digits.

pruefer_rank.m,
ranks a Pruefer code.

pruefer_successor.m,
computes the lexical Pruefer sequence successor.

pruefer_to_tree.m,
converts a Pruefer code to a tree.

pruefer_unrank.m,
unranks a Pruefer code.

queens.m,
finds possible positions for the Kth nonattacking queen.

r8vec_backtrack.m,
supervises a backtrack search for an R8VEC.

rgf_check.m,
checks a restricted growth function.

rgf_enum.m,
enumerates the restricted growth functions on M.

rgf_rank.m,
ranks a restricted growth function.

rgf_successor.m,
generates the next restricted growth function.

rgf_to_setpart.m,
converts a restricted growth function to a set partition.

rgf_unrank.m,
returns the restricted growth function of a given rank.

rgf_g_table.m,
tabulates the restricted growth functions.

setpart_check.m,
checks a set partition.

setpart_enum.m,
enumerates the partitions of a set of M elements.

setpart_to_rgf.m,
converts a set partition to a restricted growth function.

stirling_numbers1.m,
computes the Stirling numbers of the first kind.

stirling_numbers2.m,
computes the Stirling numbers of the second kind.

subset_check.m,
checks a subset.

subset_colex_rank.m,
computes the colexicographic rank of a subset.

subset_colex_successor.m,
computes the subset colexicographic successor.

subset_colex_unrank.m,
computes the subset of given colexicographic rank.

subset_complement.m,
computes the complement of a set.

subset_distance_hamming.m,
computes the Hamming distance between two sets.

subset_enum.m,
enumerates the subsets of a set with N elements.

subset_intersect.m,
computes the intersection of two sets.

subset_lex_rank.m,
computes the rank of a given lexicographic subset.

subset_lex_successor.m,
computes the lexicographic successor of a subset.

subset_lex_unrank.m,
computes the subset of a given lexicographic rank.

subset_random.m,
returns a random subset of an N set.

subset_union.m,
computes the union of two sets.

subset_weight.m,
computes the Hamming weight of a set.

subset_xor.m,
computes the symmetric difference of two sets.

subset_sum_swap.m,
seeks a solution of the subset sum problem by swapping.

tableau_check.m,
checks a 2 by N tableau.

tableau_enum.m,
enumerates the 2 by N standard tableaus.

tableau_to_bal_seq.m,
converts a 2 by N tableau to a balanced sequence.

tree_check.m,
checks a tree.

tree_enum.m,
enumerates the trees on N nodes.

tree_random.m,
randomly selects a tree on N nodes.

tree_rank.m,
ranks a tree.

tree_successor.m,
returns the successor of a tree.

tree_to_pruefer.m,
converts a tree to a Pruefer code.

tree_unrank.m,
unranks a tree.
Last revised on 25 June 2024.
<% John Burkardt >