查找嵌套PHP数组中的所有排列

Question

给定以下示例数组，如何找到所有可用时间的排列，以满足amountNeeded？换句话说，follow数组应该产生以下结果：

  

2008年4月14日08:00至08:10使用资源10和13

     

使用资源10和13

于2008-05-14 08:10至08:20提供

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. 将所有时间段预处理到时间轴，然后查询时间线，或
2. 并行扫描所有资源块。

第一个选项需要更多内存但更容易理解;第二种可能是资源不足，但编程要复杂得多。两者都将受益于最小化要考虑的数据集，即限制目标时间段。

选项＃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;
$_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

它被称为排列，用一个好词。有关通用实施，请查看此博客文章。