Skip to content

Instantly share code, notes, and snippets.

@flip111

flip111/cartesian.php

Created March 26, 2019 17:45
Show Gist options
  • Save flip111/4c46500ee42a95d08e53312d36acf3d7 to your computer and use it in GitHub Desktop.
Save flip111/4c46500ee42a95d08e53312d36acf3d7 to your computer and use it in GitHub Desktop.
Download ZIP
Cartesian product PHP algorithm benchmark (see comments for results)
Raw
cartesian.php
<?php
$decimals = 2;
// test iterations
$iterations = 1000;
printf("Iterations: %d\n\n", $iterations);
// https://stackoverflow.com/a/6313346/1833322
function cartesian($input) {
$result = array();
while (list($key, $values) = each($input)) {
// If a sub-array is empty, it doesn't affect the cartesian product
if (empty($values)) {
continue;
}
// Seeding the product array with the values from the first sub-array
if (empty($result)) {
foreach($values as $value) {
$result[] = array($key => $value);
}
}
else {
// Second and subsequent input sub-arrays work like this:
// 1. In each existing array inside $product, add an item with
// key == $key and value == first item in input sub-array
// 2. Then, for each remaining item in current input sub-array,
// add a copy of each existing array inside $product with
// key == $key and value == first item of input sub-array
// Store all items to be added to $product here; adding them
// inside the foreach will result in an infinite loop
$append = array();
foreach($result as &$product) {
// Do step 1 above. array_shift is not the most efficient, but
// it allows us to iterate over the rest of the items with a
// simple foreach, making the code short and easy to read.
$product[$key] = array_shift($values);
// $product is by reference (that's why the key we added above
// will appear in the end result), so make a copy of it here
$copy = $product;
// Do step 2 above.
foreach($values as $item) {
$copy[$key] = $item;
$append[] = $copy;
}
// Undo the side effecst of array_shift
array_unshift($values, $product[$key]);
}
// Out of the foreach, we can add to $results now
$result = array_merge($result, $append);
}
}
return $result;
}
// https://stackoverflow.com/a/15973172/1833322
function cartesian2($input) {
$result = array(array());
foreach ($input as $key => $values) {
$append = array();
foreach($result as $product) {
foreach($values as $item) {
$product[$key] = $item;
$append[] = $product;
}
}
$result = $append;
}
return $result;
}
// https://stackoverflow.com/a/6313849/1833322
function inject($elem, $array) {
return array_map(function ($n) use ($elem) { return array_merge((array)$elem, (array)$n); }, $array);
}
function zip2($array1, $array2) {
return array_reduce($array1, function ($v, $n) use ($array2) { return array_merge($v, inject($n, $array2)); }, array());
}
function cartesian_product($array) {
$keys = array_keys($array);
$prod = array_shift($array);
$prod = array_reduce($array, 'zip2', $prod);
return array_map(function ($n) use ($keys) { return array_combine($keys, $n); }, $prod);
}
// https://stackoverflow.com/a/6313849/1833322 (version 2)
function inject2($elem, $array) {
$elem = (array)$elem;
foreach ($array as &$a) {
$a = array_merge($elem, (array)$a);
}
return $array;
}
function zip3($array1, $array2) {
$prod = array();
foreach ($array1 as $a) {
$prod = array_merge($prod, inject2($a, $array2));
}
return $prod;
}
function cartesian_product2($array) {
$keys = array_keys($array);
$prod = array_shift($array);
$prod = array_reduce($array, 'zip3', $prod);
foreach ($prod as &$a) {
$a = array_combine($keys, $a);
}
return $prod;
}
// https://stackoverflow.com/a/39174062/1833322
function cartesian3($a)
{
if ($a)
{
if($u=array_pop($a))
foreach(cartesian($a)as$p)
foreach($u as$v)
yield $p+[count($p)=>$v];
}
else
yield[];
}
// https://stackoverflow.com/a/39174062/1833322 (version 2)
// Not original function, applied small fix !
function acartesian($a)
{
if ($a)
{
$tmp = array_keys($a);
$k=end($tmp);
if($u=array_pop($a))
foreach(acartesian($a)as$p)
foreach($u as$v)
yield $p+[$k=>$v];
}
else
yield[];
}
// https://stackoverflow.com/a/44910370/1833322
function cartesian4(array $input)
{
$result = [[]];
foreach ($input as $key => $values) {
$append = [];
foreach ($values as $value) {
foreach ($result as $data) {
$append[] = $data + [$key => $value];
}
}
$result = $append;
}
return $result;
}
// https://stackoverflow.com/a/15987606/1833322
function getAllVariations($input) {
$result = array();
$cnt = array_product(array_map('count', $input));
$step = 1;
foreach ($input as $key=>$array) {
for ($i=0; $i<$cnt; $i++) {
foreach ($array as $value) {
for ($k=0; $k<$step; $k++) {
$result[$i+$k][$key] = $value;
}
$i += $step;
}
$i--;
}
$step = $step * count($array);
}
return $result;
}
// https://stackoverflow.com/a/6312311/1833322
function cartesian5(array $map) {
$result = array();
$nm = '';
foreach ($map as $name => $a) {
if (empty($result)) {
$result = $a;
$nm = $name;
continue;
}
$res = array();
foreach ($result as $r) {
foreach ($a as $v) {
$myr = $r;
$myv = $v;
if(!is_array($r)) $myr = array($nm => $r);
if(!is_array($v)) $myv = array($name => $v);
$res[] = array_merge($myr, $myv);
}
}
$result = $res;
}
return $result;
}
// https://stackoverflow.com/a/43703941/1833322
function cartezianIterator($inputArray)
{
$maximumPosition = array_map('count', $inputArray);
$position = array_pad([], count($inputArray), 0);
while (false !== ($item = buildItemAtPosition($inputArray, $position))) {
yield $item;
$position = incrementPosition($position, $maximumPosition);
}
}
function buildItemAtPosition($inputArray, $positions)
{
if ($positions[0] >= count($inputArray[0])) {
return false;
}
$item = [];
foreach ($inputArray as $rowIndex => $row) {
$position = $positions[$rowIndex];
$item[] = $row[$position];
}
return $item;
}
function incrementPosition($position, $maximumPosition)
{
$digitToIncrement = count($position) - 1;
do {
$position[$digitToIncrement]++;
if ($position[$digitToIncrement] < $maximumPosition[$digitToIncrement] || 0 === $digitToIncrement) {
//no overflow
break;
}
//overflow, reset to zero and increment parent digit
$position[$digitToIncrement] = 0;
$digitToIncrement--;
} while ($digitToIncrement >= 0);
return $position;
}
// https://stackoverflow.com/a/43703899/1833322
function cartezian1($inputArray)
{
$results = [];
foreach ($inputArray as $group) {
$results = expandItems($results, $group);
}
return $results;
}
function expandItems($sourceItems, $tails)
{
$result = [];
if (empty($sourceItems)) {
foreach ($tails as $tail) {
$result[] = [$tail];
}
return $result;
}
foreach ($sourceItems as $sourceItem) {
foreach ($tails as $tail) {
$result[] = array_merge($sourceItem, [$tail]);
}
}
return $result;
}
// https://stackoverflow.com/a/41899540/1833322
function crossProduct() {
$_ = func_get_args();
if (count($_) == 0) {
return array(array());
}
$a = array_shift($_);
$c = call_user_func_array('crossProduct', $_);
$r = array();
foreach ($a as $v) {
foreach ($c as $p) {
$r[] = array_merge(array($v), $p);
}
}
return $r;
}
// https://stackoverflow.com/a/41899317/1833322
function cartesian6(array $data) {
$cartesian = [];
//Use array map to run over all array items
array_map(function($item) use($data, &$cartesian) {
//starting from your element, search for all others "next departments"
for($i = array_search($item, $data)+1, $c = count($data); $i<$c; $i++) {
//foreach "next departments" get section
foreach($data[$i]['sections'] as $section) {
//foreach sections of current department, do
foreach($item['sections'] as $item_section) {
//append to cartesian resultset
$cartesian[] = [$item_section, $section];
}
}
}
}, $data);
//create a reverse array, to get all reverse combinations.
// Ex.: We have CIS-1 -> MATH-1, now we have MATH-1 -> CIS-1
$reverse = array_map('array_reverse', $cartesian);
//merge to cartesian resultset
$cartesian = array_merge($cartesian, $reverse);
return $cartesian;
}
// https://github.com/hoaproject/Math/blob/master/Source/Combinatorics/Combination/CartesianProduct.php
// Small adjustments made to let it run standalone
class CartesianProduct implements Iterator
{
/**
* All sets.
*/
protected $_sets = [];
/**
* Number of sets.
*/
protected $_max = 0;
/**
* Key.
*/
protected $_key = 0;
/**
* Current (contains the current t-uple).
*/
protected $_current = null;
/**
* Whether the iterator has reached the end or not.
*/
protected $_break = true;
/**
* Constructor.
*/
public function __construct(array $set)
{
foreach (func_get_args() as $s) {
if (is_array($s)) {
$s = new \ArrayIterator($s);
} else {
$s = new \IteratorIterator($s);
}
$this->_sets[] = $s;
}
$this->_max = count($this->_sets) - 1;
$this->_break = empty($this->_sets);
return;
}
/**
* Get the current value.
*/
public function current(): array
{
return $this->_current;
}
/**
* Prepare the current value.
*/
protected function _current(): void
{
$this->_current = [];
foreach ($this->_sets as $set) {
$this->_current[] = $set->current();
}
return;
}
/**
* Get the current key.
*/
public function key(): int
{
return $this->_key;
}
/**
* Advance the internal collection pointer, and return the current value.
*/
public function next(): array
{
for ($i = 0; $i <= $this->_max; ++$i) {
$this->_sets[$i]->next();
if (false !== $this->_sets[$i]->valid()) {
break;
}
$this->_sets[$i]->rewind();
if ($i === $this->_max) {
$this->_break = true;
break;
}
}
++$this->_key;
$this->_current();
return $this->current();
}
/**
* Rewind the internal collection pointer, and return the first collection.
*/
public function rewind(): array
{
$this->_break = empty($this->_sets);
$this->_key = 0;
foreach ($this->_sets as $set) {
$set->rewind();
}
$this->_current();
return $this->current();
}
/**
* Check if there is a current element after calls to the rewind() or the
* next() methods.
*/
public function valid(): bool
{
return false === $this->_break;
}
}
// https://gist.github.com/jwage/11193216
function build($set) {
if (!$set) {
return array(array());
}
$subset = array_shift($set);
$cartesianSubset = build($set);
$result = array();
foreach ($subset as $value) {
foreach ($cartesianSubset as $p) {
array_unshift($p, $value);
$result[] = $p;
}
}
return $result;
}
// https://github.com/PatchRanger/cartesian-iterator/blob/master/src/CartesianIterator.php
class CartesianIterator extends \MultipleIterator
{
/** @var \Iterator[] */
protected $iterators = [];
/** @var int */
protected $key = 0;
/** @var string[] */
protected $infosHashMap = [];
public function __construct()
{
parent::__construct(static::MIT_NEED_ALL|static::MIT_KEYS_ASSOC);
}
public function attachIterator(\Iterator $iterator, $infos = null): void
{
$this->iterators[] = $iterator;
if ($infos === null) {
$infos = count($this->iterators) - 1;
}
if (isset($this->infosHashMap[$infos])) {
throw new \InvalidArgumentException("Iterator with the same key has been already added: {$infos}");
}
$this->infosHashMap[$infos] = spl_object_hash($iterator);
parent::attachIterator($iterator, $infos);
}
public function detachIterator(\Iterator $iterator): void
{
if (!$this->containsIterator($iterator)) {
return;
}
parent::detachIterator($iterator);
$iteratorHash = spl_object_hash($iterator);
foreach ($this->iterators as $index => $iteratorAttached) {
if ($iteratorHash === spl_object_hash($iteratorAttached)) {
unset($this->iterators[$index]);
break;
}
}
$infos = array_flip($this->infosHashMap)[spl_object_hash($iterator)];
unset($this->infosHashMap[$infos]);
}
public function key(): int
{
return $this->key;
}
public function next(): void
{
$this->applyNext();
$this->key += 1;
}
public function rewind(): void
{
parent::rewind();
$this->key = 0;
}
private function applyNext(int $index = 0): void
{
$iterator = $this->iterators[$index];
$iterator->next();
if (!$iterator->valid() && $index < $this->countIterators() - 1) {
$iterator->rewind();
$this->applyNext($index + 1);
}
}
}
// https://github.com/bpolaszek/cartesian-product/blob/master/src/CartesianProduct.php
class CartesianProduct2 implements IteratorAggregate, Countable
{
/**
* @var array
*/
private $set = [];
/**
* @var bool
*/
private $isRecursiveStep = false;
/**
* @var int
*/
private $count;
/**
* CartesianProduct constructor.
*
* @param array $set - A multidimensionnal array.
*/
public function __construct(array $set)
{
$this->set = $set;
}
/**
* @return \Generator
*/
public function getIterator()
{
if ([] === $this->set) {
if (true === $this->isRecursiveStep) {
yield [];
}
return;
}
$keys = \array_keys($this->set);
$last = \end($keys);
$subset = \array_pop($this->set);
$this->validate($subset, $last);
foreach (self::subset($this->set) as $product) {
foreach ($subset as $value) {
yield $product + [$last => ($value instanceof \Closure ? $value($product) : $value)];
}
}
}
/**
* @param $subset
* @param $key
*/
private function validate($subset, $key)
{
// Validate array subset
if (\is_array($subset) && !empty($subset)) {
return;
}
// Validate iterator subset
if ($subset instanceof Traversable && $subset instanceof Countable && \count($subset) > 0) {
return;
}
throw new InvalidArgumentException(\sprintf('Key "%s" should return a non-empty iterable', $key));
}
/**
* @param array $subset
* @return CartesianProduct
*/
private static function subset(array $subset)
{
$product = new self($subset);
$product->isRecursiveStep = true;
return $product;
}
/**
* @return array
*/
public function asArray()
{
return \iterator_to_array($this);
}
/**
* @return int
*/
public function count()
{
if (null === $this->count) {
$this->count = (int) \array_product(
\array_map(
function ($subset, $key) {
$this->validate($subset, $key);
return \count($subset);
},
$this->set,
\array_keys($this->set)
)
);
}
return $this->count;
}
}
// https://repl.it/repls/DisgustingThreadbareWebportal
function cartesian7($input) {
// filter out empty values
$input = array_filter($input);
$result = array(array());
foreach ($input as $key => $values) {
$append = array();
foreach($result as $product) {
foreach($values as $item) {
$product[$key] = $item;
$append[] = $product;
}
}
$result = $append;
}
echo $result;
}
// https://stackoverflow.com/a/2516779/1833322
function array_cartesian() {
$_ = func_get_args();
if(count($_) == 0)
return array(array());
$a = array_shift($_);
$c = call_user_func_array(__FUNCTION__, $_);
$r = array();
foreach($a as $v)
foreach($c as $p)
$r[] = array_merge(array($v), $p);
return $r;
}
// https://stackoverflow.com/a/8936492/1833322
function array_cartesian2($arrays) {
$result = array();
$keys = array_keys($arrays);
$reverse_keys = array_reverse($keys);
$size = intval(count($arrays) > 0);
foreach ($arrays as $array) {
$size *= count($array);
}
for ($i = 0; $i < $size; $i ++) {
$result[$i] = array();
foreach ($keys as $j) {
$result[$i][$j] = current($arrays[$j]);
}
foreach ($reverse_keys as $j) {
if (next($arrays[$j])) {
break;
}
elseif (isset ($arrays[$j])) {
reset($arrays[$j]);
}
}
}
return $result;
}
// https://stackoverflow.com/a/16681624/1833322
function array_cartesian_product( $arrays )
{
$result = array();
$arrays = array_values( $arrays );
$sizeIn = sizeof( $arrays );
$size = $sizeIn > 0 ? 1 : 0;
foreach ($arrays as $array)
$size = $size * sizeof( $array );
$res_index = 0;
for ( $i = 0; $i < $size; $i++ )
{
$is_duplicate = false;
$curr_values = array();
for ( $j = 0; $j < $sizeIn; $j++ )
{
$curr = current( $arrays[$j] );
if ( !in_array( $curr, $curr_values ) )
{
array_push( $curr_values , $curr );
}
else
{
$is_duplicate = true;
break;
}
}
if ( !$is_duplicate )
{
$result[ $res_index ] = $curr_values;
$res_index++;
}
for ( $j = ( $sizeIn -1 ); $j >= 0; $j-- )
{
$next = next( $arrays[ $j ] );
if ( $next )
{
break;
}
elseif ( isset ( $arrays[ $j ] ) )
{
reset( $arrays[ $j ] );
}
}
}
return $result;
}
// https://stackoverflow.com/a/2517101/1833322
function combinations ($array, & $output, $index = 0, $p = array()) {
foreach ( $array[$index] as $i => $name ) {
$copy = $p;
$copy[] = $name;
$subIndex = $index + 1;
if (isset( $array[$subIndex])) {
combinations ($array, $output, $subIndex, $copy);
} else {
foreach ($copy as $index => $name) {
if ( !isset($output[$index])) {
$output[$index] = array();
}
$output[$index][] = $name;
}
}
}
}
// https://stackoverflow.com/a/4743758/1833322
function array_cartesian3() {
$_ = func_get_args();
if (count($_) == 0)
return array();
$a = array_shift($_);
if (count($_) == 0)
$c = array(array());
else
$c = call_user_func_array(__FUNCTION__, $_);
$r = array();
foreach($a as $v)
foreach($c as $p)
$r[] = array_merge(array($v), $p);
return $r;
}
// https://stackoverflow.com/a/4950904/1833322
function array_comb($arrays)
{
$result = array();
$arrays = array_values($arrays);
$sizeIn = sizeof($arrays);
$size = $sizeIn > 0 ? 1 : 0;
foreach ($arrays as $array)
$size = $size * sizeof($array);
for ($i = 0; $i < $size; $i ++)
{
$result[$i] = array();
for ($j = 0; $j < $sizeIn; $j ++)
array_push($result[$i], current($arrays[$j]));
for ($j = ($sizeIn -1); $j >= 0; $j --)
{
if (next($arrays[$j]))
break;
elseif (isset ($arrays[$j]))
reset($arrays[$j]);
}
}
return $result;
}
// https://stackoverflow.com/a/43902154/1833322
function direct_product(array ...$arrays)
{
$result = [[]];
foreach ($arrays as $array) {
$tmp = [];
foreach ($result as $x) {
foreach ($array as $y) {
$tmp[] = array_merge($x, [$y]);
}
}
$result = $tmp;
}
return $result;
}
// https://stackoverflow.com/a/42070211/1833322
function options_combinations($options) {
$result = array();
if (count($options) <= 1) {
$option = array_shift($options);
foreach ($option as $value) {
$result[] = array($value);
}
} else {
$option = array_shift($options);
$next_option = options_combinations($options);
foreach ($next_option as $next_value) {
foreach ($option as $value) {
$result[] = array_merge($next_value, array($value));
}
}
}
return $result;
}
// https://stackoverflow.com/a/30259912/1833322
// Don't know how to use this one
// function dfcartesian ( $input, $current, $index ) {
// // sample use: $emptyArray = array();
// // dfcartesian( $items, $emptyArray, 0 )
// if ( $index == count( $input ) ) {
// // If we have iterated over the entire space and are at the bottom
// // do whatever is relevant to your problem and return.
// //
// // If I were to improve the solution I suppose I'd pass in an
// // optional function name that we could pass data to if desired.
// var_dump( $current );
// echo '<br><br>';
// return;
// }
// // I'm using non-sequential numerical indicies in an associative array
// // so I want to skip any empty numerical index without aborting.
// //
// // If you're using something different I think the only change that
// // needs attention is to change $index + 1 to a different type of
// // key incrementer. That sort of issue is tackled at
// // https://stackoverflow.com/q/2414141/759749
// if ( isset ( $input[$index] ) ) {
// foreach ( $input[$index] as $element ) {
// $current[] = $element;
// // despite my concern about recursive function overhead,
// // this handled 24 levels quite smoothly.
// dfcartesian( $input, $current, ( $index + 1 ) );
// array_pop( $current );
// }
// } else {
// // move to the next index if there is a gap
// dfcartesian( $input, $current, ( $index + 1 ) );
// }
// }
// https://stackoverflow.com/a/44101542/1833322
function arrayCrossProduct( array $data ) {
$rowCount = 1; // keep track of total rows we need to generate
// the reference is just used for convenience to cast to and reset the array
foreach( $data as &$datum ) {
$datum = (array) $datum; // cast to array
$rowCount *= count( $datum ); // multiply total rows with current element count
reset( $datum ); // reset the array, just to be sure
}
$result = array();
while( $rowCount-- > 0 ) {
$row = array();
foreach( $data as &$datum ) { // reference necessary to keep track of array pointer
$row[] = current( $datum ); // generate new row
}
$result[] = $row; // add row to result
// find the first element that is advanceable
foreach( $data as &$datum ) { // reference necessary to keep track of array pointer
next( $datum );
// if it advanced/not at the end: break
if( !is_null( key( $datum ) ) ) {
break;
}
reset( $datum ); // else rewind the array and continue
}
}
return $result;
}
// https://gist.github.com/cecilemuller/4688876
function get_combinations($arrays) {
$result = array(array());
foreach ($arrays as $property => $property_values) {
$tmp = array();
foreach ($result as $result_item) {
foreach ($property_values as $property_value) {
$tmp[] = array_merge($result_item, array($property => $property_value));
}
}
$result = $tmp;
}
return $result;
}
// https://stackoverflow.com/a/27110374/1833322
function get_combinations2($arrays) {
$result = array(array());
foreach ($arrays as $property => $property_values) {
$tmp = array();
foreach ($result as $result_item) {
foreach ($property_values as $property_key => $property_value) {
$tmp[] = $result_item + array($property_key => $property_value);
}
}
$result = $tmp;
}
return $result;
}
// https://stackoverflow.com/a/40647033/1833322
// Doesn't seem to do cartesian product
// function comb($m, $a) {
// if (!$m) {
// yield [];
// return;
// }
// if (!$a) {
// return;
// }
// $h = $a[0];
// $t = array_slice($a, 1);
// foreach(comb($m - 1, $t) as $c)
// yield array_merge([$h], $c);
// foreach(comb($m, $t) as $c)
// yield $c;
// }
/** TESTS **/
function arrayToString(array $a) {
return '[' . implode(', ', array_map(function($item) {
return is_array($item) ? arrayToString($item) : $item;
}, $a)) . ']';
}
function expRange($start, $stop, $exp) {
return array_map(function($nr) use ($exp) {
return $nr * pow(10, $exp);
}, range(1, 10));
}
function zip(...$arrays) {
$arr_count = count($arrays);
if ($arr_count < 2) {
throw new \InvalidArgumentException('Need at least two arrays to zip.');
}
$len = count($arrays[0]);
for ($i = 1; $i < $arr_count; $i++) {
if (count($arrays[$i]) !== $len) {
throw new \InvalidArgumentException('This implementation only works with even length arrays.');
}
}
$result = [];
for ($i = 0; $i < $len; $i++) {
$tmp = [];
for ($j = 0; $j < $arr_count; $j++) {
$tmp[] = $arrays[$j][$i];
}
$results[] = $tmp;
}
return $result;
}
$tests =
[ [ 'input' => [[]]
, 'expect' => []
]
, [ 'input' => [[], []]
, 'expect' => []
]
, [ 'input' => [[1]]
, 'expect' => [[1]]
]
, [ 'input' => [[1, 2]]
, 'expect' => [[1], [2]]
]
, [ 'input' => [[1], [2]]
, 'expect' => [[1, 2]]
]
, [ 'input' => [['a', 'b'], [1]]
, 'expect' => [['a', 1], ['b', 1]]
]
, [ 'input' => [expRange(1, 10, 0), expRange(1, 10, 1)]
// i trust the output of this function enough to verify the results of other functions against it
, 'expect' => cartesian([expRange(1, 10, 0), expRange(1, 10, 1)])
]
, [ 'input' => [expRange(1, 10, 0), expRange(1, 10, 1), expRange(1, 10, 2), expRange(1, 10, 3), expRange(1, 10, 4)]
, 'expect' => cartesian([expRange(1, 10, 0), expRange(1, 10, 1), expRange(1, 10, 2), expRange(1, 10, 3), expRange(1, 10, 4)])
]
];
$testNr = 1;
$results = [];
/** Normal functions **/
// cartesian
// cartesian2
// cartesian_product
// cartesian_product2
// cartesian4
// getAllVariations
// cartesian5
// cartezian1
// crossProduct
// cartesian6
// build
// cartesian7
// array_cartesian
// array_cartesian2
// array_cartesian_product
// combinations
// array_cartesian3
// array_comb
// direct_product
// options_combinations
// arrayCrossProduct
// get_combinations
// get_combinations2
foreach ($tests as $k => ['input' => $input, 'expect' => $expect]) {
$start = microtime(true);
for ($i = 0; $i <= $iterations; $i++) {
$output = cartesian($input);
}
$results[$k][$testNr] = microtime(true) - $start;
sort($output); sort($expect);
if ($output !== $expect)
printf("Input: \"%s\" Expected \"%s\" in %d, but got \"%s\"\n",
arrayToString($input), substr(arrayToString($expect), 0, 100) . '..', $k, substr(arrayToString($output), 0, 100) . '..');
}
printf("Finished test %d\n", $testNr);
$testNr++;
foreach ($tests as $k => ['input' => $input, 'expect' => $expect]) {
$start = microtime(true);
for ($i = 0; $i <= $iterations; $i++) {
$output = cartesian2($input);
}
$results[$k][$testNr] = microtime(true) - $start;
sort($output); sort($expect);
if ($output !== $expect)
printf("Input: \"%s\" Expected \"%s\" in %d, but got \"%s\"\n",
arrayToString($input), substr(arrayToString($expect), 0, 100) . '..', $k, substr(arrayToString($output), 0, 100) . '..');
}
printf("Finished test %d\n", $testNr);
$testNr++;
// PHP Warning: array_combine() expects parameter 2 to be array, int given
// foreach ($tests as $k => ['input' => $input, 'expect' => $expect]) {
// $start = microtime(true);
// for ($i = 0; $i <= $iterations; $i++) {
// $output = cartesian_product($input);
// }
// $results[$k][$testNr] = microtime(true) - $start;
// sort($output); sort($expect);
// if ($output !== $expect)
// printf("Input: \"%s\" Expected \"%s\" in %d, but got \"%s\"\n",
// arrayToString($input), substr(arrayToString($expect), 0, 100) . '..', $k, substr(arrayToString($output), 0, 100) . '..');
// }
// printf("Finished test %d\n", $testNr);
// $testNr++;
// PHP Warning: array_combine() expects parameter 2 to be array, int given
// foreach ($tests as $k => ['input' => $input, 'expect' => $expect]) {
// $start = microtime(true);
// for ($i = 0; $i <= $iterations; $i++) {
// $output = cartesian_product2($input);
// }
// $results[$k][$testNr] = microtime(true) - $start;
// sort($output); sort($expect);
// if ($output !== $expect)
// printf("Input: \"%s\" Expected \"%s\" in %d, but got \"%s\"\n",
// arrayToString($input), substr(arrayToString($expect), 0, 100) . '..', $k, substr(arrayToString($output), 0, 100) . '..');
// }
// printf("Finished test %d\n", $testNr);
// $testNr++;
foreach ($tests as $k => ['input' => $input, 'expect' => $expect]) {
$start = microtime(true);
for ($i = 0; $i <= $iterations; $i++) {
$output = cartesian4($input);
}
$results[$k][$testNr] = microtime(true) - $start;
sort($output); sort($expect);
if ($output !== $expect)
printf("Input: \"%s\" Expected \"%s\" in %d, but got \"%s\"\n",
arrayToString($input), substr(arrayToString($expect), 0, 100) . '..', $k, substr(arrayToString($output), 0, 100) . '..');
}
printf("Finished test %d\n", $testNr);
$testNr++;
foreach ($tests as $k => ['input' => $input, 'expect' => $expect]) {
$start = microtime(true);
for ($i = 0; $i <= $iterations; $i++) {
$output = getAllVariations($input);
}
$results[$k][$testNr] = microtime(true) - $start;
sort($output); sort($expect);
if ($output !== $expect)
printf("Input: \"%s\" Expected \"%s\" in %d, but got \"%s\"\n",
arrayToString($input), substr(arrayToString($expect), 0, 100) . '..', $k, substr(arrayToString($output), 0, 100) . '..');
}
printf("Finished test %d\n", $testNr);
$testNr++;
// wrong output
// foreach ($tests as $k => ['input' => $input, 'expect' => $expect]) {
// $start = microtime(true);
// for ($i = 0; $i <= $iterations; $i++) {
// $output = cartesian5($input);
// }
// $results[$k][$testNr] = microtime(true) - $start;
// sort($output); sort($expect);
// if ($output !== $expect)
// printf("Input: \"%s\" Expected \"%s\" in %d, but got \"%s\"\n",
// arrayToString($input), substr(arrayToString($expect), 0, 100) . '..', $k, substr(arrayToString($output), 0, 100) . '..');
// }
// printf("Finished test %d\n", $testNr);
// $testNr++;
foreach ($tests as $k => ['input' => $input, 'expect' => $expect]) {
$start = microtime(true);
for ($i = 0; $i <= $iterations; $i++) {
$output = cartezian1($input);
}
$results[$k][$testNr] = microtime(true) - $start;
sort($output); sort($expect);
if ($output !== $expect)
printf("Input: \"%s\" Expected \"%s\" in %d, but got \"%s\"\n",
arrayToString($input), substr(arrayToString($expect), 0, 100) . '..', $k, substr(arrayToString($output), 0, 100) . '..');
}
printf("Finished test %d\n", $testNr);
$testNr++;
// wrong output
// foreach ($tests as $k => ['input' => $input, 'expect' => $expect]) {
// $start = microtime(true);
// for ($i = 0; $i <= $iterations; $i++) {
// $output = crossProduct($input);
// }
// $results[$k][$testNr] = microtime(true) - $start;
// sort($output); sort($expect);
// if ($output !== $expect)
// printf("Input: \"%s\" Expected \"%s\" in %d, but got \"%s\"\n",
// arrayToString($input), substr(arrayToString($expect), 0, 100) . '..', $k, substr(arrayToString($output), 0, 100) . '..');
// }
// printf("Finished test %d\n", $testNr);
// $testNr++;
// PHP Notice: Undefined index: sections
// PHP Warning: Invalid argument supplied for foreach()
// foreach ($tests as $k => ['input' => $input, 'expect' => $expect]) {
// $start = microtime(true);
// for ($i = 0; $i <= $iterations; $i++) {
// $output = cartesian6($input);
// }
// $results[$k][$testNr] = microtime(true) - $start;
// sort($output); sort($expect);
// if ($output !== $expect)
// printf("Input: \"%s\" Expected \"%s\" in %d, but got \"%s\"\n",
// arrayToString($input), substr(arrayToString($expect), 0, 100) . '..', $k, substr(arrayToString($output), 0, 100) . '..');
// }
// printf("Finished test %d\n", $testNr);
// $testNr++;
foreach ($tests as $k => ['input' => $input, 'expect' => $expect]) {
$start = microtime(true);
for ($i = 0; $i <= $iterations; $i++) {
$output = build($input);
}
$results[$k][$testNr] = microtime(true) - $start;
sort($output); sort($expect);
if ($output !== $expect)
printf("Input: \"%s\" Expected \"%s\" in %d, but got \"%s\"\n",
arrayToString($input), substr(arrayToString($expect), 0, 100) . '..', $k, substr(arrayToString($output), 0, 100) . '..');
}
printf("Finished test %d\n", $testNr);
$testNr++;
// PHP Notice: Array to string conversion
// ArrayPHP Warning: sort() expects parameter 1 to be array, null given
// PHP Fatal error: Uncaught TypeError: Argument 1 passed to arrayToString() must be of the type array, null given
// foreach ($tests as $k => ['input' => $input, 'expect' => $expect]) {
// $start = microtime(true);
// for ($i = 0; $i <= $iterations; $i++) {
// $output = cartesian7($input);
// }
// $results[$k][$testNr] = microtime(true) - $start;
// sort($output); sort($expect);
// if ($output !== $expect)
// printf("Input: \"%s\" Expected \"%s\" in %d, but got \"%s\"\n",
// arrayToString($input), substr(arrayToString($expect), 0, 100) . '..', $k, substr(arrayToString($output), 0, 100) . '..');
// }
// printf("Finished test %d\n", $testNr);
// $testNr++;
// wrong output
// foreach ($tests as $k => ['input' => $input, 'expect' => $expect]) {
// $start = microtime(true);
// for ($i = 0; $i <= $iterations; $i++) {
// $output = array_cartesian($input);
// }
// $results[$k][$testNr] = microtime(true) - $start;
// sort($output); sort($expect);
// if ($output !== $expect)
// printf("Input: \"%s\" Expected \"%s\" in %d, but got \"%s\"\n",
// arrayToString($input), substr(arrayToString($expect), 0, 100) . '..', $k, substr(arrayToString($output), 0, 100) . '..');
// }
// printf("Finished test %d\n", $testNr);
// $testNr++;
foreach ($tests as $k => ['input' => $input, 'expect' => $expect]) {
$start = microtime(true);
for ($i = 0; $i <= $iterations; $i++) {
$output = array_cartesian2($input);
}
$results[$k][$testNr] = microtime(true) - $start;
sort($output); sort($expect);
if ($output !== $expect)
printf("Input: \"%s\" Expected \"%s\" in %d, but got \"%s\"\n",
arrayToString($input), substr(arrayToString($expect), 0, 100) . '..', $k, substr(arrayToString($output), 0, 100) . '..');
}
printf("Finished test %d\n", $testNr);
$testNr++;
// wrong output
// foreach ($tests as $k => ['input' => $input, 'expect' => $expect]) {
// $start = microtime(true);
// for ($i = 0; $i <= $iterations; $i++) {
// $output = array_cartesian_product($input);
// }
// $results[$k][$testNr] = microtime(true) - $start;
// sort($output); sort($expect);
// if ($output !== $expect)
// printf("Input: \"%s\" Expected \"%s\" in %d, but got \"%s\"\n",
// arrayToString($input), substr(arrayToString($expect), 0, 100) . '..', $k, substr(arrayToString($output), 0, 100) . '..');
// }
// printf("Finished test %d\n", $testNr);
// $testNr++;
// wrong output
// foreach ($tests as $k => ['input' => $input, 'expect' => $expect]) {
// $start = microtime(true);
// for ($i = 0; $i <= $iterations; $i++) {
// $output = [];
// combinations($input, $output);
// }
// $results[$k][$testNr] = microtime(true) - $start;
// sort($output); sort($expect);
// if ($output !== $expect)
// printf("Input: \"%s\" Expected \"%s\" in %d, but got \"%s\"\n",
// arrayToString($input), substr(arrayToString($expect), 0, 100) . '..', $k, substr(arrayToString($output), 0, 100) . '..');
// }
// printf("Finished test %d\n", $testNr);
// $testNr++;
// wrong output
// foreach ($tests as $k => ['input' => $input, 'expect' => $expect]) {
// $start = microtime(true);
// for ($i = 0; $i <= $iterations; $i++) {
// $output = array_cartesian3($input);
// }
// $results[$k][$testNr] = microtime(true) - $start;
// sort($output); sort($expect);
// if ($output !== $expect)
// printf("Input: \"%s\" Expected \"%s\" in %d, but got \"%s\"\n",
// arrayToString($input), substr(arrayToString($expect), 0, 100) . '..', $k, substr(arrayToString($output), 0, 100) . '..');
// }
// printf("Finished test %d\n", $testNr);
// $testNr++;
foreach ($tests as $k => ['input' => $input, 'expect' => $expect]) {
$start = microtime(true);
for ($i = 0; $i <= $iterations; $i++) {
$output = array_comb($input);
}
$results[$k][$testNr] = microtime(true) - $start;
sort($output); sort($expect);
if ($output !== $expect)
printf("Input: \"%s\" Expected \"%s\" in %d, but got \"%s\"\n",
arrayToString($input), substr(arrayToString($expect), 0, 100) . '..', $k, substr(arrayToString($output), 0, 100) . '..');
}
printf("Finished test %d\n", $testNr);
$testNr++;
// wrong output
// foreach ($tests as $k => ['input' => $input, 'expect' => $expect]) {
// $start = microtime(true);
// for ($i = 0; $i <= $iterations; $i++) {
// $output = direct_product($input);
// }
// $results[$k][$testNr] = microtime(true) - $start;
// sort($output); sort($expect);
// if ($output !== $expect)
// printf("Input: \"%s\" Expected \"%s\" in %d, but got \"%s\"\n",
// arrayToString($input), substr(arrayToString($expect), 0, 100) . '..', $k, substr(arrayToString($output), 0, 100) . '..');
// }
// printf("Finished test %d\n", $testNr);
// $testNr++;
// wrong output
// foreach ($tests as $k => ['input' => $input, 'expect' => $expect]) {
// $start = microtime(true);
// for ($i = 0; $i <= $iterations; $i++) {
// $output = options_combinations($input);
// }
// $results[$k][$testNr] = microtime(true) - $start;
// sort($output); sort($expect);
// if ($output !== $expect)
// printf("Input: \"%s\" Expected \"%s\" in %d, but got \"%s\"\n",
// arrayToString($input), substr(arrayToString($expect), 0, 100) . '..', $k, substr(arrayToString($output), 0, 100) . '..');
// }
// printf("Finished test %d\n", $testNr);
// $testNr++;
foreach ($tests as $k => ['input' => $input, 'expect' => $expect]) {
$start = microtime(true);
for ($i = 0; $i <= $iterations; $i++) {
$output = arrayCrossProduct($input);
}
$results[$k][$testNr] = microtime(true) - $start;
sort($output); sort($expect);
if ($output !== $expect)
printf("Input: \"%s\" Expected \"%s\" in %d, but got \"%s\"\n",
arrayToString($input), substr(arrayToString($expect), 0, 100) . '..', $k, substr(arrayToString($output), 0, 100) . '..');
}
printf("Finished test %d\n", $testNr);
$testNr++;
foreach ($tests as $k => ['input' => $input, 'expect' => $expect]) {
$start = microtime(true);
for ($i = 0; $i <= $iterations; $i++) {
$output = get_combinations($input);
}
$results[$k][$testNr] = microtime(true) - $start;
sort($output); sort($expect);
if ($output !== $expect)
printf("Input: \"%s\" Expected \"%s\" in %d, but got \"%s\"\n",
arrayToString($input), substr(arrayToString($expect), 0, 100) . '..', $k, substr(arrayToString($output), 0, 100) . '..');
}
printf("Finished test %d\n", $testNr);
$testNr++;
// wrong output
// foreach ($tests as $k => ['input' => $input, 'expect' => $expect]) {
// $start = microtime(true);
// for ($i = 0; $i <= $iterations; $i++) {
// $output = get_combinations2($input);
// }
// $results[$k][$testNr] = microtime(true) - $start;
// sort($output); sort($expect);
// if ($output !== $expect)
// printf("Input: \"%s\" Expected \"%s\" in %d, but got \"%s\"\n",
// arrayToString($input), substr(arrayToString($expect), 0, 100) . '..', $k, substr(arrayToString($output), 0, 100) . '..');
// }
// printf("Finished test %d\n", $testNr);
// $testNr++;
/** Iterator based functions **/
// cartesian3
// acartesian
// cartezianIterator
// comb
// wrong output
// foreach ($tests as $k => ['input' => $input, 'expect' => $expect]) {
// $start = microtime(true);
// for ($i = 0; $i <= $iterations; $i++) {
// $output = iterator_to_array(cartesian3($input));
// }
// $results[$k][$testNr] = microtime(true) - $start;
// sort($output); sort($expect);
// if ($output !== $expect)
// printf("Input: \"%s\" Expected \"%s\" in %d, but got \"%s\"\n",
// arrayToString($input), substr(arrayToString($expect), 0, 100) . '..', $k, substr(arrayToString($output), 0, 100) . '..');
// }
// printf("Finished test %d\n", $testNr);
// $testNr++;
// Needed a fix
foreach ($tests as $k => ['input' => $input, 'expect' => $expect]) {
$start = microtime(true);
for ($i = 0; $i <= $iterations; $i++) {
$output = iterator_to_array(acartesian($input));
}
$results[$k][$testNr] = microtime(true) - $start;
sort($output); sort($expect);
if ($output !== $expect)
printf("Input: \"%s\" Expected \"%s\" in %d, but got \"%s\"\n",
arrayToString($input), substr(arrayToString($expect), 0, 100) . '..', $k, substr(arrayToString($output), 0, 100) . '..');
}
printf("Finished test %d\n", $testNr);
$testNr++;
foreach ($tests as $k => ['input' => $input, 'expect' => $expect]) {
$start = microtime(true);
for ($i = 0; $i <= $iterations; $i++) {
$output = iterator_to_array(cartezianIterator($input));
}
$results[$k][$testNr] = microtime(true) - $start;
sort($output); sort($expect);
if ($output !== $expect)
printf("Input: \"%s\" Expected \"%s\" in %d, but got \"%s\"\n",
arrayToString($input), substr(arrayToString($expect), 0, 100) . '..', $k, substr(arrayToString($output), 0, 100) . '..');
}
printf("Finished test %d\n", $testNr);
$testNr++;
// foreach ($tests as $k => ['input' => $input, 'expect' => $expect]) {
// $start = microtime(true);
// for ($i = 0; $i <= $iterations; $i++) {
// $output = iterator_to_array(comb($input));
// }
// $results[$k][$testNr] = microtime(true) - $start;
// sort($output); sort($expect);
// if ($output !== $expect)
// printf("Input: \"%s\" Expected \"%s\" in %d, but got \"%s\"\n",
// arrayToString($input), substr(arrayToString($expect), 0, 100) . '..', $k, substr(arrayToString($output), 0, 100) . '..');
// }
// printf("Finished test %d\n", $testNr);
// $testNr++;
/** Iterator based classes **/
// CartesianProduct
// CartesianIterator
// CartesianProduct2
// wrong output
// This is probably my found, should look into it later
// foreach ($tests as $k => ['input' => $input, 'expect' => $expect]) {
// $start = microtime(true);
// for ($i = 0; $i <= $iterations; $i++) {
// $output = iterator_to_array(new CartesianProduct($input));
// }
// $results[$k][$testNr] = microtime(true) - $start;
// sort($output); sort($expect);
// if ($output !== $expect)
// printf("Input: \"%s\" Expected \"%s\" in %d, but got \"%s\"\n",
// arrayToString($input), substr(arrayToString($expect), 0, 100) . '..', $k, substr(arrayToString($output), 0, 100) . '..');
// }
// printf("Finished test %d\n", $testNr);
// $testNr++;
foreach ($tests as $k => ['input' => $input, 'expect' => $expect]) {
$start = microtime(true);
for ($i = 0; $i <= $iterations; $i++) {
$it = new CartesianIterator();
foreach ($input as $item) {
$it->attachIterator(new ArrayIterator($item));
}
$output = iterator_to_array($it);
}
$results[$k][$testNr] = microtime(true) - $start;
sort($output); sort($expect);
if ($output !== $expect)
printf("Input: \"%s\" Expected \"%s\" in %d, but got \"%s\"\n",
arrayToString($input), substr(arrayToString($expect), 0, 100) . '..', $k, substr(arrayToString($output), 0, 100) . '..');
}
printf("Finished test %d\n", $testNr);
$testNr++;
// PHP Fatal error: Uncaught InvalidArgumentException: Key "0" should return a non-empty iterable
// foreach ($tests as $k => ['input' => $input, 'expect' => $expect]) {
// $start = microtime(true);
// for ($i = 0; $i <= $iterations; $i++) {
// $output = iterator_to_array(new CartesianProduct2($input));
// }
// $results[$k][$testNr] = microtime(true) - $start;
// sort($output); sort($expect);
// if ($output !== $expect)
// printf("Input: \"%s\" Expected \"%s\" in %d, but got \"%s\"\n",
// arrayToString($input), substr(arrayToString($expect), 0, 100) . '..', $k, substr(arrayToString($output), 0, 100) . '..');
// }
// printf("Finished test %d\n", $testNr);
// $testNr++;
function printMarkdownTable($results) {
$spacing = 0;
foreach ($results as $test) {
foreach ($test as $algo) {
$len = strlen($algo);
if ($len > $spacing) $spacing = $len;
}
}
$headerCount = count($results[0]);
for ($i = 1; $i <= $headerCount; $i++) {
printf("| %-" . $spacing . "s ", $i);
}
printf("|\n");
for ($i = 0; $i < $headerCount; $i++) {
printf("|--" . str_repeat('-', $spacing));
}
printf("|\n");
foreach ($results as $test) {
printf("| %s |\n", implode(' | ', array_map(
function($time) use ($spacing) { return sprintf("%-" . $spacing . "s", $time);
}, $test)));
}
}
$resultsPerIteration = array_map(function($test) use ($iterations) {
return array_map(function($algo) use ($iterations) {
return $algo === null ? null : $algo / $iterations;
}, $test);
}, $results);
$results_to_string = array_map(function($test) use ($decimals) {
return array_map(function($algo) use ($decimals) {
return $algo === null ? '' : (string) round($algo, $decimals);
}, $test);
}, $resultsPerIteration);
$results_to_percentages = array_map(function($test) {
$min = PHP_FLOAT_MAX;
foreach ($test as $k => $algo) {
if ($algo < $min) {
$min = $algo;
$minPos = $k;
}
}
$return = [];
foreach ($test as $k => $algo) {
if ($k === $minPos) {
$return[] = '100%';
} elseif ($min == 0) {
$return[] = 'n/a';
} else {
$return[] = round(($algo / $min) * 100) . '%';
}
}
return $return;
}, $results);
// printMarkdownTable($results_to_string);
// printf("\n");
printMarkdownTable($results_to_percentages);
@flip111
Copy link
Author

