Я только что задал очень похожий вопрос и не смог найти отличного ответа, но в конце концов я смог выяснить это самостоятельно. Я надеялся, что если я поделюсь этим с вами, вы сможете поделиться любыми мыслями, которые могли бы найти. На самом деле это не использует никаких сторонних зависимостей, но требует расширения «DS» для PHP для использования Sets. Вы можете просто использовать массивы, наборы на самом деле не требуются, вам просто нужно написать некоторые функции для функций набора, ie set-> contains (...), et c., Если вы используя PHP. Python, вероятно, уже имеет эти структуры данных, хотя я не совсем знаком, поэтому я не могу сказать наверняка. В любом случае, вот код, я надеюсь, это поможет, он определенно может использовать некоторую оптимизацию, но он находит правильные ответы и соответствует ответам решателя из кода python, предоставленного выше ldog:
Хорошо, поэтому я нашел ответ, хотя, возможно, это не самое оптимизированное решение. Если кто-нибудь может помочь мне ускорить этот процесс или, возможно, помочь мне написать это таким образом, чтобы он мог найти оптимальную тройку лучших, я был бы признателен. Вот мой код, обратите внимание, что я использую структуру данных «Set», доступную по адресу https://github.com/php-ds
class ProductionOptimizer{
private int $CARDINALITY=6;
private CombinationsIterator $combinationsIterator;
private array $tickets;
private Set $threads;
public function __construct(array $array){
$this->tickets=$array;
$start = microtime(TRUE);
$this->threads=new Set();
foreach ($array as $ticketThreads){
foreach ($ticketThreads as $thread)
$this->threads->add($thread);
}
$end = microtime(TRUE);
// print_r($this->threads);
echo PHP_EOL."Creating the Set took " . ($end - $start) . " seconds to complete.";
$this->combinationsIterator=new CombinationsIterator($this->getThreadsAsArray(),6);
}
public function outputThreads() : void {
print_r($this->threads);
}
public function getThreadsAsArray() : array {
return $this->threads->toArray();
}
public function getCombinationsIterator() : CombinationsIterator{
return $this->combinationsIterator;
}
public function createNewCombinationsIterator(array $array, int $subsetCardinality=null) : CombinationsIterator {
if(is_null($subsetCardinality)) $subsetCardinality=$this->CARDINALITY;
$this->combinationsIterator=new CombinationsIterator($array, $subsetCardinality);
return $this->combinationsIterator;
}
public function removeFromSet(array $array){
// var_dump($this->threads);
echo "Removing Threads(before count :".$this->threads->count().")...".PHP_EOL;
$this->threads->remove(...$array);
// var_dump($this->threads);
echo "Removing Threads(after count: ".$this->threads->count().")...".PHP_EOL;
$this->combinationsIterator=new CombinationsIterator($this->getThreadsAsArray(),6);
}
public function getSet() : Set {
return $this->threads;
}
public function getThreads() : Set {
return $this->threads;
}
/* not need if using Set class */
/*
Set:
The code took 4.5061111450195E-5 seconds to complete.
This Function:
The code took 0.0054061412811279 seconds to complete.
*/
public function deduplicateArray($array){
array_walk_recursive($array, function($v) use (&$r){$r[]=$v;});
return array_values(array_unique($r));
}
}
class CombinationsIterator implements Iterator
{
protected $c = null;
protected $s = null;
protected $n = 0;
protected $k = 0;
protected $pos = 0;
function __construct($s, $k) {
if(is_array($s)) {
$this->s = array_values($s);
$this->n = count($this->s);
} else {
$this->s = (string) $s;
$this->n = strlen($this->s);
}
$this->k = $k;
$this->rewind();
}
function key() {
return $this->pos;
}
function current() {
$r = array();
for($i = 0; $i < $this->k; $i++)
$r[] = $this->s[$this->c[$i]];
return is_array($this->s) ? $r : implode('', $r);
}
function next() {
if($this->_next())
$this->pos++;
else
$this->pos = -1;
}
function rewind() {
$this->c = range(0, $this->k);
$this->pos = 0;
}
function valid() {
return $this->pos >= 0;
}
protected function _next() {
$i = $this->k - 1;
while ($i >= 0 && $this->c[$i] == $this->n - $this->k + $i)
$i--;
if($i < 0)
return false;
$this->c[$i]++;
while($i++ < $this->k - 1)
$this->c[$i] = $this->c[$i - 1] + 1;
return true;
}
}
, и вот некоторые образцы данных для тестирования. это приведет к получению трех верхних упорядоченных последовательностей, удаляя соответствующие наборы из вселенной наборов с каждой итерацией:
function humanReadableMemory($size)
{
$unit=array('b','kb','mb','gb','tb','pb');
return @round($size/pow(1024,($i=floor(log($size,1024)))),2).' '.$unit[$i];
}
$tickets = [
[1029],
[1029],
[1029],
[1029],
[1029],
[1029],
[1029],
[1029, 1049],
[1029, 1049],
[1029, 1049, 1080, 1112, 1125, 1188],
[1029, 1049, 1125],
[1029, 1049, 1188, 1278],
[1029, 1056, 1138, 1158, 1182, 1514, 1531],
[1029, 1071, 1076],
[1029, 1074, 1075, 1092, 1093, 1242, 1523, 1525],
[1029, 1094, 1125, 1138, 1158],
[1029, 1094, 1125, 1278],
[1029, 1094, 1182, 1221, 1242, 1505],
[1029, 1094, 1278, 1298],
[1029, 1094, 1298],
[1029, 1112, 1125, 1298, 1516],
[1029, 1112, 1125, 1505],
[1029, 1112, 1505],
[1029, 1125],
[1029, 1125],
[1029, 1125, 1138],
[1029, 1138, 1188, 1514, 1517],
[1029, 1138, 1242, 1317, 1505, 1525],
[1029, 1242],
[1029, 1242],
[1029, 1242, 1270, 1524],
[1029, 1242, 1370, 1505],
[1029, 1298],
[1029, 1298, 1505],
[1029, 1317],
[1029, 1505],
[1029, 1505],
[1029, 1505, 1525],
[1038, 1076, 1177, 1182],
[1045, 1048, 1097, 1100],
[1046, 1125, 1182, 1242, 1278],
[1049],
[1049],
[1049],
[1049],
[1049],
[1049],
[1049],
[1049],
[1049]
];
$po=new ProductionOptimizer($tickets);
$start = microtime(TRUE);
$end = microtime(TRUE);
echo "Current Memory Usage: ".humanReadableMemory(memory_get_usage()).PHP_EOL;
echo "Peak Memory Usage: ".humanReadableMemory(memory_get_peak_usage()).PHP_EOL;
echo "Starting Iterations and Combination Testing...".PHP_EOL;
$rankedOutput=[];
$start = microtime(TRUE);
for ($i=0;$i<3;$i++) {
$matchCountArray=[];$bestChoice=0;$bestChoiceId=-1;
foreach ($po->getCombinationsIterator() as $comboTest){
$combinationString=implode(",",$comboTest);
$matchCountArray[$combinationString]=0;
$comboTestSet=new Set($comboTest);
foreach ($tickets as $ticketIdx=>$ticketElements) {
$ticketElementsSet = new Set($ticketElements);
$testsArray[$combinationString]+=($comboTestSet->contains(...$ticketElements) ? 1 : 0);
}
if ($matchCountArray[$combinationString]>$bestChoice) {
$bestChoice = $matchCountArray[$combinationString];
$bestChoiceId=$combinationString;
} else {
//trying to save memory
unset($matchCountArray[$combinationString]);
}
}
$currentBestChoiceSet=new Set(explode(",",$bestChoiceId));
$currentUniverseSet=$po->getSet()->copy();
for($tmpJ=0;$tmpJ<$currentUniverseSet->count();$tmpJ++){
$testAgainstSet=$currentUniverseSet->get($tmpJ);
if ($currentBestChoiceSet->contains(...$testAgainstSet->toArray())){
$currentUniverseSet->remove($testAgainstSet);
}
}
$tickets = [];
foreach ($currentUniverseSet as $singleSet){
$tickets[]=$singleSet->toArray();
}
$po=new ProductionOptimizer($tickets);
$rankedOutput[$i]=["greatest_matching_sequence"=>$bestChoiceId, "coverage_count"=>$bestChoice];
}
echo "RankedOutput:".PHP_EOL;
var_dump($rankedOutput);
echo PHP_EOL;
$end = microtime(TRUE);
echo PHP_EOL."The code took " . ($end - $start) . " seconds to complete.".PHP_EOL;