找出子集乘积的和

Question

找出子集乘积的和

algorithmsumsubsetmultiplicationsubset-sum

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

- Atomic Tomq

1

"{3, 2, 1, 2}" 不是一个“集合”，它是一个“多重集”或“袋子”。 - amit

@amit 从问题来看，它似乎应该被视为一个集合。 - Abhishek Bansal

1

@AbhishekBansal 不这么认为 - 他将2计算了两次，每个元素出现的次数很重要 - 而在一个set中 - 没有重复。 - amit

@amit 是的，它们被视为4个不同的元素，以(4C3)的方式在唯一集合中处理。 - Abhishek Bansal

3个回答

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

输出：

- Abhishek Bansal

请注意，假设所有数字都为正数，“sumOfList”将很快变为负数。 - amit

2

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

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

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

上述公式没有考虑每个三元组的3!排列方式。因此需要除以 3!。

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

1. 计算给定多重集合元素的总和、平方和、立方和。 2. result = (sum^3 - 3*sumsquares*sum + 2*sumcubes)/6

- Evgeny Kluev

抱歉，我没有理解你的答案。在展开（a+b+c）^3的过程中，会出现像（a^2）*b这样的项。你的公式是如何减去这些项的？ - Abhishek Bansal

@AbhishekBansal：对于长度为2（对）的子集，这更容易解释。我们可以将所有可能的对的乘积写成矩阵形式。然后，为了得到正确的总和，我们可以将主对角线上方（或下方）的所有元素相加。复杂度为O（N ^ 2）。或者，我们可以将每一行相加（这给出a_i * sum），然后将所有这些总和相加（这给出sum ^ 2），然后删除主对角线上的元素并除以2。现在复杂度为O（N）。我提出的只是将此方法推广到长度为3的子集。 - Evgeny Kluev

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- amit · Accepted Answer

这里有一种 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 中最后一个元素之后的所有元素。