combo

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

• BAL, balanced sequences, included nested parentheses, Dyck lattice paths, ballot paths;
• 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 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

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

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

matlab_combinatorics, a MATLAB code which considers a variety of problems in combinatorics involving counting, combinations, permutations, and so on.

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

polynomial, a MATLAB code which adds, multiplies, differentiates, evaluates and prints multivariate polynomials in a space of m dimensions.

polynomial_multiply, a MATLAB code which multiplies two polynomials p(x) and q(x).

set_theory, a MATLAB code which demonstrates MATLAB commands that implement various set theoretic operations.

subset, a MATLAB code which generates, ranks and unranks various combinatorial objects.

toms515, a MATLAB code 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 code 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_random.m, randomly selects a balanced sequence.
• 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_random.m, returns a random Gray code of 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_fall.m, evaluates the falling factorial function.
• i4_fall_values.m, returns some values of the falling factorial function.
• 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_random.m, returns a random K subset of an N set.
• 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.
• pivot_sequence_check.m, checks a pivot sequence.
• pivot_sequence_enum.m, enumerates pivot sequences.
• pivot_sequence_random.m, returns a random pivot sequence.
• pivot_sequence_successor.m, computes the pivot sequence successor.
• pruefer_check.m, checks a Pruefer code.
• pruefer_enum.m, enumerates the Pruefer codes on N-2 digits.
• pruefer_random.m, returns a random Pruefer code 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.
• 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_hamming.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.
• subset_sum_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.
• tree_check.m, checks a tree.
• tree_enum.m, enumerates the trees on N nodes.
• tree_random.m, randomly selects a tree 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.