COMBO
Kreher and Stinson Combinatorial Routines

COMBO is a MATLAB 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 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 FORTRAN90 version and a MATLAB version and a Python version.

Related Data and Programs:

CHANGE_MAKING, a MATLAB library which considers the change making problem, in which a given sum is to be formed using coins of various denominations.

COMBINATION_LOCK, a MATLAB program which simulates the process of determining the secret combination of a lock.

combo_test

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

GRAY_CODE_DISPLAY, a MATLAB program which computes the Hamming distance tables for both the binary and Gray codes, and displays 3D plots that illustrate how the Gray code does a better job of providing nearby representations for nearby numbers.

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

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

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

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.

TOMS515, a MATLAB library which can select subsets of size K from a set of size N. This is a version of ACM TOMS Algorithm 515, by Bill Buckles, Matthew Lybanon.

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

Reference:

1. Donald Kreher, Douglas Simpson,
   Combinatorial Algorithms,
   CRC Press, 1998,
   ISBN: 0-8493-3988-X,
   LC: QA164.K73.

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.
• 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.
• gamma_log_values.m, returns selected values of the logarithm of the Gamma 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_choose.m, computes the binomial coefficient C(N,K).
• i4_factorial.m, computes the factorial function.
• i4_factorial_values.m, returns some values of the factorial function.
• i4_fall.m, evaluates the falling factorial function.
• i4_fall_values.m, returns some values of the falling factorial function.
• i4_huge.m, returns a huge I4;
• i4_uniform_ab.m, returns a pseudorandom I4 in a given range;
• i4mat_print.m, prints an I4MAT;
• i4mat_print_some.m, prints some of an I4MAT;
• i4vec_backtrack.m, supervises a backtrack search for an I4VEC.
• i4vec_dot_product.m, computes the dot product of two I4VEC's.
• i4vec_indicator1.m, sets an I4VEC to the indicator1 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.
• i4vec_transpose_print.m, prints an I4VEC "transposed";
• i4vec_uniform_ab.m, fills an I4VEC with uniform random integers between A and B.
• 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_random.m, returns a random 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_choose.m, computes the binomial coefficient C(N,K).
• 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_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.
• rgf_g_table.m, tabulates the restricted growth functions.
• 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_distance.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_random.m, returns a random subset of an N set.
• 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.