Trouver toutes les permutations dans un tableau PHP imbriqué

https://stackoverflow.com/questions/302559

08-07-2019
|

Question

Étant donné le tableau exemple suivant, comment puis-je trouver toutes les permutations de temps disponibles de sorte que la quantité nécessaire soit satisfaite? En d'autres termes, le tableau suivant devrait produire les éléments suivants:

Disponible le 2008-05-14 de 08h00 à 08h10 en utilisant les ressources 10 et 13

Disponible le 2008-05-14 de 08h10 à 08h20 en utilisant les ressources 10 et 13

La solution

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

Pré-traitez toutes vos périodes dans une chronologie, puis interrogez-la, ou
Parcourez tous vos blocs de ressources en parallèle.

La première option nécessite 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 gagneraient à minimiser l'ensemble de données à prendre en compte, c'est-à-dire à limiter la période cible.

L'option n ° 1 est la suivante (implémentée dans 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;
 Ce que vous recherchez n'a rien à voir avec des permutations. Vous envisagez des périodes qui se chevauchent et je vois deux approches: 


 Pré-traitez toutes vos périodes dans une chronologie, puis interrogez-la, ou 
 Parcourez tous vos blocs de ressources en parallèle. 


 La première option nécessite 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 gagneraient à minimiser l'ensemble de données à prendre en compte, c'est-à-dire à limiter la période cible. 

 L'option n ° 1 est la suivante (implémentée dans OO PHP5): 

<*>pre = "\n<p>";
 Ce que vous recherchez n'a rien à voir avec des permutations. Vous envisagez des périodes qui se chevauchent et je vois deux approches: 


 Pré-traitez toutes vos périodes dans une chronologie, puis interrogez-la, ou 
 Parcourez tous vos blocs de ressources en parallèle. 


 La première option nécessite 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 gagneraient à minimiser l'ensemble de données à prendre en compte, c'est-à-dire à limiter la période cible. 

 L'option n ° 1 est la suivante (implémentée dans OO PHP5): 

<*>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
            ? "{ Ce que vous recherchez n'a rien à voir avec des permutations. Vous envisagez des périodes qui se chevauchent et je vois deux approches: 


 Pré-traitez toutes vos périodes dans une chronologie, puis interrogez-la, ou 
 Parcourez tous vos blocs de ressources en parallèle. 


 La première option nécessite 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 gagneraient à minimiser l'ensemble de données à prendre en compte, c'est-à-dire à limiter la période cible. 

 L'option n ° 1 est la suivante (implémentée dans OO PHP5): 

<*>pre}Available from $st to $fn using resources ($res){ Ce que vous recherchez n'a rien à voir avec des permutations. Vous envisagez des périodes qui se chevauchent et je vois deux approches: 


 Pré-traitez toutes vos périodes dans une chronologie, puis interrogez-la, ou 
 Parcourez tous vos blocs de ressources en parallèle. 


 La première option nécessite 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 gagneraient à minimiser l'ensemble de données à prendre en compte, c'est-à-dire à limiter la période cible. 

 L'option n ° 1 est la suivante (implémentée dans OO PHP5): 

<*>post}"
            : "{ Ce que vous recherchez n'a rien à voir avec des permutations. Vous envisagez des périodes qui se chevauchent et je vois deux approches: 


 Pré-traitez toutes vos périodes dans une chronologie, puis interrogez-la, ou 
 Parcourez tous vos blocs de ressources en parallèle. 


 La première option nécessite 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 gagneraient à minimiser l'ensemble de données à prendre en compte, c'est-à-dire à limiter la période cible. 

 L'option n ° 1 est la suivante (implémentée dans OO PHP5): 

<*>pre}Available from $st to $fn using any $needed of resources ($res){ Ce que vous recherchez n'a rien à voir avec des permutations. Vous envisagez des périodes qui se chevauchent et je vois deux approches: 


 Pré-traitez toutes vos périodes dans une chronologie, puis interrogez-la, ou 
 Parcourez tous vos blocs de ressources en parallèle. 


 La première option nécessite 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 gagneraient à minimiser l'ensemble de données à prendre en compte, c'est-à-dire à limiter la période cible. 

 L'option n ° 1 est la suivante (implémentée dans OO PHP5): 

<*>post}"
        );
    }
}

?>

Autres conseils

Cela s'appelle des permutations, avec un beau mot. Consultez cette publication de blog pour une implémentation générique.

Licencié sous: CC-BY-SA avec attribution

Non affilié à StackOverflow