c++ - C++中的排列

Question

我有一个包含一些值的数组，例如

A=[a,b,c];

在 c++ 中计算以下内容的最简单/最快的方法是什么:

int SUM;
SUM= a*b + a*c + b*a + b*c + c*a + c*b;

在这种情况下 a*c != c*a

在实际情况下，我有不同大小的大数组，并将从其他数组中获取 a、b 和 c 的值。

/提前致谢

Answer 1

也许是这样(假设你真的想同时添加 a * b 和 b * a):

for (int i = 0; i < array_size - 1; ++i) {
    for (int j = i + 1; j < array_size; ++j) {
        sum += a[i] * a[j] * 2;
    }
}

甚至可能是一个更聪明的版本，可以降低算法的复杂性(O(n) vs O(n*n)):

对于数组中的每个成员 a[x]，你要加起来:

a[0] * a[x] + a[1] * a[x] + ... + a[n] * a[x] - a[x] * a[x]

在分解出公因数后与:

a[x] * (a[0] + a[1] + ... + a[n] - a[x])

现在所有数组项的总和可以只计算一次:

int array_sum = std::accumulate(a, a + array_size, 0);  //#include <numeric> or use a simple loop
int sum = 0;
for (int i = 0; i < array_size; ++i) {
    sum += a[i] * (array_sum - a[i]);
}