flip111 commented Mar 26, 2019

Results

Iterations: 1000

1 2 3 4 5 6 7 8 9 10 11 12 13
100% 1352% 1376% 2779% 1374% 1109% 1494% 1116% 1560% 3245% 3099% 3250% 3939%
492% 125% 100% 271% 141% 256% 192% 138% 308% 120% 557% 641% 2459%
264% 115% 146% 218% 100% 177% 306% 309% 307% 140% 647% 644% 1487%
263% 132% 201% 263% 100% 235% 389% 397% 420% 211% 682% 785% 1720%
307% 100% 132% 158% 124% 165% 202% 219% 227% 135% 482% 363% 1104%
303% 100% 141% 150% 130% 154% 227% 257% 239% 148% 429% 381% 1002%
175% 100% 184% 223% 166% 197% 387% 458% 430% 204% 271% 601% 1215%
135% 100% 137% 447% 126% 146% 286% 336% 276% 220% 203% 406% 782%

480.18user 18.12system 8:18.95elapsed 99%CPU (0avgtext+0avgdata 161132maxresident)k
0inputs+0outputs (0major+17603895minor)pagefaults 0swaps

Conclusion

The first few test cases are mainly to test some edge cases. Only the last one is really stressing the algorithms giving an output of 10^5 items. Therefor the best algorithm seems to be number 2. Below you can find this algoritm in my preferred code style:

function cartesian(array $input) : array {
  $result = [[]];

  foreach ($input as $key => $values) {
    $append = [];

    foreach ($result as $product) {
      foreach ($values as $item) {
        $product[$key] = $item;
        $append[] = $product;
      }
    }

    $result = $append;
  }

  return $result;
}

Remarks

The order of the output of the algorithms can be different. Because of that the output and the expected results are first sorted before being compared.

Memory usage is not measured. Some algorithms that provide an iterator could have better memory usage.

There is a bunch of algorithms in there that didn't give the results i wanted. But maybe they were not intended to solve this problem in the first place. Sorry for including them.

Cartesian product is the more mathematical term when people could say "find all combinations".

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment