technically-php/linear-partitioning

A simple library to solve linear partition problem with Dynamic Programming approach

1.0.2 2022-11-28 11:20 UTC

Requires

• php: >=7.0

Requires (Dev)

• larapack/dd: 1.0
• phpunit/phpunit: ^6.0 || ^7.0 || ^8.0

MIT

• Ivan Voskoboinyk

README

Based on a description from The Algorithm Design Manual book by Steven S. Skiena.

• Leverages the Dynamic Programming principle
• O(n²) complexity
• Fully annotated code
• Test suite
• Semver

Installation

composer require technically-php/linear-partitioning:^1.0

Usage

use \TechnicallyPhp\LinearPartitioning\LinearPartitioning;

$items = [100, 200, 300, 400, 500, 600, 700, 800, 900];
$ranges = LinearPartitioning::partition($items, 3);

var_dump($ranges);
// [ [100, 200, 300, 400, 500], [600, 700], [800, 900] ]

Credits

• Implemented by Ivan Voskoboinyk