Finding all permutations within a nested PHP Array

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
                            )
                ...

");

Answer 1

It's called permutations, with a fine word. Have a look at this blog post, for a generic implementation.

Answer 2

What you are looking for has nothing to do with permutations. You are considering overlapping time periods, and I see two approaches:

1. Pre-process all your time-periods into a timeline, then query the timeline, or
2. 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}"
     );
    }
}

?>