我试图在Javascript中实现某种数学组合，但可以找到最好的方法。
我试图实现的是从N.中找到组合(由3个元素组成(的总和
例如，我如何找到由5个元素中的3个元素组成的所有可能组合的和？
手动显示如下：
选择：A、B、C、D、E-所有这些都是数字
所有可能的5个组合中的3个如下：
ABC ABD ABE ACD ACE ADE BCE BCE BDE CDE
ABC表示A * B * C
简化形式的组合的总和如下所示：
AB(C+D+E(+AC(D+E。
我尝试了以下代码，但没有成功：
function calc(arr) {
var total = 0;
for (let i = 0; i < arr.length; i++) {
let sum = 0;
for (let j = i + 1; j < arr.length; j++) {
sum += arr[j] + arr[j + 1] + arr[j + 2];
}
total += sum * arr[i] + arr[i + 1] + arr[i + 2];
}
return total;
}
var arr = [2, 3, 4, 5, 6];
console.log(calc(arr));
function calc(arr){
var total = 0;
//first iterate over first possible coefficient
for(var i = 0; i < arr.length - 2; i++){
var coeff1 = arr[i];
//then iterate over second possible coefficient
for(var j = i + 1; j < arr.length - 1; j++){
var coeff2 = arr[j];
var parentheticalSum = 0;
//all other values are summed and then made the third coefficient
for(var k = j + 1; k < arr.length; k++){
parentheticalSum += arr[k];
}
total += coeff1 * coeff2 * parentheticalSum;
}
}
return total;
}
console.log(calc([1,2,3,4,5])); //outputs 225
// 1*2*(3+4+5) + 1*3*(4+5) + 1*4*(5) + 2*3*(4+5) + 2*4*(5) + 3*4*(5) = 225
以上确实有效，但肯定可以进行优化。我突然想到的是，我们正在做很多重复求和，我们应该用一个反向累积和表来代替第三个循环。
优化如下：
function calc(arr){
var reverseCumSumLookup = [];
var reverseCumSum = 0;
for(var rev = arr.length - 1; rev >= 0; rev--){
reverseCumSum += arr[rev];
reverseCumSumLookup[rev] = reverseCumSum;
}
var total = 0;
for(var i = 0; i < arr.length - 2; i++){
var coeff1 = arr[i];
for(var j = i + 1; j < arr.length - 1; j++){
var coeff2 = arr[j];
var parentheticalSum = reverseCumSumLookup[j+1];
total += coeff1 * coeff2 * parentheticalSum;
}
}
return total;
}
这将复杂性从n^3提高到n^2。有可能做得更好吗？