Skip to content

Instantly share code, notes, and snippets.

@svdmitrij
Last active January 10, 2020 14:09
Show Gist options
  • Save svdmitrij/6244149 to your computer and use it in GitHub Desktop.
Save svdmitrij/6244149 to your computer and use it in GitHub Desktop.
4 algorithms of cartesian product
function cartesian($input) {
// http://stackoverflow.com/questions/6311779/finding-cartesian-product-with-php-associative-arrays
$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;
}
function array_cartesian_product($arrays) {
// http://php.net/manual/en/ref.array.php
$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;
}
function array_cartesian() {
// http://stackoverflow.com/questions/2516599/php-2d-array-output-all-combinations
$_ = 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;
}
function cartesian($arr) {
$variant = array();
$result = array();
$sizearr = sizeof($arr);
function recursiv($arr, $variant, $level, $result, $sizearr){
$level++;
if($level<$sizearr){
foreach ($arr[$level] as $val){
$variant[$level] = $val;
$result = recursiv($arr, $variant, $level, $result, $sizearr);
}
}else{
//if (sizeof(array_flip(array_flip($variant)))==$sizearr)
$result[] = $variant;
}
return $result;
}
return recursiv($arr, $variant, -1, $result, $sizearr);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment