Let's say I have an array of numbers {a,b,c,d,e} and want to calculate the sum of product of all triples abc+abd+...+cde. I can calculate it very fast without generating all triples using this formula
F(n,k)= k*F(n-1, k-1)+ F(n-1, k) with two loops

       int[] values={a, b, c, d, e...}; 
       int k = 3;
       int[,] F = new int[values.Count, k];
        for(int i = 0; i < values.Count; i++)       
            for(int j = 0; j < k && j <= i; j++)
                F[i, j] = values[i] * F[i - 1, j - 1] + F[i - 1, j];

Now I have this array of groups {{a1,a2,a3..an}, {b1,b2,b3 ...bn}, {c1,c2...} } and every element of a triple must be in different group. a1*b2*c1 is a valid triple but a1*a2*b1 is not allowed because a1, a2 are in the same group. It's possible to generalize the above algorithm to find the sum of valid triples (quadruple or n-tuple)?

  • $\begingroup$ What's the base case for your F? How do you plan to define F(i,0) and F(0,j)? I'm not quite following how you compute the sum over all triples yet. $\endgroup$ – D.W. Oct 1 '15 at 9:58
  • $\begingroup$ F(i,0)=sum of singles of first i values, F(i,1)=sum of doubles.. j must be<=i $\endgroup$ – albert Oct 1 '15 at 10:08

We have the following identity:

$$\sum_{i,j,k} a_i b_j c_k = (a_1+\dots+a_n) \times (b_1+\dots+b_n) \times (c_1 + \dots + c_n).$$

Therefore, one can compute the sum of all valid triples in $O(n)$ time by first computing the sum of the $a_i'$, the sum of the $b_i$'s, the sum of the $c_i$'s, and then multiplying these three sums. This generalizes: you can find the sum of valid k-tuples in $O(kn)$ time.

| cite | improve this answer | |
  • $\begingroup$ I must replace each group with the sum of its elements. It was so simple. $\endgroup$ – albert Oct 1 '15 at 10:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.