İç içe bir PHP Array içindeki tüm permütasyon bulma

2 Cevap php

Aşağıdaki örnek bir dizi verilen, nasıl ben amountNeeded memnun olduğunu mevcut kez tüm permütasyon gibi bulabilirim? Diğer deyişle takip dizi aşağıdaki üretmek olmalıdır:

08:10 kullanılarak kaynak 10 ve 13 08:00 dan 2008/05/14 üzerinde kullanılabilir

08:20 kullanılarak kaynak 10 ve 13'e 08:10 dan 2008/05/14 üzerinde kullanılabilir

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
                                )
                    ...
");

2 Cevap

Ne arıyorsun permütasyon ile ilgisi yoktur. Siz zaman aralıklarını örtüşen düşünüyor ve ben iki yaklaşım bakın:

  1. Bir zaman çizelgesi içine pre-process her zaman-dönemleri, daha sonra zaman çizelgesini sorgulamak, ya da
  2. Paralel olarak tüm kaynak-blokları ile tarayın.

İlk seçenek daha fazla bellek alır ama anlamak kolaydır; ikinci potansiyel olarak daha az kaynak aç ama çok daha karmaşık bir program için. Her ikisi de dikkate alınması gereken veri kümesini en aza yararlanacak, yani hedef süresini sınırlayabilir.

Şöyle Seçenek # 1 (OO PHP5'ta uygulanan) olan:

<?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}"
    	);
    }
}

?>

Bu güzel bir kelime ile, permütasyon denir. Genel bir uygulama için, this blog post bakabilirsiniz.

etiketler