subset

subset, a Fortran90 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 N into K parts;
• COMPNZ, compositions of an integer N into K parts, 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;
• KSUB's, 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, a Fortran90 code which carries out a backtrack search for a set of binary decisions, using reverse communication.

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

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

combo, a Fortran90 code which includes many combinatorial routines.

floyd, a Fortran90 code which implements Floyd's algorithm for finding the shortest distance between pairs of nodes on a directed graph.

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

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

monomial, a Fortran90 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.

partial_digest, a Fortran90 code which solves the partial digest problem.

partition_problem, a Fortran90 code which seeks solutions of the partition problem, splitting a set of integers into two subsets with equal sum.

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

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

toms515, a Fortran90 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.

treepack, a Fortran90 code which carries out computations on trees, a simple kind of graph that is minimally connected.

unicycle, a Fortran90 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. 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:

• subset.f90, the source code;
• subset.sh, compiles the source code;