SUBSET
Combinatorial Routines


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

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

Other objects considered include

Fortran77 source code for some of the algorithms is available in the The Stony Brook Algorithm Archive.

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:

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

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

COMBINATION_LOCK, a FORTRAN90 program which simulates the process of determining the secret combination of a lock.

COMBO, a FORTRAN90 library which includes many combinatorial routines.

FLOYD, a FORTRAN90 library which implements Floyd's algorithm for finding the shortest distance between pairs of nodes on a directed graph.

GRAFPACK, a FORTRAN90 library which carries out operations on abstract graphs.

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

LAMP, a FORTRAN77 library which solves linear assignment and matching problems.

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

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

PARTIAL_DIGEST, a FORTRAN90 library which solves the partial digest problem.

PARTITION_PROBLEM, a FORTRAN90 library which seeks solutions of the partition problem, splitting a set of integers into two subsets with equal sum.

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

SET_THEORY, a FORTRAN90 library which demonstrates various set theoretic operations using several models of a set.

SELECT, a FORTRAN90 library which generates various combinatorial objects.

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

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

TREEPACK, a FORTRAN90 library which carries out computations on trees, a simple kind of graph that is minimally connected.

UNICYCLE, a FORTRAN90 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. David Crouse,
    Remark on Algorithm 515,
    ACM Transactions on Mathematical Software,
    Volume 33, Number 2, Article 15, June 2007.
  9. 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.
  10. Laurent Habsieger, Maxim Kazarian, Sergei Lando,
    On the Second Number of Plutarch,
    American Mathematical Monthly,
    Volume 105, Number 5, May 1998, page 446.
  11. 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.
  12. John Hammersley,
    Monte Carlo methods for solving multivariable problems,
    Proceedings of the New York Academy of Science,
    Volume 86, 1960, pages 844-874.
  13. John Hart, Ward Cheney, Charles Lawson, Hans Maehly, Charles Mesztenyi, John Rice, Henry Thacher, Christoph Witzgall,
    Computer Approximations,
    Wiley, 1968,
    LC: QA297.C64.
  14. Brian Hayes,
    Third Base,
    American Scientist,
    Volume 89, Number 6, November-December 2001, pages 490-494.
  15. Mark Herkommer,
    Number Theory, A Programmer's Guide,
    McGraw Hill, 1999,
    ISBN: 0-07-913074-7.
  16. 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.
  17. Donald Knuth,
    The Art of Computer Programming,
    Volume 3, Sorting and Searching,
    Second Edition,
    Addison Wesley, 1998,
    ISBN: 0201896850,
    LC: QA76.6.K64.
  18. Hang Tong Lau,
    Algorithms on Graphs,
    Tab Books, 1989,
    ISBN: 0830634290,
    LC: QA166.L38
  19. Pierre LEcuyer,
    Random Number Generation,
    in Handbook of Simulation,
    edited by Jerry Banks,
    Wiley, 1998,
    ISBN: 0471134031,
    LC: T57.62.H37.
  20. Peter Lewis, Allen Goodman, James Miller,
    A Pseudo-Random Number Generator for the System/360,
    IBM Systems Journal,
    Volume 8, 1969, pages 136-143.
  21. Charles Mifsud,
    Algorithm 154, Combination in Lexicographic Order,
    Communications of the ACM,
    Volume 6, Number 3, March 1963, page 103.
  22. mil_std_1753,
    Military Standard 1753,
    FORTRAN, DoD Supplement To American National Standard X3.9-1978,
    9 November 1978.
  23. Albert Nijenhuis, Herbert Wilf,
    Combinatorial Algorithms for Computers and Calculators,
    Second Edition,
    Academic Press, 1978,
    ISBN: 0-12-519260-6,
    LC: QA164.N54.
  24. Robert Owens,
    Sums of Powers of Integers,
    Mathematics Magazine,
    Volume 65, Number 1, February 1992, pages 38-40.
  25. Norman Richert,
    Strang's Strange Figures,
    American Mathematical Monthly,
    Volume 99, Number 2, February 1992, pages 101-107.
  26. James Sandeson,
    Testing Ecological Patterns,
    American Scientist,
    Volume 88, Number 4, July-August 2000, pages 332-339.
  27. 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.
  28. Robert Sedgewick,
    Algorithms in C,
    Addison-Wesley, 1990,
    ISBN: 0-201-51425-7,
    LC: QA76.73.C15S43.
  29. Raymond Seroul,
    Programming for Mathematicians,
    Springer, 2000,
    ISBN: 3-540-66422-X,
    LC: QA76.6.S465.
  30. Mok-Kong Shen,
    Algorithm 202: Generation of Permutations in Lexicographical Order,
    Communications of the ACM,
    Volume 6, Number 9, September 1963, page 517.
  31. Richard Stanley,
    Hipparchus, Plutarch, Schroeder, and Hough,
    American Mathematical Monthly,
    Volume 104, Number 4, April 1997, pages 344-350.
  32. Dennis Stanton, Dennis White,
    Constructive Combinatorics,
    Springer, 1986,
    ISBN: 0387963472,
    LC: QA164.S79.
  33. Ian Stewart,
    A Neglected Number,
    Scientific American,
    Volume 274, pages 102-102, June 1996.
  34. Ian Stewart,
    Math Hysteria,
    Oxford, 2004,
    ISBN: 0198613369,
    LC: QA95.S7255.
  35. James Sylvester,
    Question 7382, Mathematical Questions with their Solutions,
    Educational Times,
    Volume 41, page 21, 1884.
  36. Hale Trotter,
    Algorithm 115: PERM,
    Communications of the Association for Computing Machinery,
    Volume 5, Number 8, August 1962, pages 434-435.
  37. Johannes vanderCorput,
    Verteilungsfunktionen I & II,
    Proceedings of the Koninklijke Nederlandsche Akademie van Wetenschappen,
    Volume 38, 1935, pages 813-820, pages 1058-1066.
  38. Jack vanLint, Richard Wilson,
    A Course in Combinatorics,
    Cambridge, 1992,
    ISBN: 0-521-42260-4,
    LC: QA164.L56.
  39. Eric Weisstein,
    CRC Concise Encyclopedia of Mathematics,
    CRC Press, 2002,
    Second edition,
    ISBN: 1584883472,
    LC: QA5.W45
  40. Stephen Wolfram,
    The Mathematica Book,
    Fourth Edition,
    Cambridge University Press, 1999,
    ISBN: 0-521-64314-7,
    LC: QA76.95.W65.
  41. 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.
  42. 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 FORTRAN90 source codes.


Last revised on 29 December 2014.