drupol/phpartition

Partition problem for balanced arrays splitting made easy.

0.1.2 2017-01-15 22:37 UTC

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

GPL-2.0+

• Pol Dellaiera

• math
• numbers
• statistics
• Partition
• greedy
• karmarkar
• karp

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.