Die Suche nach allen Permutationen innerhalb einer verschachtelten PHP Array

Question

Bei dem folgende Beispiel Array, wie kann ich alle Permutationen Mal finde zur Verfügung, so dass die amountNeeded zufrieden ist? In anderen Worten sollte die Folge Array erzeugen die folgende:

  

Auf 2008-05-14 8.00 bis 08.10 Uhr unter Verwendung von Ressourcen 10 und 13

     

Auf 2008-05-14 8.10 bis 08.20 Uhr unter Verwendung von Ressourcen 10 und 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

Was Sie suchen, hat nichts mit Permutationen zu tun. Sie erwägen Zeitperioden überlappen, und ich sehe zwei Ansätze:

1. Pre-Prozess alle Zeitperioden in einer Zeitleiste, dann abfragen, um die Timeline, oder
2. Scan durch alle Ressource-Blöcke parallel.

Die erste Option braucht mehr Speicher, aber ist leichter zu verstehen; die zweite ist möglicherweise weniger ressourcen-hungrig, aber viel komplizierter zu programmieren. Beide würden aus der Minimierung der Datenmenge profitieren in Betracht gezogen werden, dh die Zielzeitdauer begrenzen.

Option # 1 ist wie folgt (implementiert 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;
$_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

Es ist Permutationen genannt, mit einem feinen Wort. Hier finden Sie aktuelle diese Blog-Post für eine generische Implementierung.