drupol / phpartition
Partition problem for balanced arrays splitting made easy.
Fund package maintenance!
drupol
Installs: 4 061
Dependents: 1
Suggesters: 0
Security: 0
Stars: 8
Watchers: 5
Forks: 0
Open Issues: 1
Requires
- drupol/phpermutations: ^1.0
- oefenweb/statistics: ^1.1
- phootwork/collection: ^1.4
Requires (Dev)
- codacy/coverage: dev-master
- drupal/coder: ^8.2
- mockery/mockery: ^0.9
- phpunit/php-code-coverage: ^4.0
- phpunit/phpunit: ^5.6
- satooshi/php-coveralls: ^1.0
- scrutinizer/ocular: ^1.3
- squizlabs/php_codesniffer: ^2.0
This package is auto-updated.
Last update: 2024-10-11 20:16:55 UTC
README
In number theory and computer science, the partition problem is the task of deciding whether a given multiset of items can be partitioned into multiple balanced subsets.
Requirements
- PHP >= 5.6,
- (optional) PHPUnit to run tests.
Examples
<?php include "./vendor/autoload.php"; $data = array(1, 5, 5, 11, 6, 7, 9, 3); $greedy = new \drupol\phpartition\Algorithm\Greedy(); $greedy->setData($data); $greedy->setSize(3); $result = $greedy->getResult(); // $result is: /* * Array ( [0] => Array ( [0] => 9 [1] => 5 [2] => 1 ) [1] => Array ( [0] => 7 [1] => 6 [2] => 3 ) [2] => Array ( [0] => 11 [1] => 5 ) ) */ $simple = new \drupol\phpartition\Algorithm\Simple(); $simple->setData($data); $simple->setSize(3); $result = $simple->getResult(); // $result is: /* * Array ( [0] => Array ( [0] => 5 [1] => 11 ) [1] => Array ( [0] => 1 [1] => 7 [2] => 3 ) [2] => Array ( [0] => 5 [1] => 6 [2] => 9 ) ) */
You may also pass objects or array but then, you'll have to define how to access their value.
<?php include "./vendor/autoload.php"; $data = array( array( 'item' => 'anything A', 'weight' => 1, ), array( 'item' => 'anything B', 'weight' => 2, ), array( 'item' => 'anything C', 'weight' => 3, ), array( 'item' => 'anything D', 'weight' => 4, ), ); $greedy = new \drupol\phpartition\Algorithm\Greedy(); $greedy->setData($data); $greedy->setSize(2); $greedy->setItemAccessCallback(function($item) { return $item['weight']; }); $result = $greedy->getResult(); // $result is /* * Array ( [0] => Array ( [0] => Array ( [item] => anything C [weight] => 3 ) [1] => Array ( [item] => anything B [weight] => 2 ) ) [1] => Array ( [0] => Array ( [item] => anything D [weight] => 4 ) [1] => Array ( [item] => anything A [weight] => 1 ) ) ) */
It's also possible to mix the type of object to partition.
TODO
- Implement Complete Karmarkar-Karp (CKK) algorithm,
- Documentation.