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:

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:


Last revised on 25 September 2023.