Перестановки в 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 и б * а):

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 (п) против O (N * N)):

для каждого члена а [х] в массиве, вы хотите добавить до:

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

Answer 2

попробовать код:

int sum = 0; 

for(int i=0 ; i < size ; i++) 
{ 
    int tmp = 0; 
    for(int j=0 ; j < size ; j++) 
    { 
      if(i != j) 
      tmp += a[i] * a[j]; 
    } 
    sum += tmp; 
} 

Answer 3

int SUM = 0; 
for (int i = 0; i < 3; i++) { 
    for (int j = 0; j < 3; j++) { 
     if (i != j) { 
      SUM += A[i] * A[j]; 
     } 
    } 
} 

Но если A не имеют переменный размер вы могли бы быть лучше просто писать эту формулу вниз, как это:

int SUM = A[0] * A[1] + ...; 

Answer 4

Если я что-то не хватает, это должно быть так же просто:

int sum = 0; 

for(unsigned int i = 0; i < ARRAYSIZE; i++){ 
    for(unsigned int j = 0; j < ARRAYSIZE; j++){ 
     if(i != j){ 
      sum += A[i] * A[j]; 
     } 
    } 
} 

Answer 5

Это решение, которое торгует 9 ifs для 3 умножений и 3 вычитаний.

int sum = 0; 
for (int i = 0; i < 3; ++i) 
{ 
    for (int j = 0; j < 3; ++j) 
    { 
     sum += A[i] * A[j]; 
    } 
    sum -= A[i] * A[i]; 
} 

Answer 6

Код по Visitor может быть упрощена далее:

const int array_sum(std::accumulate(a, a + array_size, 0)); 
int sum(array_sum * array_sum); 
for (int i = 0; i < array_size; ++i) { 
    sum -= a[i] * a[i]; 
} 

И я предполагаю, что временный мог б е используется:

const int array_sum(std::accumulate(a, a + array_size, 0)); 
int sum(array_sum * array_sum); 
for (int i = 0; i < array_size; ++i) { 
    const int tmp(a[i]); 
    sum -= tmp * tmp; 
} 

И, конечно, шаг возведения в квадрат также можно сделать с помощью STL:

const int array_sum(std::accumulate(a, a + array_size, 0)); 
std::transform(a, a + array_size, a, a, std::multiplies<int>()); // store in a 
const int sum(array_sum * array_sum - std::accumulate(a, a + array_size, 0)); 

EDIT: Простой цикл за один проход:

int array_sum(0), square_sum(0); 
for(int i(0) ; i < array_size; ++i) 
{ 
    int tmp(a[i]); 
    array_sum += tmp; 
    square_sum += tmp * tmp; 
} 
const int sum( array_sum * array_sum - square_sum); 

Answer 7

Я хотел бы использовать более короткие контуры:

int SUM = 0; 
for (int i = 0; i < 2; i++) { 
    for (int j = i+1; j < 3; j++) { 
     SUM += A[i] * A[j]; 
     SUM += A[j] * A[i]; 
    } 
} 

Тогда это отрицает необходимость проверки if (i! = j) и делает меньше i ++ и j ++ и i < 2 и j < 3 вызова.