Поиск всех перестановок внутри вложенного массива PHP

Question

Учитывая следующий массив образцов, как я могу найти все перестановки времени, доступные для того, чтобы удовлетворять количеству запросов? В других словах массив последующий должен произвести следующие действия:

Доступно 2008-05-14 с 08:00 до 08:10 с использованием ресурсов 10 и 13

Доступно 2008-05-14 из 08 : 10 до 8:20 с использованием ресурсов 10 и 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

То, что вы ищете, не имеет ничего общего с перестановками. Вы рассматриваете перекрывающиеся периоды времени, и я вижу два подхода:

1. предобработать все временные периодов в сроки, а затем запросить график, или
2. сканирования через все ваши ресурсы блоки параллельно.

Первый вариант занимает больше памяти, но его легче понять; второй потенциально менее ресурсоемкий, но гораздо сложнее программировать. Оба могут выиграть от минимизации рассматриваемого набора данных, то есть ограничить целевой период времени.

Вариант № 1 состоит в следующем (реализован в ОО 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}" 
     ); 
    } 
} 

?> 

Answer 2

Это называется перестановками, с прекрасным словом. Посмотрите на this blog post, для общей реализации.