COMBO - Kreher and Stinson Combinatorial Routines

COMBO is a collection of combinatorial routines, as described in the recent book "Combinatorial Algorithms" by Kreher and Stinson. Routines are available to count, list, rank and unrank such objects as balanced sequences, trees, subsets, K subsets, partitions, restricted growth functions, and permutations.

Reference 1:

Donald Kreher and Douglas Simpson,
Combinatorial Algorithms,
CRC Press, 1998.

Reference 2:

A Nijenhuis and H Wilf,
Combinatorial Algorithms,
Academic Press, 1978, second edition,
ISBN 0-12-519260-6.

Files you may copy include:

• combo.f90, the source code;
• combo_prb.f90, the calling program;
• combo_prb.out, the sample output.

The list of routines includes:

• 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_NEX 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.
• GAMMA_LOG calculates the natural logarithm of GAMMA ( X ) for positive X.
• 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.
• I_FACTORIAL computes the factorial N!
• I_FACTORIAL_VALUES returns values of the factorial function for testing.
• I_SWAP switches two integer values.
• IVEC_BACKTRACK supervises a backtrack search for an integer vector.
• IVEC_IDENTITY sets an integer vector to the identity vector A(I)=I.
• IVEC_PART1 partitions an integer N into NPART parts.
• IVEC_PART2 partitions an integer N into NPART nearly equal parts.
• IVEC_PRINT prints an integer vector.
• IVEC_REVERSE reverses the elements of an integer vector.
• IVEC_SEARCH_BINARY_A searches the ascending sorted vector A for the value B.
• IVEC_SEARCH_BINARY_D searches the descending sorted vector A for the value B.
• IVEC_SORT_INSERT_A uses an ascending insertion sort on an integer vector.
• IVEC_SORT_INSERT_D uses a descending insertion sort on an integer vector.
• 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_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.
• R_SWAP swaps two real values.
• 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.
• RVEC_BACKTRACK supervises a backtrack search for a real vector.
• 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_TO_PRUEFER converts a tree to a Pruefer code.

Return to the FORTRAN software page.