COMBO
Kreher and Stinson Combinatorial Routines

COMBO is a FORTRAN77 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

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

Licensing:

The computer code and data files 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 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;

Examples and Tests:

• combo_prb.f, the calling program;
• combo_prb.sh, commands to compile, link and run the calling program;
• combo_prb_output.txt, the output file.

List of Routines:

• BACKTRACK supervises a backtrack search.
• BAL_SEQ_CHECK checks a balanced sequence.
• BAL_SEQ_ENUM enumerates the balanced sequences.
• BAL_SEQ_RANK ranks a balanced sequence.
• BAL_SEQ_SUCCESSOR computes the lexical balanced sequence successor.
• BAL_SEQ_TO_TABLEAU converts a balanced sequence to a 2 by N tableau.
• BAL_SEQ_UNRANK unranks a balanced sequence.
• BELL_NUMBERS computes the Bell numbers.
• BINOMIAL computes the binomial coefficient C(N,K).
• COMBIN computes the combinatorial coefficient C(N,K).
• CYCLE_CHECK checks a permutation in cycle form.
• CYCLE_TO_PERM converts a permutation from cycle to array form.
• DIST_ENUM returns the number of distributions of indistinguishable objects.
• DIST_NEXT returns the next distribution of indistinguishable objects.
• EDGE_CHECK checks a graph stored by edges.
• EDGE_DEGREE returns the degree of the nodes of a graph stored by edges.
• EDGE_ENUM enumerates the maximum number of edges in a graph on N_NODE nodes.
• FALL computes the falling factorial function [X]_N.
• GRAY_CODE_CHECK checks a Gray code element.
• GRAY_CODE_ENUM enumerates the Gray codes on N digits.
• GRAY_CODE_RANK computes the rank of a Gray code element.
• GRAY_CODE_SUCCESSOR computes the binary reflected Gray code successor.
• GRAY_CODE_UNRANK computes the Gray code element of given rank.
• I4_FACTORIAL computes the factorial of an I4.
• I4_FACTORIAL_VALUES returns values of the factorial function for testing.
• I4_HUGE returns a "huge" I4.
• I4_UNIFORM returns a scaled pseudorandom I4.
• I4VEC_BACKTRACK supervises a backtrack search for an I4VEC.
• I4VEC_INDICATOR sets an I4VEC to the indicator vector.
• I4VEC_PART1 partitions an integer N into NPART parts.
• I4VEC_PART2 partitions an integer N into NPART nearly equal parts.
• I4VEC_PRINT prints an I4VEC.
• I4VEC_REVERSE reverses the elements of an I4VEC.
• I4VEC_SEARCH_BINARY_A searches the ascending sorted I4VEC for a value.
• I4VEC_SEARCH_BINARY_D searches a descending sorted I4VEC for a value.
• I4VEC_SORT_INSERT_A uses an ascending insertion sort on an I4VEC.
• I4VEC_SORT_INSERT_D uses a descending insertion sort on an I4VEC.
• KNAPSACK_01 solves the 0/1 knapsack problem.
• KNAPSACK_RATIONAL solves the rational knapsack problem.
• KNAPSACK_REORDER reorders the knapsack data by "profit density".
• KSUBSET_COLEX_CHECK checks a K subset in colex form.
• KSUBSET_COLEX_RANK computes the colex rank of a K subset.
• KSUBSET_COLEX_SUCCESSOR computes the K subset colex successor.
• KSUBSET_COLEX_UNRANK computes the K subset of given colex rank.
• KSUBSET_ENUM enumerates the K element subsets of an N set.
• KSUBSET_LEX_CHECK checks a K subset in lex form.
• KSUBSET_LEX_RANK computes the lexicographic rank of a K subset.
• KSUBSET_LEX_SUCCESSOR computes the K subset lexicographic successor.
• KSUBSET_LEX_UNRANK computes the K subset of given lexicographic rank.
• KSUBSET_REVDOOR_RANK computes the revolving door rank of a K subset.
• KSUBSET_REVDOOR_SUCCESSOR computes the K subset revolving door successor.
• KSUBSET_REVDOOR_UNRANK computes the K subset of given revolving door rank.
• MARRIAGE finds a stable set of marriages for given preferences.
• MOUNTAIN enumerates the mountains.
• NPART_ENUM enumerates the number of partitions of N with NPART parts.
• NPART_RSF_LEX_RANDOM returns a random RSF NPART partition.
• NPART_RSF_LEX_RANK computes the lex rank of an RSF NPART partition.
• NPART_RSF_LEX_SUCCESSOR computes the RSF lex successor for NPART partitions.
• NPART_RSF_LEX_UNRANK unranks an RSF NPART partition in the lex ordering.
• NPART_SF_LEX_SUCCESSOR computes SF NPART partition.
• NPART_TABLE tabulates the number of partitions of N having NPART parts.
• PART_ENUM enumerates the number of partitions of N.
• PART_RSF_CHECK checks a reverse standard form partition of an integer.
• PART_SF_CHECK checks a standard form partition of an integer.
• PART_SF_CONJUGATE computes the conjugate of a partition.
• PART_SF_MAJORIZE determines if partition A majorizes partition B.
• PART_SUCCESSOR computes the lexicographic partition successor.
• PART_TABLE tabulates the number of partitions of N.
• PARTITION_GREEDY attacks the partition problem with a greedy algorithm.
• PARTN_SF_CHECK checks an SF partition of an integer with largest entry NMAX.
• PARTN_ENUM enumerates the partitions of N with maximum element NMAX.
• PARTN_SUCCESSOR computes partitions whose largest part is NMAX.
• PERM_CHECK checks a representation of a permutation.
• PERM_ENUM enumerates the permutations on N digits.
• PERM_INV computes the inverse of a permutation.
• PERM_LEX_RANK computes the lexicographic rank of a permutation.
• PERM_LEX_SUCCESSOR computes the lexicographic permutation successor.
• PERM_LEX_UNRANK computes the permutation of given lexicographic rank.
• PERM_MUL computes the product of two permutations.
• PERM_PARITY computes the parity of a permutation.
• PERM_PRINT prints a permutation.
• PERM_TJ_RANK computes the Trotter-Johnson rank of a permutation.
• PERM_TJ_SUCCESSOR computes the Trotter-Johnson permutation successor.
• PERM_TJ_UNRANK computes the permutation of given Trotter-Johnson rank.
• PERM_TO_CYCLE converts a permutation from array to cycle form.
• PRUEFER_CHECK checks a Pruefer code.
• PRUEFER_ENUM enumerates the Pruefer codes on N-2 digits.
• PRUEFER_RANK ranks a Pruefer code.
• PRUEFER_SUCCESSOR computes the lexical Pruefer sequence successor.
• PRUEFER_TO_TREE converts a Pruefer code to a tree.
• PRUEFER_UNRANK unranks a Pruefer code.
• QUEENS finds possible positions for the K-th nonattacking queen.
• R4_UNIFORM returns a scaled pseudorandom R4.
• R8_GAMMA_LOG calculates the natural logarithm of GAMMA ( X ) for positive X.
• R8VEC_BACKTRACK supervises a backtrack search for an R8VEC.
• RGF_CHECK checks a restricted growth function.
• RGF_ENUM enumerates the restricted growth functions on M.
• RGF_G_ENUM enumerates the generalized restricted growth functions.
• RGF_RANK ranks a restricted growth function.
• RGF_SUCCESSOR generates the next restricted growth function.
• RGF_TO_SETPART converts a restricted growth function to a set partition.
• RGF_UNRANK returns the restricted growth function of a given rank.
• SETPART_CHECK checks a set partition.
• SETPART_ENUM enumerates the partitions of a set of M elements.
• SETPART_TO_RGF converts a set partition to a restricted growth function.
• STIRLING_NUMBERS1 computes Stirling numbers of the first kind.
• STIRLING_NUMBERS2 computes Stirling numbers of the second kind.
• SUBSET_COLEX_RANK computes the colexicographic rank of a subset.
• SUBSET_COLEX_SUCCESSOR computes the subset colexicographic successor.
• SUBSET_COLEX_UNRANK computes the subset of given colexicographic rank.
• SUBSET_CHECK checks a subset.
• SUBSET_COMPLEMENT computes the complement of a set.
• SUBSET_DISTANCE computes the Hamming distance between two sets.
• SUBSET_ENUM enumerates the subsets of a set with N elements.
• SUBSET_INTERSECT computes the intersection of two sets.
• SUBSET_LEX_RANK computes the lexicographic rank of a subset.
• SUBSET_LEX_SUCCESSOR computes the subset lexicographic successor.
• SUBSET_LEX_UNRANK computes the subset of given lexicographic rank.
• SUBSET_UNION computes the union of two sets.
• SUBSET_WEIGHT computes the Hamming weight of a set.
• SUBSET_XOR computes the symmetric difference of two sets.
• SUBSETSUM_SWAP seeks a solution of the subset sum problem by swapping.
• TABLEAU_CHECK checks a 2 by N tableau.
• TABLEAU_ENUM enumerates the 2 by N standard tableaus.
• TABLEAU_TO_BAL_SEQ converts a 2 by N tableau to a balanced sequence.
• TIMESTAMP prints the current YMDHMS date as a time stamp.
• TREE_CHECK checks a tree.
• TREE_ENUM enumerates the trees on N nodes.
• TREE_RANK ranks a tree.
• TREE_SUCCESSOR returns the successor of a tree.
• TREE_TO_PRUEFER converts a tree to a Pruefer code.
• TREE_UNRANK unranks a tree.

You can go up one level to the FORTRAN77 source codes.