SUBSET
Combinatorial Routines


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

These include the enumeration, generation, random selection, ranking and unranking of

Other objects considered include

Licensing:

The computer code and data files 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 a Python version.

Related Data and Programs:

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

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

COMBO, a C++ library which includes many combinatorial routines.

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

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

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

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

SUBSET_SUM, a C++ library which seeks solutions of the subset sum problem.

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

UBVEC, a C++ library 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++ library 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:

Examples and Tests:

List of Routines:

You can go up one level to the C++ source codes.


Last revised on 11 December 2013.