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)
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.
"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";
}
<?php
function array_permutation(array $a)
{
$count = array_map('count', $a);
$finalSize = 1;
foreach ($count as $val) {
$finalSize *= $val;
}
$output = [];
for ($i = 0; $i < $finalSize; $i++) {
$output[$i] = [];
for ($c = 0; $c < count($a); $c++) {
$index = ($i + $finalSize) % $count[$c];
array_push($output[$i], $a[$c][$index]);
}
}
return $output;
}
$a = [['x'], ['y', 'z', 'w'], ['m', 'n']];
$output= array_permutation($a);
It appears as though none of the answers, including the accepted one, will work if there are two arrays of the same length. I have personally tested the accepted answer and found this to be the case, and judging from the comments on the other two, they have the same issue.
I had to implement this algorithm recently, so I will post my solution. This solution is designed to work with associative arrays and also supports sets of columns that will be grouped together in the output and not permuted against each other; this is useful if any of the columns contain related information. If you don't need these features it should be fairly trivial to modify this algorithm to support your needs.
// the input column sets to be permuted
$column_sets = [
[ //set 1
['Column 1' => 'c1v1']
],
[ //set 2
['column 2' => 'c2v1', 'Column 3' => 'c3v1'],
['column 2' => 'c2v2', 'Column 3' => 'c3v2'],
],
[ //set 3
['Column 4' => 'c4v1', 'Column 5' => 'c5v1'],
['Column 4' => 'c4v2', 'Column 5' => 'c5v2'],
],
[ //set 4
['Column 6' => 'c6v1', 'Column 7' => 'c7v1'],
['Column 6' => 'c6v2', 'Column 7' => 'c7v2'],
['Column 6' => 'c6v3', 'Column 7' => 'c7v3'],
],
[ //set 5
['Column 8' => 'c8v1', 'Column 9' => 'c9v1'],
['Column 8' => 'c8v2', 'Column 9' => 'c9v2'],
['Column 8' => 'c8v3', 'Column 9' => 'c9v3'],
],
];
// copy the first set into the output to start
$output_rows = $column_sets[0];
foreach ($column_sets as $column_set) {
// save the current state of the rows for use within this loop
$current_output = $output_rows;
// calculate the number of permutations necessary to combine the output rows with the current column set
$permutations = count($output_rows) * count($column_set);
for ($permutation=0; $permutation < $permutations; $permutation++) {
// if the current permutation index is grater than the number of rows in the output,
// then copy a row from the pre-permutation output rows, repeating as necessary
if ($permutation > count($output_rows) - 1) {
$output_rows[] = $current_output[$permutation % count($current_output)];
}
// copy the columns from the column set
foreach ($column_set[0] as $key => $value) {
$output_rows[$permutation][$key] = $column_set[intval($permutation / count($current_output)) % count($column_set)][$key];
}
}
}
echo "After Permutaion:\n";
echo implode("\t", array_keys($output_rows[0])) . PHP_EOL;
foreach ($output_rows as $row) {
echo implode("\t", array_values($row)) . PHP_EOL;
}
[x][y][z]
[x][z][y]
[y][x][z]
[y][z][x]
[z][x][y]
[z][y][x]
I think your problem is not permutation but rather combinatorics because if permutation your code will output what is written above if given the array of {x,y,z} the formula for permutation is that n!/(n-1)! in this case it is 6. so six permutations.
