COMBO
Kreher and Stinson Combinatorial Routines


COMBO is a C++ library 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

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.

Licensing:

The computer code and data files described and made available on this web page are distributed under the GNU LGPL 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 a Python version.

Related Data and Programs:

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

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

KNAPSACK_01, a C++ library which uses brute force to solve small versions of the 0/1 knapsack problem;

LEGENDRE_PRODUCT_POLYNOMIAL, a C++ library which defines Legendre product polynomials, creating a multivariate polynomial as the product of univariate Legendre polynomials.

MONOMIAL, a C++ library 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.

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

POLYNOMIAL, a C++ library which adds, multiplies, differentiates, evaluates and prints multivariate polynomials in a space of M dimensions.

SELECT, a FORTRAN90 library which generates various combinatorial objects.

SUBSET, a C++ library which generates, ranks and unranks various combinatorial objects.

SUBSET_SUM, a C++ library which seeks solutions of the subset sum problem.

TOMS515, a C++ library 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 C++ library 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:

Examples and Tests:

List of Routines:

You can go up one level to the C++ source codes.


Last revised on 28 July 2011.