# combo

combo, a FORTRAN90 code which includes routines for ranking, unranking, enumerating and randomly selecting balanced sequences, cycles, graphs, Gray codes, subsets, partitions, permutations, restricted growth functions, Pruefer codes and trees.

Routines are available to count, list, rank and unrank such objects

• BAL, balanced sequences;
• 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 FORTRAN90 version and a MATLAB version and a Python version.

### Related Data and Programs:

CHANGE_MAKING, a FORTRAN90 code which considers the change making problem, in which a given sum is to be formed using coins of various denominations.

FLOYD, a FORTRAN90 code which implements Floyd's algorithm for finding the shortest distance between pairs of nodes on a directed graph.

GRAFPACK, a FORTRAN90 code which carries out computations involving graphs.

KNAPSACK, a FORTRAN77 code which solves a variety of knapsack problems.

KNAPSACK_01, a FORTRAN90 code which uses brute force to solve small versions of the 0/1 knapsack problem;

LAMP, a FORTRAN77 code which solves linear assignment and matching problems.

LAU_NP, a FORTRAN90 code which implements heuristic algorithms for various NP-hard combinatorial problems.

LEGENDRE_PRODUCT_POLYNOMIAL, a FORTRAN90 code which defines Legendre product polynomials, creating a multivariate polynomial as the product of univariate Legendre polynomials.

MONOMIAL, a FORTRAN90 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.

PARTIAL_DIGEST, a FORTRAN90 code which solves the partial digest problem.

PARTITION_PROBLEM, a FORTRAN90 code which seeks solutions of the partition problem, splitting a set of integers into two subsets with equal sum.

POLYNOMIAL, a FORTRAN90 code which adds, multiplies, differentiates, evaluates and prints multivariate polynomials in a space of M dimensions.

SELECT, a FORTRAN90 code which generates various combinatorial objects.

SET_THEORY, a FORTRAN90 code which demonstrates various set theoretic operations using several models of a set.

SUBSET, a FORTRAN90 code which generates, ranks and unranks various combinatorial objects.

SUBSET_SUM, a FORTRAN90 code which seeks solutions of the subset sum problem.

TOMS515, a FORTRAN90 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 FORTRAN90 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 10 June 2020.