用乘法求子集的总和 [英] Find sum of subset with multiplication

问题描述

假设我们有一个集合

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

我们的目标是找到我们通过以下方式创建的总和:我们找到所有长度为 3 的子集，然后将每个子集的元素相乘(对于子集 {b_1, b_2, b_3}结果将是 b_1*b_2*b_3).最后我们总结了所有这些产品.

The goal is to find a sum that we create in the following way: We find all subsets whose length is 3, then multiply each subset's elements (for the subset {b_1, b_2, b_3} the result will be b_1*b_2*b_3). At the end we sum up all these products.

我正在寻找一种最短执行时间的算法.

I am looking for a shortest time-execution algorithm.

例子

SET: {3, 2, 1, 2}

Let S be our sum.

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

推荐答案

在允许重复的情况下(如 a_1*a_1*a_1)更容易计算相乘的三元组之和.这个总和就是(sum^3).

It is easier to calculate sum of multiplied triplets when repetitions are allowed (like a_1*a_1*a_1). This sum is just (sum^3).

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

Since repetitions are not allowed, we could just subtract them: (sum^3 - 3*sumsquares*sum).

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

But the above formula subtracts elements on main diagonal 3 times while it should be subtracted only once. Need to compensate this: (sum^3 - 3*sumsquares*sum + 2*sumcubes).

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

The above formula does not take into account 3! permutations of each triplet. So it should be divided by 3!.

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

Finally we have a linear-time algorithm:

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

这篇关于用乘法求子集的总和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！