4

假设我们有一套

{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
4

3 回答 3

5

这是一种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))

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

于 2013-11-01T09:07:29.397 回答
2

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

输出：

28
于 2013-11-01T09:06:02.023 回答
2

当允许重复时（如 a_1*a_1*a_1）更容易计算相乘的三元组的总和。这个总和只是(sum^3)。

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

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

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

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

  1. 计算给定多集元素的总和、平方和、立方和。
  2. result = (sum^3 - 3*sumsquares*sum + 2*sumcubes)/6
于 2013-11-01T10:23:19.237 回答