subset

subset, an Octave 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 information on this web page is distributed under the MIT 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 an Octave version and a Python version.

Related Data and Programs:

subset_test

backtrack_binary_rc, an Octave code which carries out a backtrack search for a set of binary decisions, using reverse communication.

combination_lock, an Octave code which simulates the process of determining the secret combination of a lock.

combo, an Octave code which contains many combinatorial routines.

gray_code_display, an Octave code 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, an Octave 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.

octave_combinatorics, an Octave code which considers a variety of problems in combinatorics involving counting, combinations, permutations, and so on.

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

polynomial_multiply, an Octave code which multiplies two polynomials p(x) and q(x).

set_theory, an Octave code which demonstrates MATLAB commands that implement various set theoretic operations.

subset_sum, an Octave code which seeks solutions of the subset sum problem.

toms515, an Octave 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.

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

Source Code:

• asm_enum.m, returns the number of alternating sign matrices of a given order.
• asm_triangle.m, returns a row of the alternating sign matrix triangle.
• bell.m, computes the Bell numbers.
• bell_values.m, returns some values of the Bell numbers.
• boolean_to_string.m, returns "True" or "False", given a boolean value.
• catalan_number.m, computes a Catalan number.
• catalan_numbers.m, computes the Catalan numbers.
• catalan_row_next.m, returns the next row of the Catalan matrix.
• catalan_values.m, returns some values of the Catalan numbers.
• cfrac_to_rat.m, converts a continued fraction to a rational.
• cfrac_to_rfrac.m, converts a continued polynomial fraction to a rational polynomial fraction.
• ch_to_digit.m converts a character to a digit;
• change_greedy.m, makes change using a greedy algorithm.
• change_next.m, computes the next set of change for a given total.
• chinese_check.m, checks a set of Chinese remainder moduluses.
• chinese_to_i4.m, converts a set of Chinese remainders to an equivalent integer.
• comb_next.m, returns the next combination of K things out of N.
• comb_row_next.m, computes the next row of Pascal's triangle.
• comb_unrank.m, returns the RANK-th combination of N things out of M things.
• comp_enum.m, enumerates the compositions of an integer into K parts.
• comp_next.m, returns the next composition of an integer into K parts.
• comp_random.m, returns a random composition of an integer into K parts.
• comp_next_grlex.m, returns the next composition of an integer into K parts, using grlex order.
• comp_random_grlex.m, returns a random composition of an integer into K parts, with the integer between 0 and N.
• comp_rank_grlex.m, ranks a composition of an integer into K parts, using grlex order.
• comp_unrank_grlex.m, returns the composition of an integer into K parts of a given rank, using grlex order.
• comp_to_ksub.m, returns the K-subset corresponding to a composition.
• compnz_enum.m, enumerates the compositions of an integer into K nonzero parts.
• compnz_next.m, returns the next composition of an integer into K nonzero parts.
• compnz_random.m, returns a random composition of an integer into K nonzero parts.
• compnz_to_ksub.m, returns the K-subset corresponding to a composition into K nonzero parts.
• congruence.m, solves a congruence of the form A * X = C (mod B).
• count_pose_random.m, poses a random problem for the game "The Count is Good".
• debruijn.m, constructs a de Bruijn string.
• dec_add.m, adds two decimal values.
• dec_div.m, divides two decimal values.
• dec_mul.m, multiplies two decimal values.
• dec_round.m, rounds a decimal value to a given number of digits.
• dec_to_r8.m, converts a decimal to a real value.
• dec_to_rat.m, converts a decimal to a rational value.
• dec_to_s.m, returns a string representation of a decimal.
• dec_width.m, returns the "width" of a decimal.
• decmat_det.m, computes the determinant of a decimal matrix.
• decmat_print.m, prints a decimal matrix.
• derange_enum.m, returns the number of derangements of N objects.
• derange_enum2.m, returns the number of derangements of 0 through N objects.
• derange_enum3.m, returns the number of derangements of N objects.
• derange1_back_candidate.m, finds possible values for the K-th entry of a derangement.
• derange1_back_next.m, returns the next derangement of N items.
• derange1_check.m, checks whether a permutation of (1,...,N) is a derangement.
• derange1_weed_next.m, returns next derangements of (1,...,N).
• digit_to_ch.m, converts a digit to a character;
• digraph_arc_euler.m, returns an Euler circuit in a directed graph.
• digraph_arc_print.m, prints out a digraph from an edge list.
• diophantine.m, solves a Diophantine equation A * X + B * Y = C.
• diophantine_solution_minimize.m, seeks a minimal solution of a Diophantine equation.
• dvec_add.m, adds two decimal vectors.
• dvec_complementx.m, returns the complement of a decimal vector.
• dvec_mul.m, multiplies two decimal vectors.
• dvec_print.m, prints a decimal vector.
• dvec_sub.m, subtracts two decimal vectors.
• dvec_to_i4.m, converts a (signed) decimal vector to an integer.
• equiv_next.m, returns the next partition of a set.
• equiv_next2.m, returns the next partition of a set.
• equiv_print.m, prints a partition of a set.
• equiv_print2.m, prints a partition of a set using parentheses for grouping.
• equiv_random.m, returns a random partition of a set.
• euler_row.m, returns the N-th row of Euler's triangle.
• frobenius_number_order2.m, computes the Frobenius number for the order 2 case.
• frobenius_number_order2_values.m, returns some values of the Frobenius number for the order 2 case.
• gamma_log_values.m, returns some values of the logarithm of the Gamma function.
• gray_next.m, returns the next Gray code by switching one item at a time.
• gray_rank2.m, returns the rank of a given Gray code.
• gray_unrank2.m, returns the Gray code of a given rank.
• i4_bclr.m, sets a given bit of an I4 to 0.
• i4_bset.m, sets a given bit of an I4 to 1.
• i4_btest.m, returns TRUE if bit POS of I is a 1.
• i4_factor.m, factors an I4 into a product of primes.
• i4_fall.m, computes the falling factorial.
• i4_fall_values.m, returns selected values of the falling factorial.
• i4_gpf.m, computes the greatest prime factor of an integer.
• i4_gpf_values.m, returns selected values of the greatest prime factor of an integer.
• i4_log_10.m, returns the integer part of the logarithm of an I4.
• i4_modp.m, returns the nonnegative remainder of integer division.
• i4_moebius.m, evaluates the Moebius function.
• i4_partition_conj.m, computes the conjugate of a partition of an integer.
• i4_partition_count.m, returns the number of partitions of an integer.
• i4_partition_count2.m, returns the number of partitions of an integer.
• i4_partition_count_values.m, returns some values of the partition count function.
• i4_partition_next.m, computes the next partition of an integer.
• i4_partition_next2.m, computes the next partition of an integer.
• i4_partition_print.m, prints a partition of an integer.
• i4_partition_random.m, returns a random partition of an integer.
• i4_partitions_next.m, returns the next partition of an integer, and when there are no more, it increases the integer and continues.
• i4_rise.m, computes the rising factorial.
• i4_rise_values.m, returns selected values of the rising factorial.
• i4_sign.m, returns the sign of an I4.
• i4_sqrt.m, finds the integer square root of an I4.
• i4_sqrt_cf.m, finds the continued fraction square root of an integer.
• i4_to_chinese.m, converts an integer to its Chinese remainder form.
• i4_to_dvec.m, 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.
• i4mat_01_rowcolsum.m, creates a 0/1 matrix with given row and column sums.
• i4mat_perm1.m, applies a permutation to the rows and columns of a square I4MAT.
• i4mat_2perm1.m, applies permutations to the rows and columns of a rectangular I4MAT.
• i4mat_print.m, prints an I4MAT.
• i4mat_print_some.m, prints some of an I4MAT.
• i4mat_u1_inverse.m, computes the inverse of a unit upper triangular integer matrix.
• i4poly.m, performs operations on an I4POLY.
• i4poly_add.m, adds two I4POLY's.
• i4poly_cyclo.m, computes a cyclotomic polynomial.
• i4poly_degree.m, returns the degree of an I4POLY.
• i4poly_dif.m, differentiates an I4POLY.
• i4poly_div.m, divides one I4POLY by another.
• i4poly_mul.m, multiplies two I4POLY's.
• i4poly_print.m, prints an I4POLY.
• i4poly_to_i4.m, converts an I4POLY to an I4.
• i4vec_backtrack.m, supervises a backtrack search for an I4VEC.
• i4vec_frac.m, searches for the K-th smallest entry in an I4VEC.
• i4vec_index.m, returns the location of the first occurrence of a given value in an I4VEC.
• i4vec_indicator0.m, sets an I4VEC to the indicator vector.
• i4vec_indicator1.m, sets an I4VEC to the indicator vector.
• i4vec_is_ascending.m, is TRUE if an I4VEC is increasing.
• i4vec_is_descending.m, is TRUE if an I4VEC is decreasing.
• i4vec_max_index_last.m, returns the index of the last maximal element of an I4VEC.
• i4vec_pairwise_prime.m, returns TRUE if the elements of an I4VEC are pairwise prime.
• i4vec_print.m, prints an I4VEC.
• i4vec_reverse.m, reverses the elements of an I4VEC.
• i4vec_sort_bubble_a.m, ascending sorts an I4VEC using bubble sort.
• i4vec_sort_heap_index_d.m, produces an index vector that descending sorts an integer array, using heapsort.
• i4vec_transpose_print.m, prints the "transpose" of an integer vector.
• index_box_next_2d.m, produces index vectors on the surface of a box in 2D.
• index_box_next_3d.m, produces index vectors on the surface of a box in 3D.
• index_box2_next_2d.m, produces index vectors on the surface of a box in 2D.
• index_box2_next_3d.m, produces index vectors on the surface of a box in 3D.
• index_next0.m, generates all index vectors with given upper limits.
• index_next1.m, generates all index vectors with given upper limits.
• index_next2.m, generates all index vectors with given lower and upper limits.
• index_rank0.m, ranks an index vector with given upper limits.
• index_rank1.m, ranks an index vector with given upper limits.
• index_rank2.m, ranks an index vector with given lower and upper limits.
• index_unrank0.m, unranks an index vector with given upper limits.
• index_unrank1.m, unranks an index vector with given upper limits.
• index_unrank2.m, unranks an index vector with given upper and lower limits.
• inverse_mod_n.m, computes the inverse of B mod N.
• inversion_to_perm1.m, computes a permutation of (1,...,N) from its inversion sequence.
• involute_enum.m, returns the number of involutions of N objects.
• jfrac_to_rfrac.m, converts a J-fraction to a rational polynomial fraction.
• josephus.m, returns the position of the K-th man to be executed.
• ksub_next.m, selects the next subset of size K from a set of size N.
• ksub_next2.m, selects the next subset of size K from a set of size N.
• ksub_next3.m, selects the next subset of size K from a set of size N.
• ksub_next4.m, selects the next subset of size K from a set of size N.
• ksub_random.m, selects a random subset of size K from a set of size N.
• ksub_random2.m, selects a random subset of size K from a set of size N.
• ksub_random3.m, selects a random subset of size K from a set of size N.
• ksub_random4.m, selects a random subset of size K from a set of size N.
• ksub_random5.m, selects a random subset of size K from a set of size N.
• ksub_rank.m, returns the rank of a subset of size K from a set of size N.
• ksub_to_comp.m, returns the composition corresponding to a given K-subset.
• ksub_to_compnz.m, returns the composition into K nonzero parts corresponding to a given K-subset.
• ksub_unrank.m, returns a subset of size K from a set of size N, of given rank.
• l4vec_next.m, returns the next logical vector.
• matrix_product_opt.m, determines the optimal cost of a matrix product.
• moebius_matrix.m, finds the Moebius matrix from a covering relation.
• moebius_values.m, returns selected values of the Moebius function.
• monomial_count.m, counts the number of monomials up to a given degree.
• monomial_counts.m, counts the number of monomials up to a given degree.
• morse_thue.m, generates a Morse-Thue number.
• multinomial_coef1.m, computes a multinomial coefficient.
• multinomial_coef2.m, computes a multinomial coefficient.
• multiperm_enum.m, enumerates multipermutations.
• multiperm_next.m, computes the next multipermutation.
• nim_sum.m, computes the Nim sum of two integers.
• padovan.m, computes the Padovan numbers.
• pell_basic.m, returns the basic solution of Pell's equation.
• pell_next.m, returns the next solution of Pell's equation.
• pell_number.m, returns the Pell number of index N.
• pent_enum.m, computes the N-th pentagonal number.
• perm_ascend.m, returns the longest ascending subsequence of a permutation.
• perm_fixed_enum.m, enumerates the permutations of N objects with M of them unchanged.
• perm0_check.m, checks a permutation of (0,...,N-1);
• perm0_lex_next.m, generates the next permutation of (0,...,N-1), in lexical order.
• perm0_print.m, prints a permutation of (0,...,N-1).
• perm1_break_count.m counts breaks in a permutation of (1,...,N).
• perm1_canon_to_cycle.m, converts a permutation of (1,...,N) from canonical to cycle form.
• perm1_check.m, checks a permutation of (1,...,N);
• perm1_cycle.m, analyzes a permutation of (1,...,N).
• perm1_cycle_max.m, returns the length of a longest cycle in a permutation of (1,...,N).
• perm1_cycle_stats.m, returns the lengths of the cycles in a permutation of (1,...,N).
• perm1_cycle_to_canon.m, converts a permutation of (1,...,N) from cycle to canonical format.
• perm1_cycle_to_index.m, converts a permutation of (1,...,N) from cycle to standard index format.
• perm1_distance.m, computes the distance of two permutations of (1,...,N).
• perm1_free.m, reports the unused items in a partial permutation of (1,...,N).
• perm1_index_to_cycle.m, converts a permutation of (1,...,N) from standard index to cycle form.
• perm1_inverse.m, inverts a permutation of (1,...,N).
• perm1_inverse2.m, inverts a permutation of (1,...,N).
• perm1_inverse3.m, inverts a permutation of (1,...,N).
• perm1_lex_next.m, generates the next permutation of (1,...,N) in lexical order.
• perm1_mul.m, multiplies two permutations of (1,...,N).
• perm1_next.m, computes the next permutation of (1,...,N).
• perm1_next2.m, computes the next permutation of (1,...,N).
• perm1_next3.m, computes the next permutation of (1,...,N).
• perm1_print.m, prints a permutation.
• perm1_random.m, returns a random permutation of (1,...,N).
• perm1_random2.m, returns a random permutation of (1,...,N).
• perm1_rank.m, ranks a permutation of (1,...,N).
• perm1_sign.m, returns the sign of a permutation of (1,...,N).
• perm1_to_equiv.m, converts a permutation of (1,...,N) to an equivalence relation.
• perm1_to_inversion.m, returns the inversion sequence of a permutation of (1,...,N).
• perm1_to_ytb.m, converts a permutation of (1,...,N) to a Young tableau.
• perm1_unrank.m, unranks a permutation of (1,..,N).
• perrin.m, computes the Perrin numbers.
• pord_check.m, checks a matrix representing a partial ordering.
• power_mod.m, computes mod ( A^N, M ).
• power_series1.m, computes the power series for (1+F(Z))^ALPHA.
• power_series2.m, computes the power series for exp(F(Z))-1.
• power_series3.m, computes the power series for G(F(Z)).
• power_series4.m, computes the power series for G(1/F(Z)).
• prime.m, returns any of the first MAXPRIME prime numbers.
• pythag_triple_ijk.m, computes a Pythagorean triple from (i,j,k) coordinates.
• pythag_triple_next.m, computes the next Pythagorean triple.
• r8_agm.m, finds the arithmetic-geometric mean of two real numbers.
• r8_fall.m, computes the falling factorial.
• r8_fall_values.m, returns selected values of the falling factorial function.
• r8_rise.m, computes the rising factorial.
• r8_rise_values.m, returns selected values of the rising factorial function.
• r8_to_cfrac.m, converts an R8 to a continued fraction.
• r8_to_dec.m, converts an R8 to a decimal value;
• r8_to_rat.m, converts an R8 to a rational value.
• r8mat_det.m, computes the determinant of a real array.
• r8mat_perm1.m, applies a permutation to the rows and columns of a square matrix.
• r8mat_2perm1.m, applies a permutation to the rows and columns of a rectangular matrix.
• r8mat_permanent.m, computes the permanent of a square matrix.
• r8mat_print.m, prints a real matrix.
• r8mat_print_some.m, prints some of an R8MAT.
• r8poly.m, performs operations on an R8POLY.
• r8poly_f2p.m, converts an R8POLY from factorial to standard form.
• r8poly_fval.m, evaluates an R8POLY in factorial form.
• r8poly_n2p.m, converts an R8POLY from Newton to standard form.
• r8poly_nval.m, evaluates an R8POLY in Newton form.
• r8poly_nx.m, replaces one of the base points in the Newton form of a polynomial.
• r8poly_p2f.m, converts an R8POLY from standard to factorial form.
• r8poly_p2n.m, converts an R8POLY from standard to Newton form.
• r8poly_p2t.m, converts an R8POLY from standard to Taylor form.
• r8poly_print.m, prints an R8POLY.
• r8poly_pval.m, evaluates an R8POLY.
• r8poly_t2p.m, converts an R8POLY from Taylor to standard form.
• r8vec_backtrack.m, supervises a backtrack search for a real vector.
• r8vec_frac.m, searches for the K-th smallest entry in an N vector.
• r8vec_indicator1.m, sets a real vector to the indicator1 vector.
• r8vec_mirror_next.m, steps through all sign variations of a real vector.
• r8vec_print.m, prints a real vector.
• rat_add.m, adds two rational values.
• rat_div.m, carries out division of rational values.
• rat_farey.m, returns a row of the Farey fraction table.
• rat_farey2.m, returns the next row of the Farey fraction table.
• rat_mul.m, multiplies two rational values.
• rat_normalize.m, normalizes a rational value.
• rat_sum_formula.m, computes the formulas for sums of powers of integers.
• rat_to_cfrac.m, converts a rational to a continued fraction.
• rat_to_dec.m, converts a rational to a decimal value.
• rat_to_r8.m, converts a rational to a real value.
• rat_to_s.m, converts a rational to a left-justified string.
• rat_width.m, returns the "width" of a rational number.
• ratmat_det.m, computes the determinant of a rational matrix.
• ratmat_print.m, prints a rational matrix.
• regro_next.m, computes the next restricted growth function.
• rfrac_to_cfrac.m, converts a rational polynomial fraction to continued fraction form.
• rfrac_to_jfrac.m, converts a rational polynomial fraction to a J fraction.
• s_len_trim.m, returns the length of a string to the last nonblank.
• schroeder.m, generates the Schroeder numbers.
• sort_heap_external.m, externally sorts a list of items into ascending order.
• sort_heap_external_noglobal.m, externally sorts a list of items into ascending order, and does not use global memory.
• subcomp_next.m, computes the next subcomposition of N into K parts;
• subcompnz_next.m, computes the next subcomposition of N into K nonzero parts;
• subcompnz2_next.m, computes the next composition of N into K nonzero parts for N between N_LO and N_HI;
• subset_by_size_next.m, returns all the subsets of an N set, in decreasing order of size.
• subset_gray_next.m, generates the next subset of an N set.
• subset_gray_rank.m, ranks a subset of an N set using the Gray ordering.
• subset_gray_unrank.m, returns a subset of an N set with the given Gray ranking.
• subset_lex_next.m, returns the next subset of an N set, in lexicographic order.
• subset_random.m, selects a random subset of an N set.
• subtriangle_next.m, returns the next subtriangle in a triangle whose edges have each been subdivided into N parts.
• thue_binary_next.m, returns the next element in a binary Thue sequence.
• thue_ternary_next.m, returns the next element in a ternary Thue sequence.
• triang.m, renumbers items in accordance with a partial ordering.
• tuple_next.m, computes the next element of a tuple space.
• tuple2_next.m, computes the next element of a tuple space.
• tuple_next_fast.m, computes the next element of a tuple space, "fast".
• tuple_next_ge.m, computes the next "nondecreasing" element of a tuple space.
• ubvec_add.m, adds two unsigned binary vectors.
• ubvec_print.m, prints a UBVEC.
• ubvec_to_ui4.m, converts an unsigned binary vector to an unsigned integer.
• ubvec_xor.m, applies an exclusive OR to two unsigned binary vectors.
• ui4_to_ubvec.m, converts an integer to an unsigned binary vector.
• vec_colex_next.m, generates vectors in colex order.
• vec_colex_next2.m, generates vectors in colex order.
• vec_colex_next3.m, generates vectors in colex order.
• vec_gray_next.m, generates the elements of a product space.
• vec_gray_rank.m, returns the rank of an N-vectors of integers modulo a given base.
• vec_gray_unrank.m, computes the product space element of a given rank.
• vec_lex_next.m, generates all N-vectors of integers modulo a given base.
• vec_random.m, selects a random N-vectors of integers modulo a given base.
• vector_constrained_next.m, computes the next vector that lies in a given range and satisfies a particular constraint.
• vector_constrained_next2.m, computes the next vector that lies in a given range and satisfies a particular constraint.
• vector_constrained_next3.m, computes the next vector that lies in a given range and satisfies a particular constraint.
• vector_constrained_next4.m, computes the next vector that lies in a given range and satisfies a particular constraint.
• vector_constrained_next5.m, computes the next vector that lies in a given range and satisfies a particular constraint.
• vector_constrained_next6.m, computes the next vector that lies in a given range and satisfies a particular constraint.
• vector_constrained_next7.m, returns the next vector that lies in a given range and satisfies a particular constraint.
• vector_next.m, returns the next integer vector between two ranges.
• vector_sumlex_next.m, returns the next integer vector of dimension N, ordered by the sum of the entries, and by lexicographic order for equal sums.
• ytb_conjugate.m, conjugates a Young tableau.
• ytb_enum.m, enumerates the Young tableaus of size N.
• ytb_next.m, returns the next Young tableau of size N.
• ytb_print.m, prints a Young tableau.
• ytb_random.m, returns a random Young tableau.