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

Question

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

  

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

     

Доступно 2008-05-14 с 08:10 до 08: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 выглядит следующим образом (реализован в 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;
 То, что вы ищете, не имеет ничего общего с перестановками. Вы рассматриваете перекрывающиеся периоды времени, и я вижу два подхода: 

<Ол>
 Предварительно обработайте все свои периоды времени на временной шкале, затем запросите временную шкалу или 
 Сканируйте все свои блоки ресурсов параллельно. 


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

 Вариант № 1 выглядит следующим образом (реализован в OO PHP5): 

<*>pre = "\n<p>";
 То, что вы ищете, не имеет ничего общего с перестановками. Вы рассматриваете перекрывающиеся периоды времени, и я вижу два подхода: 

<Ол>
 Предварительно обработайте все свои периоды времени на временной шкале, затем запросите временную шкалу или 
 Сканируйте все свои блоки ресурсов параллельно. 


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

 Вариант № 1 выглядит следующим образом (реализован в 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
            ? "{
 То, что вы ищете, не имеет ничего общего с перестановками. Вы рассматриваете перекрывающиеся периоды времени, и я вижу два подхода: 

<Ол>
 Предварительно обработайте все свои периоды времени на временной шкале, затем запросите временную шкалу или 
 Сканируйте все свои блоки ресурсов параллельно. 


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

 Вариант № 1 выглядит следующим образом (реализован в OO PHP5): 

<*>pre}Available from $st to $fn using resources ($res){
 То, что вы ищете, не имеет ничего общего с перестановками. Вы рассматриваете перекрывающиеся периоды времени, и я вижу два подхода: 

<Ол>
 Предварительно обработайте все свои периоды времени на временной шкале, затем запросите временную шкалу или 
 Сканируйте все свои блоки ресурсов параллельно. 


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

 Вариант № 1 выглядит следующим образом (реализован в OO PHP5): 

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

<Ол>
 Предварительно обработайте все свои периоды времени на временной шкале, затем запросите временную шкалу или 
 Сканируйте все свои блоки ресурсов параллельно. 


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

 Вариант № 1 выглядит следующим образом (реализован в OO PHP5): 

<*>pre}Available from $st to $fn using any $needed of resources ($res){
 То, что вы ищете, не имеет ничего общего с перестановками. Вы рассматриваете перекрывающиеся периоды времени, и я вижу два подхода: 

<Ол>
 Предварительно обработайте все свои периоды времени на временной шкале, затем запросите временную шкалу или 
 Сканируйте все свои блоки ресурсов параллельно. 


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

 Вариант № 1 выглядит следующим образом (реализован в OO PHP5): 

<*>post}"
        );
    }
}

?>

Answer 2

Это называется перестановкой, с хорошим словом. Ознакомьтесь с этим сообщением в блоге , чтобы ознакомиться с общей реализацией.