PHP or JavaScript iterate infinite number of arrays

Question

I am facing a challange, I have three arrays, each array contains only numbers. I have a function get_sum the function receives 2 parameters, an array of arrays and a number. The number is a sum I want to receive from summing one or more number from each array, for example: If I have 2 arrays [[1,2,3], [1,2,3]] and the second parameter is 4 the function will return the number of combinations that will sum an amount of 4. in this case:

1+3 = 4
2+2 = 4
3+1 = 4

So the function will retun the int 3

I wrote the function below, and it works great but I am looking for a way to make it more efficient. At the moment it will work if I have less than 6 arrays, I want it to work if I have a hundred arrays. Is there any array function that can help me here?

This is the code:

<?php
function get_sum ($dice, $sum) {
    $sumcount = array();
    $num_of_dice = count($dice);    
    foreach($dice[0] as $die1){
        foreach($dice[1] as $die2){
            if($num_of_dice == 5){
                foreach($dice[2] as $die3){
                    foreach($dice[3] as $die4){
                        foreach($dice[4] as $die5){
                            if($die1 + $die2 + $die3+ $die4 + $die5 == $sum){
                                $good_res = array();
                                array_push( $good_res, $die1, $die2, $die3, $die4, $die5);
                                array_push($sumcount, $good_res);
                            }
                        }
                    }
                }
            }
            if($num_of_dice == 4){
                foreach($dice[2] as $die3){
                    foreach($dice[3] as $die4){
                        if($die1 + $die2 + $die3+ $die4 == $sum){
                            $good_res = array();
                            array_push( $good_res, $die1, $die2, $die3, $die4);
                            array_push($sumcount, $good_res);
                        }
                    }
                }
            }elseif ($num_of_dice == 3){
                foreach($dice[2] as $die3){
                    if($die1 + $die2 + $die3 == $sum){
                        $good_res = array();
                        array_push( $good_res, $die1, $die2, $die3);
                        array_push($sumcount, $good_res);
                    }
                }
            }else{
                if($die1 + $die2 == $sum){
                    $good_res = array();
                    array_push( $good_res, $die1, $die2);
                    array_push($sumcount, $good_res);
                }
            }

        }
    };



    echo count($sumcount);
}



get_sum([[1, 2, 3, 4, 5, 6], [1, 2, 3, 4, 5, 6], [1, 2, 3, 4, 5, 6]], 9)
?>

If there is a function in JavaScript it will be good as well.

Thanks

Answer 1

Idea

The idea is that to create a Cartesian Product of all elements for all arrays together and then count the rows that give the expected sum.

JavaScript

In JavaScript ES6 this idea can be implemented like this:

const simpleCartesian = (arr1, arr2) => [].concat( ...arr1.map( el1 => arr2.map( el2 => [].concat( el1, el2 ) ) ) );
const fullCartesian = (arr1, arr2, ...arrN) => (arr2 ? fullCartesian(simpleCartesian(arr1, arr2), ...arrN) : arr1);
const reduceSum = (a, b) => a + b;
const getSum = (arr, sum) =>  fullCartesian(...arr).reduce((prev, currArr) => prev += currArr.reduce(reduceSum) == sum ? 1 : 0, 0);

The functions simpleCartesian, fullCartesian and reduceSum are auxiliary for the getSum function.

In use:

getSum( [[1, 2, 3, 4, 5, 6], [1, 2, 3, 4, 5, 6], [1, 2, 3, 4, 5, 6]], 9)
// Returned value: 25

PHP

In PHP this idea can be implemented for example like this:

function cartesian_product($arrays) {
    $cartesian_product = [[]];
    foreach ($arrays as $key => $arr) {
        $appendArr = [];
        foreach ($cartesian_product as $product) {
            foreach ($arr as $item) {
                $product[$key] = $item;
                $appendArr[] = $product;
            }
        }
        $cartesian_product = $appendArr;
    }
    return $cartesian_product;
}
function get_sum($arrays, $sum) {
    $counter = 0;
    $cartesian_product = cartesian_product($arrays);
    foreach ($cartesian_product as $row) {
        if ($sum == array_sum($row)) {
            $counter++;
        }
    }
    return $counter;
}

The function cartesian_product is auxiliary for the get_sum function.

In use:

get_sum( [[1, 2, 3, 4, 5, 6], [1, 2, 3, 4, 5, 6], [1, 2, 3, 4, 5, 7]], 7);
// Returned value: 15

Optimization

We need to know that creating a full array with a Cartesian Product consuming a lot of memory when we use many arrays or some very big arrays.

• If we assume that the elements of tables are non-negative, we can optimize that algorithm by remove all elements equal to or larger than sum parameter from the input tables, before creating a Cartesian Product.

• If we assume that the elements of tables are positive, we can optimize that algorithm by remove all elements equal to or larger than sum parameter minus count of input arrays from the input tables, before creating a Cartesian Product.

Thanks

Special thanks for @rsp and @SergiySokolenko for their answers about the implementation of a Cartesian Product in JavaScript and PHP.