SUBSET
Combinatorial Routines

SUBSET is a Python 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.

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

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 FORTRAN77 version and a FORTRAN90 version and a MATLAB version and a Python version.

Related Data and Programs:

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

POLYNOMIAL, a Python library which adds, multiplies, differentiates, evaluates and prints multivariate polynomials in a space of M dimensions.

Source Code:

• agm_values.py, returns selected values of the arithmetic geometric mean function.
• asm_enum.py, returns the number of alternating sign matrices of a given order.
• asm_triangle.py, returns a row of the alternating sign matrix triangle.
• bell.py, computes the Bell numbers.
• bell_values.py, returns some values of the Bell numbers.
• catalan.py, computes the Catalan numbers.
• catalan_row_next.py, returns the next row of the Catalan matrix.
• catalan_values.py, returns some values of the Catalan numbers.
• cfrac_to_rat.py, converts a continued fraction to a rational.
• change_greedy.py, makes change using a greedy algorithm.
• change_next.py, computes the next set of change for a given total.
• chinese_check.py, checks a set of Chinese remainder moduluses.
• chinese_to_i4.py, converts a set of Chinese remainders to an equivalent integer.
• comb_next.py, returns the next combination of K things out of N.
• comb_row.py, computes row N of Pascal's triangle.
• comb_unrank.py, returns the RANK-th combination of N things out of M things.
• comp_enum.py, enumerates the compositions of an integer into K parts.
• comp_next.py, returns the next composition of an integer into K parts.
• comp_next_grlex.py, returns the next composition of an integer into K parts, using grlex order.
• comp_random.py, returns a random composition of an integer into K parts.
• comp_random_grlex.py, returns a random composition of an integer into K parts, with the integer between 0 and N.
• comp_rank_grlex.py, ranks a composition of an integer into K parts, using grlex order.
• comp_to_ksub.py, returns the K-subset corresponding to a composition.
• comp_unrank_grlex.py, returns the composition of an integer into K parts of a given rank, using grlex order.
• compnz_enum.py, enumerates the compositions of an integer into K nonzero parts.
• compnz_next.py, returns the next composition of an integer into K nonzero parts.
• compnz_random.py, returns a random composition of an integer into K nonzero parts.
• compnz_to_ksub.py, returns the K-subset corresponding to a composition into K nonzero parts.
• congruence.py, solves a congruence of the form A * X = C (mod B).
• count_pose_random.py, poses a random problem for the game "The Count is Good".
• derange_enum.py, returns the number of derangements of N objects.
• derange_enum2.py, returns the number of derangements of 0 through N objects.
• derange_enum3.py, returns the number of derangements of N objects.
• digraph_arc_print.py, prints out a digraph from an edge list.
• dvec_add.py, adds two decimal vectors.
• dvec_complementx.py, returns the complement of a decimal vector.
• dvec_mul.py, multiplies two decimal vectors.
• dvec_print.py, prints a decimal vector.
• dvec_sub.py, subtracts two decimal vectors.
• dvec_to_i4.py, converts a (signed) decimal vector to an integer.
• equiv_print.py, prints a partition of a set.
• equiv_print2.py, prints a partition of a set using parentheses for grouping.
• equiv_random.py, returns a random partition of a set.
• euler.py, returns the N-th row of Euler's triangle.
• frobenius_number_order2.py, computes the Frobenius number for the order 2 case.
• frobenius_number_order2_values.py, returns some values of the Frobenius number for the order 2 case.
• gamma_values.py, returns selected values of the gamma function;
• gamma_log_values.py, returns some values of the logarithm of the Gamma function.
• gray_rank2.py, returns the rank of a given Gray code.
• gray_unrank2.py, returns the Gray code of a given rank.
• i4_choose.py, computes the binomial coefficient C(N,K).
• i4_factorial.py, computes the factorial function.
• i4_factorial_values.py, returns selected values of the factorial function.
• i4_fall.py, computes the falling factorial.
• i4_fall_values.py, returns selected values of the falling factorial.
• i4_gcd.py, finds the greatest common divisor of I and J.
• i4_huge.py, returns a "huge" I4.
• i4_log_10.py, returns the integer part of the logarithm of an I4.
• i4_modp.py, returns the nonnegative remainder of integer division.
• i4_partition_conj.py, computes the conjugate of a partition of an integer.
• i4_partition_count.py, returns the number of partitions of an integer.
• i4_partition_count2.py, returns the number of partitions of an integer.
• i4_partition_count_values.py, returns some values of the partition count function.
• i4_partition_print.py, prints a partition of an integer.
• i4_rise.py, computes the rising factorial.
• i4_rise_values.py, returns selected values of the rising factorial.
• i4_sign.py, returns the sign of an I4.
• i4_sqrt.py, returns the square root of an I4 with integer remainder.
• i4_sqrt_cf.py, finds the continued fraction square root of an integer.
• i4_to_chinese.py, converts an integer to its Chinese remainder form.
• i4_to_dvec.py, converts an integer to a (signed) decimal vector.
• i4_to_ipoly.m, converts an integer to an integer polynomial in a given base.
• i4_to_van_der_corput.py, computes an element of a van der Corput sequence.
• i4_uniform_ab.py, returns a random I4 in a given range.
• i4mat_mm.py, computes the product of two I4MAT's.
• i4mat_print.py, prints an I4MAT.
• i4mat_print_some.py, prints some of an I4MAT.
• i4mat_u1_inverse.py, computes the inverse of a unit upper triangular I4MAT.
• i4poly_add.py, adds two I4POLY's.
• i4poly_degree.py, returns the degree of an I4POLY.
• i4poly_dif.py, differentiates an I4POLY.
• i4poly_mul.py, multiplies two I4POLY's.
• i4poly_print.py, prints an I4POLY.
• i4poly_to_i4.py, converts an I4POLY to an I4.
• i4vec_ascends.py, is TRUE if an I4VEC is increasing.
• i4vec_descends.py, is TRUE if an I4VEC is decreasing.
• i4vec_frac.py, searches for the K-th smallest entry in an N vector.
• i4vec_index.py, returns the location of the first occurrence of a given value.
• i4vec_indicator0.py, sets an integer vector to the indicator0 vector.
• i4vec_indicator1.py, sets an integer vector to the indicator1 vector.
• i4vec_max_index_last.m, returns the index of the last maximal element of an I4VEC.
• i4vec_pairwise_prime.py, returns TRUE if the elements of an integer vector are pairwise prime.
• i4vec_print.py, prints an I4VEC.
• i4vec_product.py, computes the product of the entries of an I4VEC.
• i4vec_reverse.py, reverses the order of the entries of an I4VEC.
• i4vec_sort_bubble_a.py, ascending sorts an integer vector using bubble sort.
• i4vec_sort_heap_index_d.py, produces an index vector that descending sorts an integer array, using heapsort.
• i4vec_sum.py, sums the entries of an I4VEC.
• i4vec_transpose_print.py, prints the "transpose" of an integer vector.
• i4vec_uniform_ab.py, returns a random I4VEC with values between A and B.
• index_box_next_2d.py, produces index vectors on the surface of a box in 2D.
• index_box_next_3d.py, produces index vectors on the surface of a box in 3D.
• inverse_mod_n.py, computes the inverse of B mod N.
• involute_enum.py, returns the number of involutions of N objects.
• josephus.py, returns the position of the K-th man to be executed.
• ksub_random.py, selects a random subset of size K from a set of size N.
• ksub_random2.py, selects a random subset of size K from a set of size N.
• ksub_random3.py, selects a random subset of size K from a set of size N.
• ksub_random4.py, selects a random subset of size K from a set of size N.
• ksub_random5.py, selects a random subset of size K from a set of size N.
• ksub_rank.py, returns the rank of a subset of size K from a set of size N.
• ksub_to_comp.py, returns the composition corresponding to a given K-subset.
• ksub_to_compnz.py, returns the composition into K nonzero parts corresponding to a given K-subset.
• ksub_unrank.py, returns a subset of size K from a set of size N, of given rank.
• lvec_next.py, returns the next logical vector.
• moebius_values.py, returns values of the Moebius function.
• monomial_count.py, counts the number of monomials up to a given degree.
• monomial_counts.py, counts the number of monomials up to a given degree.
• multinomial_coef1.py, computes a multinomial coefficient.
• multinomial_coef2.py, computes a multinomial coefficient.
• multiperm_enum.py, enumerates multipermutations.
• nim_sum.py, computes the Nim sum of two integers.
• padovan.py, computes the Padovan numbers.
• pent_enum.py, computes the N-th pentagonal number.
• perm_fixed_enum.py, enumerates the permutations of N objects with M of them unchanged.
• perm_print.py, prints a permutation.
• perm0_check.py, checks a permutation of (0,...,N-1).
• perm0_lex_next.py, generates the next permutation of (0,...,N-1), in lexical order.
• perm0_random.py, returns a random permutation of (0,...,N-1).
• perm0_random2.py, returns a random permutation of (0,...,N-1).
• perm0_sign.py, returns the sign of a permutation of (0,...,N-1).
• perm1_check.py, checks a permutation of (1,...,N).
• perrin.py, computes the Perrin numbers.
• pord_check.py, checks a matrix representing a partial ordering.
• power_mod.py, computes mod ( A^N, M ).
• prime.py, returns a prime number from a stored table.
• pythag_triple_next.py, computes the next Pythagorean triple.
• r8_agm.py, computes the arithmetic geometric mean of two numbers;
• r8_choose.py, computes the binomial coefficient C(N,K).
• r8_fall.py, computes the falling factorial.
• r8_fall_values.py, returns selected values of the falling factorial.
• r8_gamma.py, evaluates the gamma function.
• r8_print.py, prints an R8.
• r8_rise.py, computes the rising factorial.
• r8_rise_values.py, returns selected values of the rising factorial.
• r8_to_dec.py, converts an R8 to a decimal value;
• r8_uniform_01.py, is a uniform random number generator.
• r8_uniform_ab.py, returns a random real in a given range.
• r8mat_print.py, prints an R8MAT.
• r8mat_print_some.py, prints some of an R8MAT.
• r8poly_add.py, adds two R8POLY's.
• r8poly_degree.py, returns the degree of an R8POLY.
• r8poly_dif.py, differentiates an R8POLY.
• r8poly_div.py, computes the quotient and remainder of two R8POLY's.
• r8poly_mul.py, computes the product of two R8POLY's.
• r8poly_print.py, prints an R8POLY.
• r8vec_frac.py, searches for the K-th smallest entry in an N vector.
• r8vec_indicator.py, sets a real vector to the indicator vector.
• r8vec_mirror_next.py, steps through all sign variations of a real vector.
• r8vec_print.py, prints a real vector.
• r8vec_uniform_01.py, returns a unit pseudorandom R8VEC.
• r8vec_uniform_ab.py, returns a scaled pseudorandom R8VEC.
• rat_to_cfrac.py, converts a rational to a continued fraction.
• regro_next.py, computes the next restricted growth function.
• schroeder.py, generates the Schroeder numbers.
• subset_gray_rank.py, ranks a subset of an N set using the Gray ordering.
• subset_gray_unrank.py, returns a subset of an N set with the given Gray ranking.
• subset_lex_next.py, returns the next subset of an N set, in lexicographic order.
• subset_random.py, selects a random subset of an N set.
• subtriangle_next.py, returns the next subtriangle in a triangle whose edges have each been subdivided into N parts.
• thue_binary_next.py, returns the next element in a binary Thue sequence.
• thue_ternary_next.py, returns the next element in a ternary Thue sequence.
• timestamp.py, returns the current YMDHMS date as a timestamp.
• tuple_next.py, computes the next element of a tuple space.
• tuple2_next.py, computes the next element of a tuple space.
• tuple_next_ge.py, computes the next "nondecreasing" element of a tuple space.
• ubvec_add.py, adds two unsigned binary vectors.
• ubvec_print.py, prints an unsigned binary vector.
• ubvec_to_ui4.py, converts an unsigned binary vector to an unsigned integer.
• ubvec_xor.py, computes the exclusive OR of two unsigned binary vectors.
• ui4_to_ubvec.py, converts an integer to an unsigned binary vector.
• vec_colex_next.py, generates vectors in colex order.
• vec_colex_next2.py, generates vectors in colex order.
• vec_colex_next3.py, generates vectors in colex order.
• vec_gray_next.py, generates the elements of a product space.
• vec_gray_rank.py, returns the rank of an N-vectors of integers modulo a given base.
• vec_gray_unrank.py, computes the product space element of a given rank.
• vec_lex_next.py, generates all N-vectors of integers modulo a given base.
• vec_random.py, selects a random N-vectors of integers modulo a given base.
• vector_constrained_next.py, computes the "next" vector that lies in a given range and satisfies a particular constraint.
• vector_constrained_next2.py, computes the "next" vector that lies in a given range and satisfies a particular constraint.
• vector_constrained_next3.py, computes the "next" vector that lies in a given range and satisfies a particular constraint.
• vector_next.py, returns the "next" integer vector between two ranges.
• ytb_enum.py, enumerates the Young tableaus of size N.
• ytb_next.py, returns the next Young tableau of size N.
• ytb_print.py, prints a Young tableau.
• ytb_random.py, returns a random Young tableau.

