Trovare tutte le permutazioni all'interno di un array PHP nidificato

Question

Dato il seguente esempio di array, come posso trovare tutte le permutazioni dei tempi disponibili in modo tale che la quantità necessaria sia soddisfatta? In altre parole, l'array seguente dovrebbe produrre quanto segue:

  

Disponibile il 14/05/2008 dalle 08:00 alle 08:10 utilizzando le risorse 10 e 13

     

Disponibile il 14/05/2008 dalle 08:10 alle 08:20 utilizzando le risorse 10 e 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

Quello che stai cercando non ha nulla a che fare con le permutazioni. Stai valutando la sovrapposizione di periodi di tempo e vedo due approcci:

1. Pre-elabora tutti i tuoi periodi di tempo in una sequenza temporale, quindi esegui una query sulla sequenza temporale o
2. Scansione parallela di tutti i blocchi di risorse.

La prima opzione richiede più memoria ma è più facile da capire; il secondo è potenzialmente meno affamato di risorse ma molto più complicato da programmare. Entrambi trarrebbero beneficio dalla riduzione al minimo dell'insieme di dati da prendere in considerazione, vale a dire limitare il periodo di tempo previsto.

L'opzione n. 1 è la seguente (implementata 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;
 Quello che stai cercando non ha nulla a che fare con le permutazioni. Stai valutando la sovrapposizione di periodi di tempo e vedo due approcci: 


 Pre-elabora tutti i tuoi periodi di tempo in una sequenza temporale, quindi esegui una query sulla sequenza temporale o 
 Scansione parallela di tutti i blocchi di risorse. 


 La prima opzione richiede più memoria ma è più facile da capire; il secondo è potenzialmente meno affamato di risorse ma molto più complicato da programmare. Entrambi trarrebbero beneficio dalla riduzione al minimo dell'insieme di dati da prendere in considerazione, vale a dire limitare il periodo di tempo previsto. 

 L'opzione n. 1 è la seguente (implementata in OO PHP5): 

<*>pre = "\n<p>";
 Quello che stai cercando non ha nulla a che fare con le permutazioni. Stai valutando la sovrapposizione di periodi di tempo e vedo due approcci: 


 Pre-elabora tutti i tuoi periodi di tempo in una sequenza temporale, quindi esegui una query sulla sequenza temporale o 
 Scansione parallela di tutti i blocchi di risorse. 


 La prima opzione richiede più memoria ma è più facile da capire; il secondo è potenzialmente meno affamato di risorse ma molto più complicato da programmare. Entrambi trarrebbero beneficio dalla riduzione al minimo dell'insieme di dati da prendere in considerazione, vale a dire limitare il periodo di tempo previsto. 

 L'opzione n. 1 è la seguente (implementata in 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
            ? "{
 Quello che stai cercando non ha nulla a che fare con le permutazioni. Stai valutando la sovrapposizione di periodi di tempo e vedo due approcci: 


 Pre-elabora tutti i tuoi periodi di tempo in una sequenza temporale, quindi esegui una query sulla sequenza temporale o 
 Scansione parallela di tutti i blocchi di risorse. 


 La prima opzione richiede più memoria ma è più facile da capire; il secondo è potenzialmente meno affamato di risorse ma molto più complicato da programmare. Entrambi trarrebbero beneficio dalla riduzione al minimo dell'insieme di dati da prendere in considerazione, vale a dire limitare il periodo di tempo previsto. 

 L'opzione n. 1 è la seguente (implementata in OO PHP5): 

<*>pre}Available from $st to $fn using resources ($res){
 Quello che stai cercando non ha nulla a che fare con le permutazioni. Stai valutando la sovrapposizione di periodi di tempo e vedo due approcci: 


 Pre-elabora tutti i tuoi periodi di tempo in una sequenza temporale, quindi esegui una query sulla sequenza temporale o 
 Scansione parallela di tutti i blocchi di risorse. 


 La prima opzione richiede più memoria ma è più facile da capire; il secondo è potenzialmente meno affamato di risorse ma molto più complicato da programmare. Entrambi trarrebbero beneficio dalla riduzione al minimo dell'insieme di dati da prendere in considerazione, vale a dire limitare il periodo di tempo previsto. 

 L'opzione n. 1 è la seguente (implementata in OO PHP5): 

<*>post}"
            : "{
 Quello che stai cercando non ha nulla a che fare con le permutazioni. Stai valutando la sovrapposizione di periodi di tempo e vedo due approcci: 


 Pre-elabora tutti i tuoi periodi di tempo in una sequenza temporale, quindi esegui una query sulla sequenza temporale o 
 Scansione parallela di tutti i blocchi di risorse. 


 La prima opzione richiede più memoria ma è più facile da capire; il secondo è potenzialmente meno affamato di risorse ma molto più complicato da programmare. Entrambi trarrebbero beneficio dalla riduzione al minimo dell'insieme di dati da prendere in considerazione, vale a dire limitare il periodo di tempo previsto. 

 L'opzione n. 1 è la seguente (implementata in OO PHP5): 

<*>pre}Available from $st to $fn using any $needed of resources ($res){
 Quello che stai cercando non ha nulla a che fare con le permutazioni. Stai valutando la sovrapposizione di periodi di tempo e vedo due approcci: 


 Pre-elabora tutti i tuoi periodi di tempo in una sequenza temporale, quindi esegui una query sulla sequenza temporale o 
 Scansione parallela di tutti i blocchi di risorse. 


 La prima opzione richiede più memoria ma è più facile da capire; il secondo è potenzialmente meno affamato di risorse ma molto più complicato da programmare. Entrambi trarrebbero beneficio dalla riduzione al minimo dell'insieme di dati da prendere in considerazione, vale a dire limitare il periodo di tempo previsto. 

 L'opzione n. 1 è la seguente (implementata in OO PHP5): 

<*>post}"
        );
    }
}

?>

Answer 2

Si chiama permutazioni, con una bella parola. Dai un'occhiata a questo post sul blog , per un'implementazione generica.