数字组合的总和

Question

我想以尽可能快的方式解决数学问题。我有一组 1 到 n 之间的自然数，例如 {1,2,3,4,n=5} 我想计算这样的公式：

s = 1*2*3*4+1*2*3*5+1*2*4*5+1*3*4*5+2*3*4*5

如您所见，求和中的每个元素都是集合中 n-1 个数字的乘积。例如在(1*2*3*4)中排除了5，在(1*2*3*5)中排除了4。我知道一些乘法是重复的，例如 (1*2) 在 3 个乘法中重复。我怎样才能用最少的乘法来解决这个问题。

抱歉英语不好。谢谢。

Answer 1

以下是最直接的答案。

def f(n):
    result = 0
    nList = [i+1 for i in range(n)]
    for i in range(len(nList)):
        result += reduce(lambda x, y: x*y,(nList[:i]+nList[i+1:]))
return result

演练 - 使用 reduce 函数将所有长度为 n-1 的列表相乘并添加到变量结果中。

Answer 2

如果只想尽量减少乘法的次数，可以用加法代替所有的乘法，像这样：

// Compute 1*2*…*n
mult_all(n):
    if n = 1
        return 1
    res = 0
    // by adding 1*2*…*(n-1) an entirety of n times
    for i = 1 to n do
        res += mult_all(n-1)
    return res

// Compute sum of 1*2*…*(i-1)*(i+1)*…*n
sum_of_mult_all_but_one(n):
    if n = 1
        return 0
    // by computing 1*2*…*(n-1) + (sum 1*2*…*(i-1)*(i+1)*…*(n-1))*n
    res = mult_all(n-1)
    for i = 1 to n do
        res += sum_of_mult_all_but_one(n-1)
    return res

Answer 3

这是一个适用于 javascript 的答案。这不是最快的方法，因为它没有优化，但如果你只想找到答案，它应该可以工作。

function combo(n){
var mult = 1;
var sum = 0;
for (var i = 1; i <= n; i++){
    mult = 1;
    for (var j = 1; j<= n; j++){
        if(j != i){
            mult = mult*j;
        }
    }
    sum += mult;
}
return (sum);
}

alert(combo(n));

Answer 4

这里有一种不"cheat"的方法，即用重复的加法代替乘法或使用除法。这个想法是用

替换你的表达式

1*2*3*4 + 5*(1*2*3 + 4*(1*2 + 3*(1 + 2)))

这对数字 1 到 5 使用了 9 次乘法。一般来说，我认为乘法次数会比第 (n-1) 个三角数 n * (n - 1) / 2 - 1 少一个。这是 Python 代码，它存储中间阶乘值以将乘法次数减少到 6，或者通常是 2 * n - 4，加法计数相同（但其中一半只是加 1）：

def f(n):
    fact = 1
    term = 2
    sum = 3
    for j in range(2, n):
        fact *= j
        term = (j + 1) * sum
        sum = fact + term
    return sum

找到最快算法的唯一方法是用一种语言对所有算法进行编码，并且运行每个算法都使用一个计时器。

数字组合的总和

Sum of combinations of numbers

math

combinations

numbers

discrete-mathematics