Sum of Product of subset of size upto K

[cool123dude]

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

[lastchance]

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:

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

[sawingboat12]

A more general approch to do this? and even for large length of array and large K. A time efficient approch?

[jonnin]

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?

[lastchance]

@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.

[jonnin]

I don't either. You can make it parallel, perhaps, but you can't do less work.
Fortran forever :)

[sawingboat12]

What was your approch? @lastChance
Can you explain?

[lastchance]

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.

[dhayden]

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.

[sawingboat12]

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

[sawingboat12]

@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

[lastchance]

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

[sawingboat12]

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?

[lastchance]

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?