COMBO
Kreher and Stinson Combinatorial Routines

COMBO is a MATLAB 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 MATLAB program which simulates the process of determining the secret combination of a lock.

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

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

SET_THEORY, a MATLAB library which demonstrates MATLAB commands that implement various set theoretic operations.

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

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

UNICYCLE, a MATLAB 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:

• backtrack.m, supervises a backtrack search.
• bal_seq_check.m, checks a balanced sequence.
• bal_seq_enum.m, enumerates the balanced sequences.
• bal_seq_rank.m, ranks a balanced sequence.
• bal_seq_successor.m, returns the successor of a balanced sequence.
• bal_seq_to_tableau.m, converts a balanced sequence to a tableau.
• bal_seq_unrank.m, unranks a balanced sequence.
• bell_numbers.m, computes the Bell numbers.
• bell_values.m, returns some values of the Bell numbers.
• binomial.m, computes the binomial coefficient C(N,K).
• combin.m, computes the binomial coefficient C(N,K).
• cycle_check.m, checks a permutation in cycle form.
• cycle_to_perm.m, converts a permutation from cycle to array form.
• dist_enum.m, enumerates the number of distributions of indistinguishable objects.
• dist_next.m, returns the next distribution of indistinguishable objects.
• edge_check.m, checks a graph described by an edge list.
• edge_degree.m, returns the degree of each node in a graph described by an edge list.
• edge_enum.m, enumerates the maximum number of edges in a graph with a given number of nodes.
• fall.m, evaluates the falling factorial function.
• gray_code_check.m, checks a Gray code element.
• gray_code_enum.m, enumerates the Gray codes on N digits.
• gray_code_rank.m, computes the rank of a Gray code element.
• gray_code_successor.m, computes the binary reflected Gray code successor.
• gray_code_unrank.m, computes the Gray code element of given rank.
• i4_factorial.m, computes the factorial function.
• i4_factorial_values.m, returns some values of the factorial function.
• i4_huge.m, returns a huge I4;
• i4_uniform.m, returns a pseudorandom I4 in a given range;
• i4vec_backtrack.m, supervises a backtrack search for an I4VEC.
• i4vec_indicator.m, sets an I4VEC to the indicator vector.
• i4vec_part1.m, partitions an integer N into NPART parts.
• i4vec_part2.m, partitions an integer N into NPART nearly equal parts.
• i4vec_print.m, prints an I4VEC.
• i4vec_reverse.m, reverses the order of the entries of an I4VEC;
• i4vec_search_binary_a.m, searches the ascending sorted I4VEC for a value.
• i4vec_search_binary_d.m, searches the descending sorted I4VEC for a value.
• i4vec_sort_insert_a.m, uses an ascending insertion sort on an I4VEC.
• i4vec_sort_insert_d.m, uses a descending insertion sort on an I4VEC.
• knapsack_01.m, solves the 0,1 knapsack problem.
• knapsack_rational.m, solves the rational knapsack problem.
• knapsack_reorder.m, reorders the knapsack data by "profit density".
• ksubset_colex_check.m, checks a K subset in colex form.
• ksubset_colex_rank.m, computes the colex rank of a K subset.
• ksubset_colex_successor.m, computes the K subset colex successor.
• ksubset_colex_unrank.m, computes the K subset of given colex rank.
• ksubset_enum.m, enumerates the K element subsets of an N set.
• ksubset_lex_check.m, checks a K subset in lex form.
• ksubset_lex_rank.m, computes the lexicographic rank of a K subset.
• ksubset_lex_successor.m, computes the K subset lexicographic successor.
• ksubset_lex_unrank.m, computes the K subset of given lexicographic rank.
• ksubset_revdoor_rank.m, computes the revolving door rank of a K subset.
• ksubset_revdoor_successor.m, computes the K subset revolving door successor.
• ksubset_revdoor_unrank.m, computes the K subset of given revolving door rank.
• marriage.m, finds a stable set of marriages for given preferences.
• mountain.m, enumerates the mountains.
• npart_enum.m, enumerates the number of partitions of N with NPART parts.
• npart_rsf_lex_random.m, returns a random RSF NPART partition.
• npart_rsf_lex_rank.m, computes the lex rank of an RSF NPART partition.
• npart_rsf_lex_successor.m, computes the RSF lex successor for NPART partitions.
• npart_rsf_lex_unrank.m, unranks an RSF NPART partition in the lex ordering.
• npart_sf_lex_successor.m, computes SF NPART partition.
• npart_table.m, tabulates the number of partitions of N having NPART parts.
• part_enum.m, enumerates the partitions of an integer.
• part_rsf_check.m, checks a reverse standard form partition of an integer.
• part_sf_check.m, checks a standard form partition of an integer.
• part_sf_conjugate.m, computes the conjugate of a partition.
• part_sf_majorize.m, determines if partition A majorizes partition B.
• part_successor.m, computes the lexicographic partition successor.
• part_table.m, tabulates the number of partitions of N.
• partition_greedy.m, attacks the partition problem with a greedy algorithm.
• partn_enum.m, enumerates the partitions of N with maximum element NMAX.
• partn_sf_check.m, checks an SF partition of an integer with largest entry NMAX.
• partn_successor.m, computes partitions whose largest part is NMAX.
• perm_check.m, checks that a vector represents a permutation.
• perm_enum.m, enumerates the permutations on N digits.
• perm_inv.m, computes the inverse of a permutation.
• perm_lex_rank.m, computes the lexicographic rank of a permutation.
• perm_lex_successor.m, computes the lexicographic permutation successor.
• perm_lex_unrank.m, computes the permutation of given lexicographic rank.
• perm_mul.m, computes the product of two permutations.
• perm_parity.m, computes the parity of a permutation.
• perm_print.m, prints a permutation.
• perm_tj_rank.m, computes the Trotter-Johnson rank of a permutation.
• perm_tj_successor.m, computes the Trotter-Johnson permutation successor.
• perm_tj_unrank.m, computes the permutation of given Trotter-Johnson rank.
• perm_to_cycle.m, converts a permutation from array to cycle form.
• pruefer_check.m, checks a Pruefer code.
• pruefer_enum.m, enumerates the Pruefer codes on N-2 digits.
• pruefer_rank.m, ranks a Pruefer code.
• pruefer_successor.m, computes the lexical Pruefer sequence successor.
• pruefer_to_tree.m, converts a Pruefer code to a tree.
• pruefer_unrank.m, unranks a Pruefer code.
• queens.m, finds possible positions for the K-th nonattacking queen.
• r8_gamma_log.m, returns the logarithm of the gamma function.
• r8vec_backtrack.m, supervises a backtrack search for an R8VEC.
• rgf_check.m, checks a restricted growth function.
• rgf_enum.m, enumerates the restricted growth functions on M.
• rgf_g_enum.m, enumerates the generalized restricted growth functions.
• rgf_rank.m, ranks a restricted growth function.
• rgf_successor.m, generates the next restricted growth function.
• rgf_to_setpart.m, converts a restricted growth function to a set partition.
• rgf_unrank.m, returns the restricted growth function of a given rank.
• setpart_check.m, checks a set partition.
• setpart_enum.m, enumerates the partitions of a set of M elements.
• setpart_to_rgf.m, converts a set partition to a restricted growth function.
• stirling_numbers1.m, computes the Stirling numbers of the first kind.
• stirling_numbers2.m, computes the Stirling numbers of the second kind.
• subset_check.m, checks a subset.
• subset_colex_rank.m, computes the colexicographic rank of a subset.
• subset_colex_successor.m, computes the subset colexicographic successor.
• subset_colex_unrank.m, computes the subset of given colexicographic rank.
• subset_complement.m, computes the complement of a set.
• subset_dist.m, computes the Hamming distance between two sets.
• subset_enum.m, enumerates the subsets of a set with N elements.
• subset_intersect.m, computes the intersection of two sets.
• subset_lex_rank.m, computes the rank of a given lexicographic subset.
• subset_lex_successor.m, computes the lexicographic successor of a subset.
• subset_lex_unrank.m, computes the subset of a given lexicographic rank.
• subset_union.m, computes the union of two sets.
• subset_weight.m, computes the Hamming weight of a set.
• subset_xor.m, computes the symmetric difference of two sets.
• subsetsum_swap.m, seeks a solution of the subset sum problem by swapping.
• tableau_check.m, checks a 2 by N tableau.
• tableau_enum.m, enumerates the 2 by N standard tableaus.
• tableau_to_bal_seq.m, converts a 2 by N tableau to a balanced sequence.
• timestamp.m, prints the current YMDHMS date as a timestamp.
• tree_check.m, checks a tree.
• tree_enum.m, enumerates the trees on N nodes.
• tree_rank.m, ranks a tree.
• tree_successor.m, returns the successor of a tree.
• tree_to_pruefer.m, converts a tree to a Pruefer code.
• tree_unrank.m, unranks a tree.

