# 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, Trotter-Johnson).

Kreher and Stinson provide C source-code for the routines, as well as other information, at their web site.

### 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:

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:

1. Donald Kreher, Douglas Simpson,
Combinatorial Algorithms,
CRC Press, 1998,
ISBN: 0-8493-3988-X,
LC: QA164.K73.

### Source Code:

Last revised on 25 June 2024. <%-- John Burkardt -->