查找与乘子集的总和

比方说，我们已经得到了一套查找与乘子集的总和

{a_1, a_2, a_3, ..., a_n}

的目标是发现我们以下列方式产生了一加：我们发现，其长度为3的所有子集，然后乘以每个子集的元素（子集{b_1, b_2, b_3}的结果将是b_1*b_2*b_3）。最后，我们总结所有这些产品。

我正在寻找最短的时间执行算法。

例

SET: {3, 2, 1, 2} 

Let S be our sum. 

S = 3*2*1 + 3*2*2 + 2*1*2 + 3*1*2 = 28

来源

2013-11-01 Atomic Tomq

'{3，2，1,2}'是不是一个组* *。这是一个* multiset */*包* – amit

@amit从这个问题看来，它应该被视为一个集合。 –

@AbhishekBansal不要这么认为 - 他计数2次，每个元素的出现次数都很重要 - 而在* set *中则没有重复次数。 – amit

当允许重复时（如a_1 * a_1 * a_1），计算倍增三元组的总和更容易。这笔钱只是(sum^3)。

由于不允许重复，我们可以将它们相减：(sum^3 - 3*sumsquares*sum)。

但是，上面的公式减去主对角线上的元素3次，而它应该只减一次。需要补偿的是：(sum^3 - 3*sumsquares*sum + 2*sumcubes)。

上述公式没有考虑到3！每个三元组的排列。所以它应该除以3!。

最后，我们有一个线性时间的算法：

给出多集元素的计算总和，平方和，和立方体。
result = (sum^3 - 3*sumsquares*sum + 2*sumcubes)/6

来源

2013-11-01 10:23:19

对不起，没有得到你的答案。在（a + b + c）^ 3的扩展中还有（a^2）* b这样的项。你的公式如何减去这些条款？ –

@AbhishekBansal：对于长度为2（对）的子集，这很容易解释。我们可以将所有可能的对的产品写成矩阵。然后为了得到适当的总和，我们可以将主对角线上方（或下方）的所有元素加在一起。复杂性是O（N^2）。或者，我们可以将每一行相加（它给出a_i *和），然后将所有这些和相加（这给出和^ 2），然后移除主对角线的元素并除以2.现在复杂度为O（N）。我提出的只是将这种方法推广到长度为3的子集。 –

++完整的工作守则C（上Amit的想法跟进）

#include <iostream> 

using namespace std; 

int main() 
{ 
    int s[] = {3, 2, 1, 2}; 

    double sumOfFullList = 0; 
    for (int i = 0; i < 4; i++) 
     sumOfFullList += s[i]; 

    double sum = 0; 

    for (int i = 0; i < 4; i++) { 
     double sumOfList = sumOfFullList - s[i]; 
     sumOfFullList -= s[i]; 
     for (int j = i+1; j < 4; j++) { 
      sumOfList -= s[j]; 
      sum += s[i]*s[j]*(sumOfList); 
      //cout << s[i] << " " << s[j] << " " << sumOfList; 
     } 
    } 

    cout << sum << endl; 
    return 0; 
}

输出：

来源

2013-11-01 09:06:02

请注意，假设所有正数，'sumOfList'将迅速变为负数 – amit

@amit oops试图纠正它。 –

看起来很好（+1） – amit

这里是一个O(n^2)方法：

sum = SUM(list) 
answer = 0 
for each i from 0 to n: 
    sum -= list[i] 
    remains = sum 
    for each j from i+1 to n: 
     remains -= list[j] 
     answer += list[i] * list[j] * (remains)

它的工作原理，因为x,y你需要总结x*y*z（所有元素z）每两个元素，但所有可能z值的总和是SUM(list) - x - y。

所以，与其做：x*y*z1 + x*y*z2 + ... + x*y*z(n-2)，你基本上做x*y*(z1 + ... + z(n-2))

编辑： Editted多计数由于只在“尾巴”不乘，由@AbhishekBansal提及。您需要仅将每个元素与列表的“尾部”相乘，其中尾部是x,y中最后一个元素之后的所有元素。

来源

2013-11-01 09:07:29 amit

哇，没有想到这一点。 –

我不知何故认为它可能有重复。 –

@AbhishekBansal TBH，我不确定（重读后）OP真正需要什么，他的例子增加了3 * 2 * 1和3 * 1 * 2，但只计算了3 * 2 * 2一次。 – amit

查找与乘子集的总和

回答

相关问题