Not converted yet:

• cfrac_to_rfrac.py, converts a continued polynomial fraction to a rational polynomial fraction.
• debruijn.py, constructs a de Bruijn string.
• dec_add.py, adds two decimal values.
• dec_div.py, divides two decimal values.
• dec_mul.py, multiplies two decimal values.
• dec_round.py, rounds a decimal value to a given number of digits.
• dec_to_r8.py, converts a decimal to a real value.
• dec_to_rat.py, converts a decimal to a rational value.
• dec_to_s.py, returns a string representation of a decimal.
• dec_width.py, returns the "width" of a decimal.
• decmat_det.py, computes the determinant of a decimal matrix.
• decmat_print.py, prints a decimal matrix.
• derange_back_candidate.py, finds possible values for the K-th entry of a derangement.
• derange_back_next.py, returns the next derangement of N items.
• derange_check.py, checks whether a permutation is a derangement.
• derange_weed_next.py, returns next derangements of N objects.
• digraph_arc_euler.py, returns an Euler circuit in a directed graph.
• diophantine.py, solves a Diophantine equation A * X + B * Y = C.
• diophantine_solution_minimize.py, seeks a minimal solution of a Diophantine equation.
• equiv_next.py, returns the next partition of a set.
• equiv_next2.py, returns the next partition of a set.
• gray_next.py, returns the next Gray code by switching one item at a time.
• i4_bclr.py, sets a given bit of an I4 to 0.
• i4_bset.py, sets a given bit of an I4 to 1.
• i4_btest.py, returns TRUE if bit POS of I is a 1.
• i4_factor.py, factors an I4 into a product of primes.
• i4_moebius.py, evaluates the Moebius function.
• i4_partition_next.py, computes the next partition of an integer.
• i4_partition_next2.py, computes the next partition of an integer.
• i4_partition_random.py, returns a random partition of an integer.
• i4_partitions_next.py, returns the next partition of an integer, and when there are no more, it increases the integer and continues.
• i4mat_01_rowcolsum.py, creates a 0/1 matrix with given row and column sums.
• i4mat_perm.py, applies a permutation to the rows and columns of a square I4MAT.
• i4mat_perm2.py, applies permutations to the rows and columns of a rectangular I4MAT.
• i4poly.py, performs operations on an I4POLY.
• i4poly_cyclo.py, computes a cyclotomic polynomial.
• i4poly_div.py, divides one I4POLY by another.
• i4vec_backtrack.py, supervises a backtrack search for an I4VEC.
• index_box2_next_2d.py, produces index vectors on the surface of a box in 2D.
• index_box2_next_3d.py, produces index vectors on the surface of a box in 3D.
• index_next0.py, generates all index vectors with given upper limits.
• index_next1.py, generates all index vectors with given upper limits.
• index_next2.py, generates all index vectors with given lower and upper limits.
• index_rank0.py, ranks an index vector with given upper limits.
• index_rank1.py, ranks an index vector with given upper limits.
• index_rank2.py, ranks an index vector with given lower and upper limits.
• index_unrank0.py, unranks an index vector with given upper limits.
• index_unrank1.py, unranks an index vector with given upper limits.
• index_unrank2.py, unranks an index vector with given upper and lower limits.
• ins_perm.py, computes a permutation from its inversion sequence.
• jfrac_to_rfrac.py, converts a J-fraction to a rational polynomial fraction.
• ksub_next.py, selects the next subset of size K from a set of size N.
• ksub_next2.py, selects the next subset of size K from a set of size N.
• ksub_next3.py, selects the next subset of size K from a set of size N.
• ksub_next4.py, selects the next subset of size K from a set of size N.
• matrix_product_opt.py, determines the optimal cost of a matrix product.
• moebius_matrix.py, finds the Moebius matrix from a covering relation.
• morse_thue.py, generates a Morse-Thue number.
• multiperm_next.py, computes the next multipermutation.
• pell_basic.py, returns the basic solution of Pell's equation.
• pell_next.py, returns the next solution of Pell's equation.
• perm_ascend.py, returns the longest ascending subsequence of a permutation.
• perm_canon_to_cycle.py, converts a permutation from canonical to cycle form.
• perm_cycle.py, analyzes a permutation.
• perm_cycle_to_canon.py, converts a permutation from cycle to canonical format.
• perm_cycle_to_index.py, converts a permutation from cycle to standard index format.
• perm_distance.py, computes the Ulam metric distance of two permutations.
• perm_free.py, reports the unused items in a partial permutation.
• perm_index_to_cycle.py, converts a permutation from standard index to cycle form.
• perm_ins.py, returns the inversion sequence of a permutation.
• perm_inverse.py, inverts a permutation.
• perm_inverse2.py, inverts a permutation.
• perm_inverse3.py, inverts a permutation.
• perm_mul.py, multiplies two permutations.
• perm_next.py, computes the next permutation of N objects.
• perm_next2.py, computes the next permutation of N objects.
• perm_next3.py, computes the next permutation of N objects.
• perm_rank.py, returns the rank of a permutation.
• perm_to_equiv.py, converts a permutation to an equivalence relation.
• perm_to_ytb.py, converts a permutation to a Young tableau.
• perm_unrank.py, produces the permutation of given rank.
• power_series1.py, computes the power series for (1+F(Z))^ALPHA.
• power_series2.py, computes the power series for exp(F(Z))-1.
• power_series3.py, computes the power series for G(F(Z)).
• power_series4.py, computes the power series for G(1/F(Z)).
• r8_to_cfrac.py, converts an R8value to a continued fraction.
• r8_to_rat.py, converts an R8 to a rational value.
• r8mat_det.py, computes the determinant of a real array.
• r8mat_perm.py, applies a permutation to the rows and columns of a square matrix.
• r8mat_perm2.py, applies a permutation to the rows and columns of a rectangular matrix.
• r8mat_permanent.py, computes the permanent of a square matrix.
• r8poly.py, performs operations on an R8POLY.
• r8poly_f2p.py, converts an R8POLY from factorial to standard form.
• r8poly_fval.py, evaluates an R8POLY in factorial form.
• r8poly_n2p.py, converts an R8POLY from Newton to standard form.
• r8poly_nval.py, evaluates an R8POLY in Newton form.
• r8poly_nx.py, replaces one of the base points in the Newton form of a polynomial.
• r8poly_p2f.py, converts an R8POLY from standard to factorial form.
• r8poly_p2n.py, converts an R8POLY from standard to Newton form.
• r8poly_p2t.py, converts an R8POLY from standard to Taylor form.
• r8poly_power.py, computes a power of an R8POLY.
• r8poly_pval.py, evaluates an R8POLY.
• r8poly_t2p.py, converts an R8POLY from Taylor to standard form.
• r8vec_backtrack.py, supervises a backtrack search for a real vector.
• rat_add.py, adds two rational values.
• rat_div.py, carries out division of rational values.
• rat_farey.py, returns a row of the Farey fraction table.
• rat_farey2.py, returns the next row of the Farey fraction table.
• rat_mul.py, multiplies two rational values.
• rat_normalize.py, normalizes a rational value.
• rat_sum_formula.py, computes the formulas for sums of powers of integers.
• rat_to_dec.py, converts a rational to a decimal value.
• rat_to_r8.py, converts a rational to a real value.
• rat_to_s_left.py, converts a rational to a left-justified string.
• rat_width.py, returns the "width" of a rational number.
• ratmat_det.py, computes the determinant of a rational matrix.
• ratmat_print.py, prints a rational matrix.
• rfrac_to_cfrac.py, converts a rational polynomial fraction to continued fraction form.
• rfrac_to_jfrac.py, converts a rational polynomial fraction to a J fraction.
• sort_heap_external.py, externally sorts a list of items into ascending order.
• subcomp_next.py, computes the next subcomposition of N into K parts;
• subcompnz_next.py, computes the next subcomposition of N into K nonzero parts;
• subcompnz2_next.py, computes the next composition of N into K nonzero parts for N between N_LO and N_HI;
• subset_by_size_next.py, returns all the subsets of an N set, in decreasing order of size.
• subset_gray_next.py, generates the next subset of an N set.
• triang.py, renumbers items in accordance with a partial ordering.
• tuple_next_fast.py, computes the next element of a tuple space, "fast".
• vector_constrained_next4.py, computes the "next" vector that lies in a given range and satisfies a particular constraint.
• vector_constrained_next5.py, computes the "next" vector that lies in a given range and satisfies a particular constraint.
• vector_constrained_next6.py, computes the "next" vector that lies in a given range and satisfies a particular constraint.
• vector_constrained_next7.py, returns the "next" vector that lies in a given range and satisfies a particular constraint.

Examples and Tests:

• subset_test.py, calls all the tests;
• subset_test.sh, runs all the tests;
• subset_test_output.txt, the output file;

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