Encontrar todas las permutaciones dentro de una matriz PHP anidada

Question

Dada la siguiente matriz de muestra, ¿cómo puedo encontrar todas las permutaciones de tiempos disponibles de modo que se satisfaga la cantidad Necesaria? En otras palabras, la siguiente matriz debería producir lo siguiente:

  

Disponible el 14/05/2008 de 08:00 a 08:10 utilizando los recursos 10 y 13

     

Disponible el 14/05/2008 de 08:10 a 08:20 utilizando los recursos 10 y 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

Lo que estás buscando no tiene nada que ver con las permutaciones. Está considerando períodos de tiempo superpuestos, y veo dos enfoques:

1. Preprocese todos sus períodos de tiempo en una línea de tiempo, luego consulte la línea de tiempo o
2. Escanee todos sus bloques de recursos en paralelo.

La primera opción requiere más memoria pero es más fácil de entender; el segundo potencialmente consume menos recursos pero es mucho más complicado de programar. Ambos se beneficiarían de minimizar el conjunto de datos a considerar, es decir, limitar el período de tiempo objetivo.

La opción # 1 es la siguiente (implementada 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;
 Lo que estás buscando no tiene nada que ver con las permutaciones. Está considerando períodos de tiempo superpuestos, y veo dos enfoques: 


 Preprocese todos sus períodos de tiempo en una línea de tiempo, luego consulte la línea de tiempo o 
 Escanee todos sus bloques de recursos en paralelo. 


 La primera opción requiere más memoria pero es más fácil de entender; el segundo potencialmente consume menos recursos pero es mucho más complicado de programar. Ambos se beneficiarían de minimizar el conjunto de datos a considerar, es decir, limitar el período de tiempo objetivo. 

 La opción # 1 es la siguiente (implementada en OO PHP5): 

<*>pre = "\n<p>";
 Lo que estás buscando no tiene nada que ver con las permutaciones. Está considerando períodos de tiempo superpuestos, y veo dos enfoques: 


 Preprocese todos sus períodos de tiempo en una línea de tiempo, luego consulte la línea de tiempo o 
 Escanee todos sus bloques de recursos en paralelo. 


 La primera opción requiere más memoria pero es más fácil de entender; el segundo potencialmente consume menos recursos pero es mucho más complicado de programar. Ambos se beneficiarían de minimizar el conjunto de datos a considerar, es decir, limitar el período de tiempo objetivo. 

 La opción # 1 es la siguiente (implementada en 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
            ? "{
 Lo que estás buscando no tiene nada que ver con las permutaciones. Está considerando períodos de tiempo superpuestos, y veo dos enfoques: 


 Preprocese todos sus períodos de tiempo en una línea de tiempo, luego consulte la línea de tiempo o 
 Escanee todos sus bloques de recursos en paralelo. 


 La primera opción requiere más memoria pero es más fácil de entender; el segundo potencialmente consume menos recursos pero es mucho más complicado de programar. Ambos se beneficiarían de minimizar el conjunto de datos a considerar, es decir, limitar el período de tiempo objetivo. 

 La opción # 1 es la siguiente (implementada en OO PHP5): 

<*>pre}Available from $st to $fn using resources ($res){
 Lo que estás buscando no tiene nada que ver con las permutaciones. Está considerando períodos de tiempo superpuestos, y veo dos enfoques: 


 Preprocese todos sus períodos de tiempo en una línea de tiempo, luego consulte la línea de tiempo o 
 Escanee todos sus bloques de recursos en paralelo. 


 La primera opción requiere más memoria pero es más fácil de entender; el segundo potencialmente consume menos recursos pero es mucho más complicado de programar. Ambos se beneficiarían de minimizar el conjunto de datos a considerar, es decir, limitar el período de tiempo objetivo. 

 La opción # 1 es la siguiente (implementada en OO PHP5): 

<*>post}"
            : "{
 Lo que estás buscando no tiene nada que ver con las permutaciones. Está considerando períodos de tiempo superpuestos, y veo dos enfoques: 


 Preprocese todos sus períodos de tiempo en una línea de tiempo, luego consulte la línea de tiempo o 
 Escanee todos sus bloques de recursos en paralelo. 


 La primera opción requiere más memoria pero es más fácil de entender; el segundo potencialmente consume menos recursos pero es mucho más complicado de programar. Ambos se beneficiarían de minimizar el conjunto de datos a considerar, es decir, limitar el período de tiempo objetivo. 

 La opción # 1 es la siguiente (implementada en OO PHP5): 

<*>pre}Available from $st to $fn using any $needed of resources ($res){
 Lo que estás buscando no tiene nada que ver con las permutaciones. Está considerando períodos de tiempo superpuestos, y veo dos enfoques: 


 Preprocese todos sus períodos de tiempo en una línea de tiempo, luego consulte la línea de tiempo o 
 Escanee todos sus bloques de recursos en paralelo. 


 La primera opción requiere más memoria pero es más fácil de entender; el segundo potencialmente consume menos recursos pero es mucho más complicado de programar. Ambos se beneficiarían de minimizar el conjunto de datos a considerar, es decir, limitar el período de tiempo objetivo. 

 La opción # 1 es la siguiente (implementada en OO PHP5): 

<*>post}"
        );
    }
}

?>

Answer 2

Se llama permutaciones, con una buena palabra. Eche un vistazo a esta publicación de blog , para una implementación genérica.