mikegarde/partition

The Partition Problem

, _(*1)

A PHP function to partition a set of values into equal sets or near equal sets (partitions). Read more about the partition problem on wikipedia., _(*2)

Installing

Find on packagist.org, _(*3)

composer require mikegarde/partition, _(*4)

Example

<?php

require 'vendor/autoload.php';

use partition\partition;

$data = [
    [
        'id'    => 'A',
        'value' => 5,
    ],
    [
        'id'    => 'B',
        'value' => 5,
    ],
    [
        'id'    => 'C',
        'value' => 15,
    ],
    [
        'id'    => 'D',
        'value' => 5,
    ],
    [
        'id'    => 'E',
        'value' => 9,
    ],
    [
        'id'    => 'F',
        'value' => 3,
    ],
    [
        'id'    => 'G',
        'value' => 7,
    ],
    [
        'id'    => 'H',
        'value' => 12,
    ],
];

$partition = new partition($data, 4);
$partition->process();

$results = $partition->getResults();
$part    = $partition->getPartition(0);

A JSON representation of $results and $part, _(*5)

{
  "summary": [
    15,
    17,
    14,
    15
  ],
  "partitions": [
    [
      {
        "id": "C",
        "value": 15
      }
    ],
    [
      {
        "id": "H",
        "value": 12
      },
      {
        "id": "D",
        "value": 5
      }
    ],
    [
      {
        "id": "E",
        "value": 9
      },
      {
        "id": "B",
        "value": 5
      }
    ],
    [
      {
        "id": "G",
        "value": 7
      },
      {
        "id": "A",
        "value": 5
      },
      {
        "id": "F",
        "value": 3
      }
    ]
  ]
}

[
  {
    "id": "C",
    "value": 15
  }
]

TODO:

• [ ] Replace dusank/knapsack with a custom implementation
• [ ] Move/Duplicate to GitHub Actions