TOMS448
Number of Multiply-Restricted Partitions

TOMS448 is a FORTRAN77 library which implements ACM TOMS algorithm 448, which determines the number of partitions of an integer into parts restricted to a given set.

This routine can be used to solve various problems in counting the number of ways of making change with a given set of coin denominations, for instance.

The text of many ACM TOMS algorithms is available online through ACM: http://www.acm.org/pubs/calgo or NETLIB: http://www.netlib.org/toms/index.html.

Usage:

call count ( c, k, p, n )

where C, is a vector of K positive integers, and N is an integer larger than the largest value in C. On return P(I) contains the number of partitions of I restricted to entries from C.

Languages:

TOMS448 is available in a FORTRAN77 version.

Reference:

1. Terry Beyer, Donald Swinehart,
   Algorithm 448: Number of Multiply-Restricted Partitions,
   Communications of the ACM,
   June 1973, Volume 16, Number 6, page 379.

Source Code:

• toms448.f, the source code.
• toms448.sh, commands to compile the source code.

Examples and Tests:

• toms448_prb.f, a sample calling program.
• toms448_prb.sh, commands to compile and run the sample program.
• toms448_prb_output.txt, the output file.

List of Routines:

• COUNT determines the number of partitions of an integer, restricted to integers in a given set.

You can go up one level to the FORTRAN77 source codes.