Skip to content
master
Go to file
Code

Latest commit

 

Git stats

Files

Permalink
Failed to load latest commit information.
Type
Name
Latest commit message
Commit time
 
 
src
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

README.md

PHPartition

Build Status Code Coverage Scrutinizer Code Quality Dependency Status

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.

About

Partition problem for balanced arrays splitting made easy.

Topics

Resources

Sponsor this project

 

Packages

No packages published

Languages

You can’t perform that action at this time.