subset

subset, a C++ 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.

These 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 made available on this web page are distributed under the MIT 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:

subset_test

backtrack_binary_rc, a C++ code which carries out a backtrack search for a set of binary decisions, using reverse communication (RC).

change_making, a C++ code which considers the change making problem, in which a given sum is to be formed using coins of various denominations.

combo, a C++ code which includes many combinatorial routines.

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

legendre_product_polynomial, a C++ code which defines Legendre product polynomials, creating a multivariate polynomial as the product of univariate Legendre polynomials.

monomial, a C++ 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_problem, a C++ code which seeks solutions of the partition problem, splitting a set of integers into two subsets with equal sum.

polynomial, a C++ code which adds, multiplies, differentiates, evaluates and prints multivariate polynomials in a space of M dimensions.

subset_sum, a C++ code which seeks solutions of the subset sum problem.

toms515, a C++ 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 C++ 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 C++ code 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. Walter Ball,
   Mathematical Recreations and Essays,
   Macmillan, 1962,
   ISBN: 1417921269,
   LC: QA95.B2.
3. Paul Bratley, Bennett Fox, Linus Schrage,
   A Guide to Simulation,
   Second Edition,
   Springer, 1987,
   ISBN: 0387964673,
   LC: QA76.9.C65.B73.
4. Bill Buckles, Matthew Lybanon,
   Algorithm 515: Generation of a Vector from the Lexicographical Index,
   ACM Transactions on Mathematical Software,
   Volume 3, Number 2, June 1977, pages 180-182.
5. Tom Christiansen, Nathan Torkington,
   Perl Cookbook,
   O'Reilly, 2003,
   ISBN: 0596003137,
   LC: QA76.73.P22.C38.
6. 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.
7. John Conway, Richard Guy,
   The Book of Numbers,
   Springer, 1998,
   ISBN: 038797993X,
   LC: QA241.C6897.
8. 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.
9. Laurent Habsieger, Maxim Kazarian, Sergei Lando,
   On the Second Number of Plutarch,
   American Mathematical Monthly,
   Volume 105, Number 5, May 1998, page 446.
10. John Halton,
    On the efficiency of certain quasi-random sequences of points in evaluating multi-dimensional integrals,
    Numerische Mathematik,
    Volume 2, Number 1, December 1960, pages 84-90.
11. John Hammersley,
    Monte Carlo methods for solving multivariable problems,
    Proceedings of the New York Academy of Science,
    Volume 86, 1960, pages 844-874.
12. John Hart, Ward Cheney, Charles Lawson, Hans Maehly, Charles Mesztenyi, John Rice, Henry Thacher, Christoph Witzgall,
    Computer Approximations,
    Wiley, 1968,
    LC: QA297.C64.
13. Brian Hayes,
    Third Base,
    American Scientist,
    Volume 89, Number 6, November-December 2001, pages 490-494.
14. Mark Herkommer,
    Number Theory, A Programmer's Guide,
    McGraw Hill, 1999,
    ISBN: 0-07-913074-7.
15. Karla Hoffman, Douglas Shier,
    Algorithm 564: A Test Problem Generator for Discrete Linear L1 Approximation Problems,
    ACM Transactions on Mathematical Software,
    Volume 6, Number 4, December 1980, pages 615-617.
16. Donald Knuth,
    The Art of Computer Programming,
    Volume 3, Sorting and Searching,
    Second Edition,
    Addison Wesley, 1998,
    ISBN: 0201896850,
    LC: QA76.6.K64.
17. Hang Tong Lau,
    Algorithms on Graphs,
    Tab Books, 1989,
    ISBN: 0830634290,
    LC: QA166.L38
18. Pierre LEcuyer,
    Random Number Generation,
    in Handbook of Simulation,
    edited by Jerry Banks,
    Wiley, 1998,
    ISBN: 0471134031,
    LC: T57.62.H37.
19. Peter Lewis, Allen Goodman, James Miller,
    A Pseudo-Random Number Generator for the System/360,
    IBM Systems Journal,
    Volume 8, 1969, pages 136-143.
