partitionpy 1.0.0

A collection of PARTITION algorithms

partition package

This is a collection of several algorithms to solve PARTITION.

The package offers two heuristics:

• the naive greedy heuristic
• the Karmakar-Karp heuristic or Largest Differencing Method (LDM) and a complete algorithm,
• the Complete Karmarkar-Karp algorithm.

The latter is also available in a more efficient version for some instances.

Resources on the partition problem

The implementation stem from a project during my master's degree. The resulting thesis is available, feel free to read especially the sections 1 to 3. From the references, I would like to recommend the following publications in particular:

R. E. Korf. A complete anytime algorithm for number partitioning. Artif. Intell., 106(2): 181–203, dec 1998. ISSN 0004-3702. doi:10.1016/S0004-3702(98)00086-1.

B. Hayes. Computing science: The easiest hard problem. American Scientist, 90(2):113–117, 2002. ISSN 00030996. URL http://www.jstor.org/stable/27857621.

S. Mertens. The easiest hard problem: number partitioning. In Computational Complexity and Statistical Physics. Oxford University Press, 12 2005. ISBN 9780195177374. doi:10.1093/oso/9780195177374.003.0012.

Installation and usage

Run pip install partitionpy to install.

Example code:

import partitionpy

partitionpy.karmarkar_karp([4,5,6,7,8])
partitionpy.naive_greedy([4,5,6,7,8])
partitionpy.complete_karmarkar_karp([4,5,6,7,8])
partitionpy.kernelized_complete_karmarkar_karp([4,5,6,7,8])
partitionpy.complete_greedy([4,5,6,7,8])

Alternatives

This is by far not the only package for PARTITION. You may want to check out numberpartitioning and prtpy as well.