javascript - 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 个，它就可以工作，如果我有 100 个数组，我希望它可以工作。有什么数组函数可以帮到我吗？

这是代码:

<?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 参数的元素来优化该算法em> 来自输入表，然后创建笛卡尔积。

• 如果我们假设表的元素是正数，我们可以通过删除等于或大于参数和减去输入计数的所有元素来优化该算法来自输入表的数组，然后创建笛卡尔积。

谢谢

特别感谢@rsp和 @SergiySokolenko获取他们关于在 JavaScript 和 PHP 中实现笛卡尔积的答案。