permutations in c++

Question

I have an Array with some values e.g

A=[a,b,c];

What would be the easiest/fastest way in c++ to calculate the following:

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

In this case a*c != c*a

In the real case i have differently sized big arrays and will take the values for a,b & c from other arrays.

/thanks in Advance

Answer 1

try out the code :

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 2

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

But unless A have variable size you might be better of just writing this formula down as it is:

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

Answer 3

Unless I'm missing something, it should be as easy as:

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 4

Here is a solution that trades 9 ifs for 3 multiplications and 3 subtractions.

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 5

Perhaps so (assuming you actually want to add both a * b and 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;
    }
}

And may-be even a cleverer version that would reduce the algorithmic complexity (O(n) vs O(n*n)):

For each member a[x] in the array, you want to add up:

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

which after factoring out the common factor is the same as:

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

Now the sum of all array items can be calculated just once:

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 6

The code by Visitor can be simplified further:

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

And I guess a temporary could be used:

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

And of course the squaring step can also be done using 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: A simple loop with a single pass:

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

I would use shorter loops:

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

Then this negates the need for the if (i != j) check and does fewer i++ and j++ and i<2 and j<3 calls.