|
1
|
|
|
<?php |
|
2
|
|
|
|
|
3
|
|
|
namespace drupol\phpartition\Algorithm; |
|
4
|
|
|
|
|
5
|
|
|
use drupol\phpartition\BasePartitionAlgorithm; |
|
6
|
|
|
use drupol\phpartition\PartitionAlgorithmInterface; |
|
7
|
|
|
use drupol\phpartition\Subset; |
|
8
|
|
|
use Math\Combinatorics\Permutation; |
|
9
|
|
|
use Oefenweb\Statistics\Statistics; |
|
10
|
|
|
|
|
11
|
|
|
/** |
|
12
|
|
|
* Class BruteForceCustomA. |
|
13
|
|
|
* |
|
14
|
|
|
* @package drupol\phpartition\Algorithm |
|
15
|
|
|
*/ |
|
16
|
|
|
class BruteForceCustomA extends BasePartitionAlgorithm implements PartitionAlgorithmInterface { |
|
17
|
|
|
|
|
18
|
|
|
/** |
|
19
|
|
|
* @inheritdoc |
|
20
|
|
|
*/ |
|
21
|
4 |
|
public function getResult() { |
|
22
|
4 |
|
$permutation = new Permutation(); |
|
23
|
|
|
// Sort the initial data set ascending. |
|
24
|
4 |
|
$this->dataset->sortByValue('ASC'); |
|
25
|
|
|
// Compute the maximum value of the variance. |
|
26
|
4 |
|
$variance = pow(2, $this->dataset->count()); |
|
27
|
|
|
// Set a default value for the variable that will contain the solution. |
|
28
|
4 |
|
$solution = NULL; |
|
|
|
|
|
|
29
|
|
|
// Get the number of elements in the input dataset. |
|
30
|
4 |
|
$count = $this->dataset->count(); |
|
31
|
|
|
// Compute the size of a chunk. Ceiling the value because it cannot be zero. |
|
32
|
4 |
|
$chunkSize = ceil($count/$this->getPartition()); |
|
33
|
|
|
|
|
34
|
|
|
// Loop through each permutation and compute the variance of each subsetchunks. |
|
35
|
4 |
|
foreach ($permutation->getPermutations($this->dataset->getItems(), $count) as $subset) { |
|
36
|
|
|
// Get the variance of the sums array. |
|
37
|
4 |
|
$varianceCandidate = Statistics::variance( |
|
38
|
4 |
|
array_map(function($items) { |
|
|
|
|
|
|
39
|
4 |
|
$phpartitionSubset = new Subset(); |
|
40
|
4 |
|
$phpartitionSubset->setItems($items); |
|
41
|
4 |
|
return $phpartitionSubset->getWeight(); |
|
42
|
4 |
|
}, array_chunk($subset, $chunkSize) |
|
43
|
4 |
|
) |
|
44
|
4 |
|
); |
|
45
|
|
|
|
|
46
|
|
|
// If we've found a better variance with this subset, store it. |
|
47
|
4 |
|
if ($varianceCandidate < $variance) { |
|
48
|
4 |
|
$variance = $varianceCandidate; |
|
49
|
4 |
|
$solution = $subset; |
|
50
|
|
|
|
|
51
|
|
|
// If the variance is equal to zero, that's the best candidate, |
|
52
|
|
|
// store the value and exit the loop prematurely. |
|
53
|
4 |
|
if (0 == $varianceCandidate) { |
|
54
|
2 |
|
break; |
|
55
|
|
|
} |
|
56
|
4 |
|
} |
|
57
|
4 |
|
} |
|
58
|
|
|
|
|
59
|
|
|
// Store each chunks into a subset in the SubsetContainer. |
|
60
|
4 |
|
foreach (array_chunk($solution, $chunkSize) as $subsetChunks) { |
|
61
|
4 |
|
$subset = new Subset(); |
|
62
|
4 |
|
$subset->setAlgo($this); |
|
63
|
4 |
|
$subset->setItems($subsetChunks); |
|
64
|
4 |
|
$this->getSubsetContainer()->insert($subset); |
|
65
|
4 |
|
} |
|
66
|
|
|
|
|
67
|
4 |
|
return $this->getSubsetContainer()->getSubsetsAndItemsAsArray(); |
|
68
|
|
|
} |
|
69
|
|
|
|
|
70
|
|
|
} |
drupol /
phpartition
Loading history...