20. Charles Mifsud,
    Algorithm 154, Combination in Lexicographic Order,
    Communications of the ACM,
    Volume 6, Number 3, March 1963, page 103.
21. mil_std_1753,
    Military Standard 1753,
    Fortran, DoD Supplement To American National Standard X3.9-1978,
    9 November 1978.
22. Albert Nijenhuis, Herbert Wilf,
    Combinatorial Algorithms for Computers and Calculators,
    Second Edition,
    Academic Press, 1978,
    ISBN: 0-12-519260-6,
    LC: QA164.N54.
23. Robert Owens,
    Sums of Powers of Integers,
    Mathematics Magazine,
    Volume 65, Number 1, February 1992, pages 38-40.
24. Norman Richert,
    Strang's Strange Figures,
    American Mathematical Monthly,
    Volume 99, Number 2, February 1992, pages 101-107.
25. James Sandeson,
    Testing Ecological Patterns,
    American Scientist,
    Volume 88, Number 4, July-August 2000, pages 332-339.
26. Ian Saunders,
    Algorithm AS 205,
    Enumeration of R x C Tables with Repeated Row Totals,
    Applied Statistics,
    Volume 33, Number 3, 1984, pages 340-352.
27. Robert Sedgewick,
    Algorithms in C,
    Addison-Wesley, 1990,
    ISBN: 0-201-51425-7,
    LC: QA76.73.C15S43.
28. Raymond Seroul,
    Programming for Mathematicians,
    Springer, 2000,
    ISBN: 3-540-66422-X,
    LC: QA76.6.S465.
29. Mok-Kong Shen,
    Algorithm 202: Generation of Permutations in Lexicographical Order,
    Communications of the ACM,
    Volume 6, Number 9, September 1963, page 517.
30. Richard Stanley,
    Hipparchus, Plutarch, Schroeder, and Hough,
    American Mathematical Monthly,
    Volume 104, Number 4, April 1997, pages 344-350.
31. Dennis Stanton, Dennis White,
    Constructive Combinatorics,
    Springer, 1986,
    ISBN: 0387963472,
    LC: QA164.S79.
32. Ian Stewart,
    A Neglected Number,
    Scientific American,
    Volume 274, pages 102-102, June 1996.
33. Ian Stewart,
    Math Hysteria,
    Oxford, 2004,
    ISBN: 0198613369,
    LC: QA95.S7255.
34. James Sylvester,
    Question 7382, Mathematical Questions with their Solutions,
    Educational Times,
    Volume 41, page 21, 1884.
35. Hale Trotter,
    Algorithm 115: PERM,
    Communications of the Association for Computing Machinery,
    Volume 5, Number 8, August 1962, pages 434-435.
36. Johannes vanderCorput,
    Verteilungsfunktionen I & II,
    Proceedings of the Koninklijke Nederlandsche Akademie van Wetenschappen,
    Volume 38, 1935, pages 813-820, pages 1058-1066.
37. Jack vanLint, Richard Wilson,
    A Course in Combinatorics,
    Cambridge, 1992,
    ISBN: 0-521-42260-4,
    LC: QA164.L56.
38. Eric Weisstein,
    CRC Concise Encyclopedia of Mathematics,
    CRC Press, 2002,
    Second edition,
    ISBN: 1584883472,
    LC: QA5.W45
39. Stephen Wolfram,
    The Mathematica Book,
    Fourth Edition,
    Cambridge University Press, 1999,
    ISBN: 0-521-64314-7,
    LC: QA76.95.W65.
40. ML Wolfson, HV Wright,
    ACM Algorithm 160: Combinatorial of M Things Taken N at a Time,
    Communications of the ACM,
    Volume 6, Number 4, April 1963, page 161.
41. Daniel Zwillinger, editor,
    CRC Standard Mathematical Tables and Formulae,
    30th Edition,
    CRC Press, 1996,
    ISBN: 0-8493-2479-3,
    LC: QA47.M315.

Source Code:

• subset.cpp, the source code;
• subset.sh, compiles the source code;
• subset.hpp, the include file for SUBSET;