subset

subset, a Python code 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. Other routines handle continued fractions, Diophantine equations, and Pythagorean triples.

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,
• primitive Pythagorean triples: relatively prime integers such that a^2 + b^2 = c^2
• RAT's, rational numbers represented as a pair of integers;
• rising factorials (7*8*9...).

Licensing:

The computer code and data files described and made available on this web page are distributed under the GNU LGPL license.

Languages:

subset is available in a C version and a C++ version and a Fortran90 version and a MATLAB version and an Octave version and a Python version.

Related Data and Programs:

change_diophantine, a Python code which sets up a Diophantine equation to solve the change making problem, which counts the number of ways a given sum can be formed using coins of various denominations.

combo, a Python code 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.

knapsack_01, a Python code which uses brute force to solve small versions of the 0/1 knapsack problem;

mcnuggets, a Python code which counts M(N), the number of ways a given number N of Chicken McNuggets can be assembled, given that they are only available in packages of 6, 9, and 20.

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

partition_brute, a Python code which uses a brute force method to find solutions of the partition problem, in which a set of integers must be split into two subsets with equal sum.

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

satisfy_brute, a Python code which uses brute force to find all assignments of values to a set of logical variables which make a complicated logical statement true.

subset_sum, a Python code which seeks solutions of the subset sum problem, in which it is desired to find a subset of a set of integers which has a given sum.

toms515, a Python 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.

ubvec, a Python code which demonstrates how unsigned binary vectors, strings of 0's and 1's, can represent nonnegative integers or subsets or other mathematical objects, for which various arithmetic and logical operations can be defined.

unicycle, a Python code which considers permutations containing a single cycle, sometimes called cyclic permutations.

Source Code:

• subset.py, the source code;
• subset.sh, runs all the tests;
• subset.txt, the output file;