找到子集的乘法总和 [英] 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 ）。最后我们总结一下这些产品。

我要寻找一个最短时间执行算法。

示例

 设置：{3，2，1，2}

设S是我们的一笔。

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

解决方案

这是比较容易计算出乘三胞胎的总和允许重复时（如A_1 * A_1 * A_1）。这笔款项只是（总和^ 3）。

由于重复是不允许的，我们可以只减去他们：（总和^ 3 - 3 * sumsquares *总和）

但是，上述式中减去上主对角线的3倍元素而它应该被减去一次。需要补偿这一点：（总和^ 3 - 3 * sumsquares *之和+ 2 * sumcubes）

以上公式没有考虑到3！每个三元组排列。因此，应该由分 3！。

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

1. 在给定的多集元素的计算总和，平方和，立方体的总和。
2. 的结果=（总和^ 3 - 3 * sumsquares *之和+ 2 * sumcubes）/ 6

Let's say we have got a set

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

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.

Example

SET: {3, 2, 1, 2}

Let S be our sum.

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

解决方案

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).

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

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).

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. Compute sum of given multiset elements, sum of squares, sum of cubes.
2. result = (sum^3 - 3*sumsquares*sum + 2*sumcubes)/6

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