|
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
|
|
|
|
|
10
|
|
|
/** |
|
11
|
|
|
* Class BruteForce. |
|
12
|
|
|
* |
|
13
|
|
|
* @package drupol\phpartition\Algorithm |
|
14
|
|
|
*/ |
|
15
|
|
|
class BruteForce extends BasePartitionAlgorithm implements PartitionAlgorithmInterface { |
|
16
|
|
|
|
|
17
|
|
|
/** |
|
18
|
|
|
* @return array |
|
19
|
|
|
*/ |
|
20
|
2 |
|
public function getResult() { |
|
|
|
|
|
|
21
|
2 |
|
$permutation = new Permutation(); |
|
22
|
2 |
|
$this->dataset->sortByValue('ASC'); |
|
23
|
|
|
|
|
24
|
2 |
|
$partition_size = ($this->getPartition() > $this->dataset->count()) ? $this->dataset->count() : $this->getPartition(); |
|
25
|
|
|
|
|
26
|
2 |
|
for ($p=$partition_size; $p > 1; $p--) { |
|
27
|
2 |
|
$best = $this->dataset->getSum(); |
|
28
|
2 |
|
$target = ($best - ($best % $p))/ $p; |
|
29
|
2 |
|
$good_subset = array(); |
|
30
|
2 |
|
$max_size = floor($this->dataset->count() / $p); |
|
31
|
|
|
|
|
32
|
2 |
|
for ($i = 1; $i <= $max_size; $i++) { |
|
33
|
2 |
|
foreach ($permutation->getPermutations($this->dataset->getItems(), $i) as $subset) { |
|
34
|
2 |
|
$x = 0; |
|
35
|
2 |
|
foreach ($subset as $item) { |
|
36
|
2 |
|
$x += $item->getValue(); |
|
37
|
2 |
|
if (abs($x - $target) - abs($best - $target) < 0) { |
|
38
|
2 |
|
$best = $x; |
|
39
|
2 |
|
$good_subset = $subset; |
|
40
|
2 |
|
} |
|
41
|
2 |
|
} |
|
42
|
2 |
|
} |
|
43
|
2 |
|
} |
|
44
|
|
|
|
|
45
|
2 |
|
$subset = new Subset(); |
|
46
|
2 |
|
$subset->setAlgo($this); |
|
47
|
2 |
|
$subset->addItems($good_subset); |
|
48
|
2 |
|
$this->getSubsetContainer()->insert($subset); |
|
49
|
2 |
|
$this->dataset->deleteItems($good_subset); |
|
50
|
2 |
|
} |
|
51
|
|
|
|
|
52
|
2 |
|
$subset = new Subset(); |
|
53
|
2 |
|
$subset->setAlgo($this); |
|
54
|
2 |
|
$subset->addItems($this->dataset->getItems()); |
|
55
|
2 |
|
$this->getSubsetContainer()->insert($subset); |
|
56
|
|
|
|
|
57
|
2 |
|
return $this->getSubsetContainer()->getSubsetsAndItemsAsArray(); |
|
58
|
|
|
} |
|
59
|
|
|
|
|
60
|
|
|
/** |
|
61
|
|
|
* @param \drupol\phpartition\Subset $subset |
|
62
|
|
|
* |
|
63
|
|
|
* @return int|mixed |
|
64
|
|
|
*/ |
|
65
|
2 |
|
public function getSubsetWeight(Subset $subset) { |
|
66
|
2 |
|
$sum = 0; |
|
67
|
|
|
|
|
68
|
2 |
|
foreach($subset->getItems() as $item) { |
|
|
|
|
|
|
69
|
2 |
|
$sum += $item->getValue(); |
|
70
|
2 |
|
} |
|
71
|
|
|
|
|
72
|
2 |
|
return $sum; |
|
73
|
|
|
} |
|
74
|
|
|
|
|
75
|
|
|
} |
drupol /
phpartition
Loading history...
This check marks variable names that have not been written in camelCase.
In camelCase names are written without any punctuation, the start of each new word being marked by a capital letter. Thus the name database connection string becomes
databaseConnectionString.