Examples and Tests:

• combo_test.m, the calling program;
• combo_test_output.txt, the output file.
• combo_test01.m tests BAL_SEQ_ENUM, BAL_SEQ_RANK, BAL_SEQ_SUCCESSOR, BAL_SEQ_UNRANK.
• combo_test02.m tests BAL_SEQ_TO_TABLEAU and TABLEAU_TO_BAL_SEQ.
• combo_test03.m tests BELL_NUMBERS.
• combo_test04.m tests BINOMIAL.
• combo_test05.m tests CYCLE_TO_PERM, PERM_TO_CYCLE.
• combo_test06.m tests DIST_ENUM, DIST_NEXT.
• combo_test07.m tests I4_FACTORIAL and I4_FACTORIAL_VALUES.
• combo_test08.m tests GRAY_CODE_*.
• combo_test09.m tests I4VEC_SEARCH_BINARY_A and I4VEC_SORT_INSERT_A.
• combo_test10.m tests I4VEC_SEARCH_BINARY_D and I4VEC_SORT_INSERT_D.
• combo_test11.m tests KNAPSACK_REORDER and KNAPSACK_01.
• combo_test12.m tests KNAPSACK_REORDER and KNAPSACK_RATIONAL.
• combo_test13.m tests KSUBSET_COLEX_RANK, _SUCCESSOR, _UNRANK, _ENUM.
• combo_test14.m tests KSUBSET_ENUM, _LEX_RANK, _LEX_SUCCESSOR, _LEX_UNRANK.
• combo_test15.m tests KSUBSET_*.
• combo_test16.m tests MARRIAGE.
• combo_test17.m tests MOUNTAIN.
• combo_test18.m tests NPART_ENUM, _RSF_LEX_RANK, _RSF_LEX_SUCCESSOR, _RSF_LEX_UNRANK.
• combo_test19.m tests NPART_RSF_LEX_RANDOM;
• combo_test20.m tests NPART_ENUM and NPART_SF_SUCCESSOR;
• combo_test21.m tests NPART_TABLE and PART_TABLE.
• combo_test22.m tests PART_SUCCESSOR and PART_ENUM.
• combo_test23.m tests PART_SUCCESSOR and PART_SF_CONJUGATE.
• combo_test24.m tests PART_SF_MAJORIZE.
• combo_test25.m tests PARTITION_GREEDY.
• combo_test26.m tests PARTN_ENUM, PARTN_SUCCESSOR and PART_SF_CONJUGATE.
• combo_test27.m tests PERM_INV and PERM_MUL.
• combo_test28.m tests PERM_ENUM, PERM_LEX_RANK, PERM_LEX_SUCCESSOR, PERM_LEX_UNRANK.
• combo_test29.m tests PERM_ENUM, PERM_TJ_RANK, PERM_TJ_SUCCESSOR, PERM_TJ_UNRANK.
• combo_test30.m tests PRUEFER_*.
• combo_test31.m tests PRUEFER_TO_TREE and TREE_TO_PRUEFER.
• combo_test32.m tests QUEENS and BACKTRACK.
• combo_test33.m tests RGF_G_ENUM.
• combo_test34.m tests RGF_ENUM, RGF_RANK, RGF_SUCCESSOR, RGF_UNRANK.
• combo_test35.m tests RGF_TO_SETPART and SETPART_TO_RGF.
• combo_test36.m tests SETPART_ENUM.
• combo_test37.m tests STIRLING_NUMBERS1.
• combo_test38.m tests STIRLING_NUMBERS2.
• combo_test39.m tests SUBSET_COLEX_RANK, _COLEX_SUCCESSOR, _COLEX_UNRANK, _ENUM.
• combo_test40.m tests SUBSET_ENUM, _LEX_RANK, _LEX_SUCCESSOR, _LEX_UNRANK.
• combo_test41.m tests SUBSETSUM_SWAP.
• combo_test42.m tests TREE_ENUM, TREE_RANK, TREE_SUCCESSOR, TREE_UNRANK.

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