Page 1 of 1

Sum of products of n-tuples

Posted: Thu Oct 01, 2015 8:53 am
by albert_nik
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)= v[k]*F(n-1, k-1)+ F(n-1, k) with two loops

Code: Select all

       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 (quadruples or n-tuples)?

Re: Sum of products of n-tuples

Posted: Thu Oct 01, 2015 12:36 pm
by jaap
Isn't it just this?
Expand
(a1+a2+a3+..+an)*(b1+b2+...+bn)*(c1+c2+...+cn)

Re: Sum of products of n-tuples

Posted: Thu Oct 01, 2015 12:48 pm
by albert_nik
jaap wrote:Isn't it just this?
Expand
(a1+a2+a3+..+an)*(b1+b2+...+bn)*(c1+c2+...+cn)
Expand
I feel so stupid :oops:

Re: Sum of products of n-tuples

Posted: Tue Jun 04, 2019 9:54 am
by SectKace
albert_nik wrote:
Thu Oct 01, 2015 8:53 am
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)= v[k]*F(n-1, k-1)+ F(n-1, k) with two loops

Code: Select all

       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 (quadruples or n-tuples)?
Like it was said, if you wish to modify the code there is a very simple solution. Obviously do not multiple the variables in combinations, rather multiply the value by the count in the set of that variable. Then find the overall product, once performing this simple procedure. Should really take 2 lines of code, in a method with few inputs.