kaszu solution isn't complete. You could probably tack on an intelligent sort algorithm to it because all the permutations are listed, just not in the right order.
By contrast my solution generates the numbers in the desired order initially. With a bit of fiddling you could set up a permutation iterator that would feed the numbers to you as they were generated.
Code: Select all
<?php
/**
* Essenital rubification
*/
class Ole_ArrayObject extends ArrayObject
{
public function last() {
return self::get($this->count() - 1);
}
public function first() {
return self::get(0);
}
public function get($key, $default = null) {
return isset($this[$key]) ? $this[$key] : $default;
}
}
/**
* Reduces requirement for null handling logic. Swallows all calls.
*/
class NullClass
{
public function __call($name, $param) { }
}
/**
* Observer like iterator. It iteratates over a set and when it hits the end it
* iterates the linked
*
*/
class Ole_WrappingRecursiveIterator implements RecursiveIterator, Countable
{
/**
* The array this will iterate over
*
* @var array
*/
private $_array;
/**
* This iterator will increment it's children after each full cycle of $_array.
*
* @var Iterator
*/
private $_children;
/**
* Current position in the array
*
* @var int
*/
private $_key;
/**
* Whether this Iterator has been incremented yet
*
* @var bool
*/
private $_fresh = true;
/**
* @param array $array to iterate over
* @param Iterator $children children to increment after each full cycle of $array
*/
public function __construct($array, RecursiveIterator $children = null) {
$this->_array = $array;
if (!$children) {
$children = new NullClass();
}
$this->_children = $children;
$this->_key = 0;
}
public function getChildren() {
return $this->_children;
}
public function hasChildren() {
return !$this->_children instanceof NullClass;
}
public function count() {
return count($this->_array);
}
public function current() {
return $this->_array[$this->_key];
}
public function __tostring() {
return (string)$this->current();
}
public function key() {
return $this->_key;
}
public function next() {
$this->_fresh = false;
if ($this->_key < $this->count() - 1) {
++$this->_key;
} else {
$this->_children->next();
$this->_key = 0; // Wrap the incrementation, impossible to overflow
}
return $this;
}
public function valid() {
return $this->_key === 0 && !$this->_fresh;
}
public function rewind() {
$this->_key = 0;
$this->_fresh = true;
$this->_children->rewind();
}
}
function permutations($set)
{
$iteratorSet = new Ole_ArrayObject(array());
$out = array();
foreach ($set as $k => $v) {
$iteratorSet->append(new Ole_WrappingRecursiveIterator($set, $iteratorSet->last()));
while (!$iteratorSet->first()->valid()) {
$permutation = array();
foreach ($iteratorSet as $iterator) {
$permutation[] = $iterator->current();
}
$out[] = $permutation;
$iteratorSet->last()->next();
}
$iteratorSet->last()->rewind();
}
return $out;
}
echo '<pre>';
foreach (permutations(array(1, 2, 3)) as $permutation) {
echo implode($permutation) . PHP_EOL;
}
Crux:
The iterators are linked. When one is created it can be given the responsibility of incrementing another iterator but only when it's completes a full cycle of iteration and has to wrap itself around to the beginning again. This is very much like a linked-list chain and could theoretically be very long indeed if required.
Example:
A iterates over array(1, 2, 3) and is responsible for increment only itself
B iterates over array(1, 2, 3) and is responsible for incrementing itself and A
C iterates over array(1, 2, 3) and is responsible for incrementing itself and B
Initially all iterators' current values are 1.
A:1, B:1, C:1
The last is incremented.
A:1, B:1, C:2
The last is incremented.
A:3, B:1, C:3
The last is incremented. C wraps around and increments B
A:1, B:2, C:1
And so on and so forth. The remainder of the functionality is delivered by adding iterators to an "iterator set" that can be dynamically changed - so this can be based upon the data set itself.
The SPL contains a RecursiveIterator interface which I have used but regrettably it uses the term "children" which I find very confusing because it leaves the direction of recursion to be completely ambiguous.