prtpy - Number Partitioning

0.8.3 · active · verified Fri Apr 17

prtpy is a Python library for number partitioning. It provides various algorithms to divide a list of numbers into a specified number of subsets, typically aiming to minimize the largest sum of a subset. It is actively maintained, with the current version being 0.8.3, and releases occur as new algorithms, improvements, or bug fixes are introduced.

Common errors

```
ModuleNotFoundError: No module named 'pulp'
```
cause You are attempting to use the `prtpy.partition.ilp` algorithm without having the `pulp` library installed.

fix Install the `pulp` library using `pip install pulp`.
```
TypeError: '<' not supported between instances of 'str' and 'int'
```
cause One or more elements in your `items` list are strings (or other non-numeric types) instead of numbers, which `prtpy` algorithms expect.

fix Ensure all items in the list passed to `prtpy` algorithms are numerical (integers or floats).
```
Program runs indefinitely or extremely slowly for large inputs.
```
cause You are likely using an exponential-time complexity algorithm (e.g., `recursive`, `schroeppel`) with a large number of input items.

fix Switch to a polynomial-time complexity algorithm for large inputs, such as `greedy`, `balancer`, or `complete_greedy`, which are much more performant.

Warnings

gotcha The `ilp` (Integer Linear Programming) algorithm requires the `pulp` library and an external solver (e.g., CBC, GLPK) to be installed. Without these, using `prtpy.partition.ilp` will result in a `ModuleNotFoundError` for `pulp` or a `PulpSolverError` if no solver is found.
Fix: Install `pulp` via `pip install pulp` and ensure a compatible solver (e.g., `cbc` is often included with `pulp` or can be installed separately) is available in your system's PATH.
gotcha Some partitioning algorithms, such as `prtpy.partition.recursive` and `prtpy.partition.schroeppel`, have exponential time complexity. They are highly efficient for small inputs but can become extremely slow or unresponsive for larger lists of numbers.
Fix: For large datasets or performance-critical applications, prefer polynomial-time algorithms like `greedy`, `balancer`, or `complete_greedy`. Consult the documentation for the complexity characteristics of each algorithm.
gotcha The `items` argument for partitioning functions expects an iterable of numerical values (integers or floats). Providing non-numerical types (e.g., strings) will lead to `TypeError` or unexpected behavior during comparisons or arithmetic operations.
Fix: Always ensure that the list of items you pass to `prtpy` algorithms contains only numbers. Validate or sanitize your input data if it originates from external sources.

Install

pip install prtpy Install stable version

Imports

partition
```
from prtpy import partition
```
Imports the main partitioning wrapper function.
greedy
```
from prtpy.partition import greedy
```
Imports a specific partitioning algorithm (e.g., greedy).
ilp
```
from prtpy.partition import ilp
```
Imports the ILP partitioning algorithm, which requires the `pulp` package and an installed solver.

Quickstart

This quickstart demonstrates how to use `prtpy` to partition a list of numbers into a specified number of bins using the greedy algorithm. The `partition` function acts as a general interface, accepting the algorithm as a parameter.

from prtpy import partition
from prtpy.partition import greedy

numbers = [3, 4, 5, 6, 7, 8, 9, 10]
num_bins = 3

# Partition the numbers into 3 bins using the greedy algorithm
result = partition(algorithm=greedy, num_bins=num_bins, items=numbers)

print(f"Original numbers: {numbers}")
print(f"Number of bins: {num_bins}")
print(f"Partition result (greedy): {result}")
# Expected output for the given input might be similar to: [[10, 8, 3], [9, 7, 4], [6, 5]]

view raw JSON →