combo

combo, a Fortran77 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.

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_making, a Fortran77 library which considers the change making problem, in which a given sum is to be formed using coins of various denominations.

combination_lock, a Fortran77 program which simulates the process of determining the secret combination of a lock.

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

KNAPSACK, a Fortran77 library which solves a variety of knapsack problems.

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

KNAPSACK_01, a dataset directory which contains test data for the 0/1 knapsack problem;

LAMP, a Fortran77 library which solves linear assignment and matching problems.

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

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

PARTIAL_DIGEST, a Fortran90 library which solves the partial digest problem.

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

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

SELECT, a Fortran77 library which generates various combinatorial objects.

SET_THEORY, a Fortran90 library which demonstrates various set theoretic operations using several models of a set.

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

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

UNICYCLE, a Fortran77 library which considers permutations containing a single cycle, sometimes called cyclic permutations.

Reference:

1. Milton Abramowitz, Irene Stegun,
   Handbook of Mathematical Functions,
   National Bureau of Standards, 1964,
   ISBN: 0-486-61272-4,
   LC: QA47.A34.
2. Paul Bratley, Bennett Fox, Linus Schrage,
   A Guide to Simulation,
   Second Edition,
   Springer, 1987,
   ISBN: 0387964673,
   LC: QA76.9.C65.B73.
3. William Cody, Kenneth Hillstrom,
   Chebyshev Approximations for the Natural Logarithm of the Gamma Function, Mathematics of Computation,
   Volume 21, Number 98, April 1967, pages 198-203.
4. Robert Fenichel,
   Algorithm 329: Distribution of Indistinguishable Objects into Distinguishable Slots,
   Communications of the ACM,
   Volume 11, Number 6, June 1968, page 430.
5. Bennett Fox,
   Algorithm 647: Implementation and Relative Efficiency of Quasirandom Sequence Generators,
   ACM Transactions on Mathematical Software,
   Volume 12, Number 4, December 1986, pages 362-376.
6. John Hart, Ward Cheney, Charles Lawson, Hans Maehly, Charles Mesztenyi, John Rice, Henry Thacher, Christoph Witzgall,
   Computer Approximations,
   Wiley, 1968,
   LC: QA297.C64.
7. Brian Hayes,
   The Easiest Hard Problem,
   American Scientist,
   Volume 90, Number 2, March-April 2002, pages 113-117.
8. Donald Kreher, Douglas Simpson,
   Combinatorial Algorithms,
   CRC Press, 1998,
   ISBN: 0-8493-3988-X,
   LC: QA164.K73.
9. Pierre LEcuyer,
   Random Number Generation,
   in Handbook of Simulation,
   edited by Jerry Banks,
   Wiley, 1998,
   ISBN: 0471134031,
   LC: T57.62.H37.
10. Peter Lewis, Allen Goodman, James Miller,
    A Pseudo-Random Number Generator for the System/360,
    IBM Systems Journal,
    Volume 8, 1969, pages 136-143.
11. Albert Nijenhuis, Herbert Wilf,
    Combinatorial Algorithms for Computers and Calculators,
    Second Edition,
    Academic Press, 1978,
    ISBN: 0-12-519260-6,
    LC: QA164.N54.
12. Robert Sedgewick,
    Algorithms in C,
    Addison-Wesley, 1990,
    ISBN: 0-201-51425-7,
    LC: QA76.73.C15S43.
13. Jack vanLint, Richard Wilson,
    A Course in Combinatorics,
    Cambridge, 1992,
    ISBN: 0-521-42260-4,
    LC: QA164.L56.
14. ML Wolfson, HV Wright,
    Algorithm 160: Combinatorial of M Things Taken N at a Time,
    Communications of the ACM,
    Volume 6, Number 4, April 1963, page 161.

Source Code:

• combo.f, the source code;
• combo.sh, commands to compile the source code;