Array combinatorics in PHP

Question

Consider following array:

$a = [['x'], ['y', 'z', 'w'], ['m', 'n']];

How can generate following array from it:

$output=[
[[x][y][m]],
[[x][z][n]],
[[x][w][m]],
[[x][y][n]],
[[x][z][m]],
[[x][w][n]],
];

I am searching for a more efficient code than mine. (My current code is presented as an answer below)

Answer 1

Here we go. Assuming:

$array = [['x'], ['y', 'z', 'w'], ['m', 'n']];

EDIT: After some performance testing, I concluded the solution I posted before is about 300% slower than OP's code, surely due to nested function call stacking. So here is an improved version of OP's approach, which is around 40% faster:

$count     = array_map('count', $array);
$finalSize = array_product($count);
$arraySize = count($array);
$output    = array_fill(0, $finalSize, []);
$i = 0;
$c = 0;
for (; $i < $finalSize; $i++) {
    for ($c = 0; $c < $arraySize; $c++) {
        $output[$i][] = $array[$c][$i % $count[$c]];
    }
}

It is basically the same code but I used native functions when possible and also took out the loops some functionality that hadn't to be executed on each iteration.

Answer 2

"more efficient code" is such a subjective thing .... ;-)
You could use iterators instead of arrays so the complete result doesn't have to be stored in memory. On the other hand this solution is most likely much slower.

<?php
class PermIterator implements Iterator {
    protected $mi;
    protected $finalSize, $pos;

    public function __construct(array $src) {
        $mi = new MultipleIterator;
        $finalSize = 1;
        foreach ( $src as $a ) {
            $finalSize *= count($a);
            $mi->attachIterator( new InfiniteIterator(new ArrayIterator($a)) );
        }
        $this->mi = $mi;
        $this->finalSize = $finalSize;
        $this->pos = 0;
    }

    public function current() { return $this->mi->current(); }
    public function key() { return $this->mi->key(); }
    public function next() { $this->pos+=1; $this->mi->next(); }
    public function rewind() { $this->pos = 0; $this->mi->rewind(); }
    public function valid() { return ($this->pos < $this->finalSize) && $this->mi->valid(); }
}


$src = $a = [['x'], ['y', 'z', 'w'], ['m', 'n']];
$pi = new PermIterator($src); // <- you can pass this one around instead of the array
foreach ( $pi as $e ) {
    echo join(', ', $e), "\n";
}

prints

x, y, m
x, z, n
x, w, m
x, y, n
x, z, m
x, w, n

Or as an array (object) where you can access each element via an integer offset

<?php
class PermArray implements  ArrayAccess {
    // todo: constraints and error handling - it's just an example
    protected $source;
    protected $size;

    public function __construct($source) {
        $this->source = $source;
        $this->size = 1;
        foreach ( $source as $a ) {
            $this->size *= count($a);
        }
    }
    public function count() { return $this->size; }

    public function offsetExists($offset) { return is_int($offset) && $offset < $this->size; }
    public function offsetGet($offset) {
        $rv = array();
        for ($c = 0; $c < count($this->source); $c++) {
          $index = ($offset + $this->size) % count($this->source[$c]);
          $rv[] = $this->source[$c][$index];
        }
        return $rv;
    }

    public function offsetSet($offset, $value ){}
    public function offsetUnset($offset){}
}

$pa = new PermArray( [['x'], ['y', 'z', 'w'], ['m', 'n']] );
$cnt = $pa->count();
for($i=0; $i<$cnt; $i++) {
    echo join(', ', $pa[$i]), "\n";
}