partition_problem

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

Licensing:

The computer code and data files described and made available on this web page are distributed under the MIT license

Languages:

partition_problem 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:

partition_problem_test

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

combo, an Octave code which includes many combinatorial routines.

subset, an Octave code which enumerates, generates, ranks and unranks combinatorial objects including combinations, partitions, subsets, index sets, and trees.

subset_sum, an Octave code which seeks solutions of the subset sum problem.

Reference:

1. Alexander Dewdney,
   The Turing Omnibus,
   Freeman, 1989,
   ISBN13: 9780716781547,
   LC: QA76.D45.
2. Brian Hayes,
   The Easiest Hard Problem,
   American Scientist,
   Volume 90, Number 2, March-April 2002, pages 113-117.
3. Silvano Martello, Paolo Toth,
   Knapsack Problems: Algorithms and Computer Implementations,
   Wiley, 1990,
   ISBN: 0-471-92420-2,
   LC: QA267.7.M37.

Source Code:

• partition_brute.m approaches the partition problem using brute force.
• partition_count.m counts the solutions to a partition problem.
• subset_next.m computes the subset lexicographic successor.