Sum of Product of subset of size upto K

Anyone tell me how to find sum of the product of subset of size upto K
i.e. K=3;
 
arr[]={1,2,3,4,5};

for k=1 ans1= 1+2+3+4+5
for k=2 ans2= 1*(2+3+4+5)+2*(3+4+5)+3*(4+5)+4*5
for k=3 ans3= 1*2*(3+4+5)+1*3*(4+5)+1*4*5+2*3*(4+5)+2*4*5+3*4*5

The final answer is ans1+ans2+ans3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
program main
   implicit none
   integer :: k = 3
   integer, allocatable :: A(:), S(:)
   integer i, kk

   A = [ 1, 2, 3, 4, 5 ]
   kk = min( size(A), k )
   allocate( S(0:kk) );   S = 0;   S(0) = 1
   do i = 1, size( A )
      S(1:kk) = S(1:kk) + A(i) * S(0:kk-1)
   end do
   print *, sum( S ) - 1
end program main

325

Either use gfortran, or an online compiler:
https://onlinegdb.com/Hk0fYiMLH
https://rextester.com/SDIP30298


Alternatively, you can do it in Python:
1
2
3
4
5
6
7
8
import numpy as np
k = 3
A = [ 1, 2, 3, 4, 5 ]
kk = min( len( A ), k ) + 1
S = np.zeros( kk, dtype=int );   S[0] = 1
for a in A:
   S[1:kk] = S[1:kk] + a * S[0:kk-1]
print( S.sum() - 1 )

https://rextester.com/OFSRO22356
Last edited on
A more general approch to do this? and even for large length of array and large K. A time efficient approch?
it may be easy to write, but python does integer math in an emulator mode. The last time I tried to do math in python, a very simple crc32, it was *100* times slower than C++, clocking 45 seconds to c++'s 0.4 per million.

scipy might do the trick, but it was not accepted for what we were doing.

I don't know if this is 'normal' … I gave up after 2 or 3 code blocks were all insanely slow.

neural net engines RELY on sum of products work. Often this is uploaded to a graphics card to use the bajillion processors on there in parallel. Maybe look at ANN techniques for ideas?
Last edited on
@jonnin, I simply put the python example in because it was (fractionally) easier to understand and I didn't want to just give the OP the C++ version without him/her trying to write some code. As I understand it, though, numpy arrays use pre-compiled C.

If I wanted speed I'd just do it in Fortran because the array-section operations are both convenient to write and blisteringly fast.

The time-complexity is O(N.K) and I don't see any easy way of improving that.
Last edited on
I don't either. You can make it parallel, perhaps, but you can't do less work.
Fortran forever :)
Last edited on
What was your approch? @lastChance
Can you explain?
Include the elements of A[] one by one.

At any stage S[j] holds the sum of products of j numbers. When you include a new element then each sum of j elements is increased by the previous sum of j-1 elements multiplied by the new element of A.

In C++ you'd probably need a loop (in reverse order) to do the update, but Fortran and Python have convenient array sections to simplify that.

For a convenient update formula it is convenient to take the (unused) S[0] as 1, but remember to subtract it from the sum at the end.
Last edited on
I'm having trouble understanding the problem. Here's now I (mis)understand it:

Find sum of the product of subset of size up to K
Consider K=2 and the set = {1,2,3,4,5}

Subsets of size 1: {1} {2} {3} {4} {5}
Product of subsets of size 1: (same as above)

Subsets of size 2: {1 2} {1 3} {1 4} {1 5} {2 3} {2 4} {2 5} {3 4} {3 5} {4 5}
Product of subsets of size 2: 2 3 4 5 6 8 10 12 15 20

Sum of all products: 1+2+3+4+5 + 2+3+4+5+6+8+10+12+15+20
= 15+85 = 100

Thanks.
@lastChance a working example for that.
Let's take A = [1, 2, 3] & k = 2.

Last edited on
@lastChance
>>>>>> S[1:kk] = S[1:kk] + a * S[0:kk-1]
Can you just simplify this such that its easier to understand preferably to a two loop version.
or explain this line
Last edited on
Hello @dhayden, I'm not sure whether you agree with me or not.

Your example is indeed what you would get for K=2.
The code given in my Fortran and Python examples is for K=3.

For K up to 5 you can run it online:
https://rextester.com/SZDQY78041

         719
S(1) = 15
S(2) = 85
S(3) = 225
S(4) = 274
S(5) = 120


So,
S(1) = 15 (as you worked out)
S(2) = 85 (as you worked out)
S(3) = 225 (this means that S(1) + S(2) + S(3) = 325 in the original question)


@sawingboat, I think you should be able to convert those array sections to a loop (though you must loop downwards to get the update correct, or the update of k-1 will contaminate the update of k).

I'm pretty sure this isn't a codechef live competition, but you are sufficiently demanding that I suspect it is live homework or competition somewhere.



sawingboat12 wrote:
@lastChance a working example for that.
Let's take A = [1, 2, 3] & k = 2.

Answer is 6 + 11 = 17

S(1) = 1 + 2 + 3 = 6
S(2) = 2 * 3 + 1 * 3 + 1 * 2 = 11
So S(1) + S(2) = 17

-----

The way my code would do it:
Start with S(0)=1, S(1) = S(2) = 0

Include value 1: then
S(0) = 1,
S(1) = 0 + 1 * 1 = 1
S(2) = 0 + 1 * 0 = 0

Include value 2: then
S(0) = 1
S(1) = 1 + 2 * 1 = 3
S(2) = 0 + 2 * 1 = 2

Include value 3: then
S(0) = 1
S(1) = 3 + 3 * 1 = 6
S(2) = 2 + 3 * 3 = 11

At the end, S(1) = 6, S(2) = 11 and S(1) + S(2) = 17

Last edited on
Include value 2: then
S(0) = 1
>> S(1) = 1 + 2 * 1 = 3 Lets consider this expression in form of (a + b * c) a seems fine, b is okay, what's c?
>> S(2) = 0 + 2 * 1 = 2 Similarly what is c here? How is 1 coming in place of c here?
Last edited on
sawingboat12 wrote:
Include value 2: then
S(0) = 1
>> S(1) = 1 + 2 * 1 = 3 Lets consider this expression in form of (a + b * c) a seems fine, b is okay, what's c?

c is the value of S(0) after 1 was included (i.e. the end of the previous loop)


>> S(2) = 0 + 2 * 1 = 2 Similarly what is c here? How is 1 coming in place of c here?

c is the value of S(1) after 1 was included (i.e. the end of the previous loop)




In general, let S(k) be the sum of a product of k elements. S(k) increases as you add successive members of the set. After inclusion of the nth term:
S(k)n = S(k)n-1 + an * S(k-1)n-1      = sum of k-product without an + sum of k-product with an

(with the convenience value S(0) = 1 always, in order to force S(1) just to be the sum of values.)



That is what has been coded. I just used array sections rather than loops, because they are usually heavily optimised where available.



BTW, where exactly does this problem arise from?
Last edited on
Topic archived. No new replies allowed.