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

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

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.

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,
ISBN: 0-12-519260-6,
LC: QA164.N54.
12. Robert Sedgewick,
Algorithms in C,
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.

### Examples and Tests:

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

Last revised on 26 January 2011. <%-- John Burkardt -->