Finding all permutations within a nested PHP Array

Given the following sample array, how can I find all permutations of times available such that the amountNeeded is satisfied? In others words the follow array should produce the following:

Available on 2008-05-14 from 08:00 to 08:10 using resource 10 and 13

Available on 2008-05-14 from 08:10 to 08:20 using resource 10 and 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
                                )
                    ...
");

Answers


What you are looking for has nothing to do with permutations. You are considering overlapping time periods, and I see two approaches:

  1. Pre-process all your time-periods into a timeline, then query the timeline, or
  2. Scan through all your resource-blocks in parallel.

The first option takes more memory but is easier to understand; the second is potentially less resource-hungry but much more complicated to program. Both would benefit from minimizing the dataset to be considered, ie limit the target time period.

Option #1 is as follows (implemented 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}"
    	);
    }
}

?>

It's called permutations, with a fine word. Have a look at this blog post, for a generic implementation.


Need Your Help

Complex query join in ebean

mysql sql database ebean

I have the following schema.

About UNIX Resources Network

Original, collect and organize Developers related documents, information and materials, contains jQuery, Html, CSS, MySQL, .NET, ASP.NET, SQL, objective-c, iPhone, Ruby on Rails, C, SQL Server, Ruby, Arrays, Regex, ASP.NET MVC, WPF, XML, Ajax, DataBase, and so on.