SUBSET Combinatorial Routines

SUBSET, a MATLAB library which enumerates, generates, randomizes, ranks and unranks combinatorial objects including combinations, compositions, Gray codes, index sets, partitions, permutations, polynomials, subsets, and Young tables. Backtracking routines are included to solve some combinatorial problems. Some routines for continued fractions are included.

Combinatorial operations include the enumeration, generation, random selection, ranking and unranking of

• COMP, compositions of an integer;
• COMPNZ, compositions of an integer with no zero parts;
• EQUIV's, partitions of a set of N objects;
• I4_PARTITION's, partitions of an integer;
• I4POLY's, integer polynomials in factorial, Newton, power sum, or Taylor form;
• I4VEC's, integer vectors;
• KSUB's, subsets of size K, from a set of N objects;
• MULTIPERM's, permutations of the N objects, some of which are indistinguishable.
• PERM's, permutations of the first N integers;
• R8POLY's, real polynomials in factorial, Newton, power sum, or Taylor form;
• subsets of a set of N objects;
• vectors whose entries range from 1 to N;
• YTB's, Young tables;

Other objects considered include

• the Bell numbers,
• Catalan numbers,
• congruence equations.
• continued fractions,
• DEC's, decimal numbers represented as a mantissa and a power of 10;
• DERANGE's, derangements (permutations that leave no element in place),
• DVEC's, decimal numbers represented as a vector of digits;
• falling factorials (20*19*18...),
• GRAY, Gray codes,
• matrix permanents (similar to determinants, but harder to compute, if you can believe that),
• Morse-Thue numbers,
• pentagonal numbers,
• Pythagorean triples,
• RAT's, rational numbers represented as a pair of integers;
• rising factorials (7*8*9...).

Languages:

SUBSET 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:

BACKTRACK_BINARY_RC, a MATLAB library which carries out a backtrack search for a set of binary decisions, using reverse communication.

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, a MATLAB library which contains many combinatorial routines.

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

Source Code:

Last revised on 23 March 2019.