Encontrando todas as permutações dentro de uma matriz PHP aninhada
-
08-07-2019 - |
Pergunta
Dada a seguinte matriz de amostra, como posso encontrar todas as permutações de vezes disponíveis de modo que o valor necessário seja satisfeito? Em outras palavras, a matriz a seguir deve produzir o seguinte:
Disponível em 2008-05-14 das 08:00 às 08:10 usando o recurso 10 e 13
Disponível em 2008-05-14 de 08:10 às 08:20 usando o recurso 10 e 13
print("Array(
[amountNeeded] => 2
[resources] => Array
(
[0] => Array
(
[resourceID] => 10
[blocks] => Array
(
[0] => Array
(
[availDate] => 2008-05-14
[startTime] => 08:00
[endTime] => 08:10
)
[1] => Array
(
[availDate] => 2008-05-14
[startTime] => 08:10
[endTime] => 08:20
)
[2] => Array
(
[availDate] => 2008-05-14
[startTime] => 08:20
[endTime] => 08:30
)
...
[1] => Array
(
[resourceID] => 13
[blocks] => Array
(
[0] => Array
(
[availDate] => 2008-05-14
[startTime] => 08:00
[endTime] => 08:10
)
[1] => Array
(
[availDate] => 2008-05-14
[startTime] => 08:10
[endTime] => 08:20
)
[2] => Array
(
[availDate] => 2008-05-14
[startTime] => 08:30
[endTime] => 08:40
)
...
");
Solução
O que você está procurando não tem nada a ver com permutações. Você está pensando em se sobrepor aos períodos de tempo e vejo duas abordagens:
- Pré-processo todos os seus períodos de tempo em uma linha do tempo e depois consulte a linha do tempo ou
- Digitalize todos os seus blocos de recursos em paralelo.
A primeira opção leva mais memória, mas é mais fácil de entender; O segundo é potencialmente menos faminto por recursos, mas muito mais complicado de programar. Ambos se beneficiariam de minimizar o conjunto de dados a ser considerado, ou seja, limitar o período de tempo alvo.
A opção 1 é a seguinte (implementada no OO PHP5):
<?php
class Resource {
protected $name; // resource ID
protected $start; // start timestamp
protected $finish; // end timestamp
// resource available while $start <= current time < $end
function __construct($n, $sd, $st, $ed, $et) {
$this->name = $n;
$this->start = strtotime("$sd $st");
$this->finish = strtotime("$ed $et");
}
function getID() { return $this->name; }
function getStart() { return $this->start; }
function getEnd() { return $this->finish; }
}
class Timeline {
protected $times; // ordered list of start-times;
protected $resources; // resources available in each timeslot
protected $offs; // iterator offset
function __construct() {
$this->times = array();
$this->resources = array();
$this->offs = 0;
}
// binary search, insert if not found, return index
private function time_ins($time) {
// array is empty?
if (count($this->times) == 0) {
$this->times[0]= $time;
$this->resources[0] = array();
return 0;
}
$min = $lo = 0;
$max = $hi = count($this->times)-1;
// binary search
while($lo <= $hi) {
$mid = ($lo+$hi) >> 1;
if ($this->times[$mid] == $time) {
// already exists - return index
return $mid;
}
elseif ($this->times[$mid] < $time) {
// if value exists, is in upper half of array
$lo = $mid+1;
if ($lo > $max || $this->times[$lo] > $time) {
// $lo points to first value greater than $time
// insert new value at $lo
array_splice($this->times, $lo, 0, $time);
$t = isset($this->resources[$lo-1]) ? $this->resources[$lo-1] : array();
array_splice($this->resources, $lo, 0, $t);
return $lo;
}
}
else {
// if value exists, is in lower half of array
$hi = $mid-1;
if ($hi < $min || $this->times[$hi] < $time) {
// $hi points to first value less than $time
// insert new value at $hi+1
array_splice($this->times, $hi+1, 0, $time);
$t = isset($this->resources[$hi+1]) ? $this->resources[$hi+1] : array();
array_splice($this->resources, $hi+1, 0, $t);
return $hi+1;
}
}
}
}
function Add( $start, $end, $id ) {
$s = $this->time_ins($start);
$e = $this->time_ins($end);
for($i = $s; $i < $e; ++$i)
$this->resources[$i][]= $id;
}
function reset() { $offs = 0; }
function isValid() { return ($this->offs+1 < count($this->times)); } // omit last time (is end-time only)
function next() { $this->offs++; }
function resCount() { return count( $this->resources[ $this->offs ] ); }
function getStart() { return $this->times[$this->offs]; }
function getEnd() { return $this->times[$this->offs + 1]; }
function getRes() { return $this->resources[$this->offs]; }
}
$res = array();
$res[]= new Resource('10', '2008-05-14', '08:00', '2008-05-14', '08:10');
$res[]= new Resource('10', '2008-05-14', '08:10', '2008-05-14', '08:20');
$res[]= new Resource('10', '2008-05-14', '08:20', '2008-05-14', '08:30');
$res[]= new Resource('13', '2008-05-14', '08:00', '2008-05-14', '08:10');
$res[]= new Resource('13', '2008-05-14', '08:10', '2008-05-14', '08:20');
$res[]= new Resource('13', '2008-05-14', '08:30', '2008-05-14', '08:40');
$tl = new Timeline();
foreach($res as $R)
$tl->Add( $R->getStart(), $R->getEnd(), $R->getID() );
$needed = 2;
$_pre = "\n<p>";
$_post = "</p>";
for( $tl->reset(); $tl->isValid(); $tl->next() ) {
$cnt = $tl->resCount();
if ($cnt >= $needed) {
$st = date("Y-m-d H:i", $tl->getStart());
$fn = date("Y-m-d H:i", $tl->getEnd());
$res = join(', ', $tl->getRes());
echo ($cnt == $needed
? "{$_pre}Available from $st to $fn using resources ($res){$_post}"
: "{$_pre}Available from $st to $fn using any $needed of resources ($res){$_post}"
);
}
}
?>
Outras dicas
É chamado de permutações, com uma palavra fina. Dê uma olhada em esta postagem do blog, para uma implementação genérica.