Recherche de toutes les permutations dans un tableau PHP imbriqué

Question

Étant donné le tableau d'échantillons suivant, comment puis-je trouver toutes les permutations d'heures disponibles, de sorte que amountNeeded soit satisfait? En d'autres termes autres le tableau de suivi devrait produire les éléments suivants:

Disponible sur 2008-05-14 8:00-8:10 en utilisant des ressources 10 et 13

Disponible sur 2008-05-14 de 08 : 10 à 08:20 à l'aide des ressources 10 et 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

Ce que vous cherchez n'a rien à voir avec permutations. Vous envisagez de périodes qui se chevauchent, et je vois deux approches:

1. prétraiter tous vos temps-périodes dans une ligne de temps, puis interroger la ligne de temps, ou
2. parcourons toutes vos ressources blocs en parallèle.

La première option prend plus de mémoire mais est plus facile à comprendre; la seconde est potentiellement moins gourmande en ressources mais beaucoup plus compliquée à programmer. Les deux auraient avantage à minimiser l'ensemble de données à prendre en compte, c'est-à-dire à limiter la période de temps cible.

Option n ° 1 est la suivante (mise en œuvre en 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}" 
     ); 
    } 
} 

?> 

Answer 2

Il appelle les permutations, avec un beau mot. Jetez un oeil à this blog post, pour une implémentation générique.