Finding all permutations within a nested PHP Array
-
08-07-2019 - |
Question
Given the following sample array, how can I find all permutations of times available such that the amountNeeded is satisfied? In others words the follow array should produce the following:
Available on 2008-05-14 from 08:00 to 08:10 using resource 10 and 13
Available on 2008-05-14 from 08:10 to 08:20 using resource 10 and 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
)
...
");
Solution
What you are looking for has nothing to do with permutations. You are considering overlapping time periods, and I see two approaches:
- Pre-process all your time-periods into a timeline, then query the timeline, or
- Scan through all your resource-blocks in parallel.
The first option takes more memory but is easier to understand; the second is potentially less resource-hungry but much more complicated to program. Both would benefit from minimizing the dataset to be considered, ie limit the target time period.
Option #1 is as follows (implemented in 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}"
);
}
}
?>
OTHER TIPS
It's called permutations, with a fine word. Have a look at this blog post, for a generic implementation.