COMBO
Kreher and Stinson Combinatorial Routines

COMBO is a FORTRAN77 library which implements some of the combinatorial algorithms of Kreher and Stinson.

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

Related Data and Programs:

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.

GRAFPACK, a FORTRAN90 library which carries out computations involving graphs.

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

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.

LAU_NP, a FORTRAN90 library which implements heuristic algorithms for various NP-hard combinatorial problems.

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.

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.