combo


combo, a Fortran90 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:

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

change_dynamic, 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.

knapsack, a Fortran77 code which solves a variety of knapsack problems.

knapsack_01_brute, 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 selects 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 2024.