PHP或JavaScript迭代无限数量的数组

Question

我正面临一个挑战,我有三个数组,每个数组只包含数字.我有一个函数get_sum,函数接收2个参数,一个数组数组和一个数字.这个数字是我希望通过从每个数组中求和一个或多个数来获得的总和,例如:如果我有2个数组[[1,2,3], [1,2,3]]而第二个参数是4 函数将返回将总和为4的数量的组合数.案件:

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

所以函数将重新调整int 3

我编写了下面的函数,它工作得很好,但我正在寻找一种方法来提高它的效率.目前,如果我有少于6个数组,它将工作,如果我有一百个数组,我希望它工作.有没有可以帮助我的阵列功能？

这是代码:

<?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)
?>

如果JavaScript中有一个函数,它也会很好.

谢谢

Answer 1

理念

我们的想法是为所有阵列创建所有元素的笛卡尔积,然后计算给出预期总和的行.

JavaScript的

在JavaScript ES6中,这个想法可以像这样实现:

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);

的功能simpleCartesian,fullCartesian和reduceSum作为辅助的getSum功能.

正在使用:

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

PHP

在PHP中,这个想法可以实现,例如:

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;
}

该功能cartesian_product是该功能的辅助get_sum功能.

正在使用:

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

优化

我们需要知道,当我们使用许多数组或一些非常大的数组时,使用笛卡尔积创建一个占用大量内存的完整数组.

• 如果我们假设表的元素是非负的,我们可以在创建笛卡尔积之前,通过从输入表中删除等于或大于sum参数的所有元素来优化该算法.

• 如果我们假设表的元素是正数,我们可以在创建笛卡尔积之前,通过从输入表中删除等于或大于sum参数减去输入数组的所有元素来优化该算法.

谢谢

特别感谢@rsp和@SergiySokolenko关于在JavaScript和PHP中实现笛卡尔积的答案.