Sum of Products of Subsets

Question

Given an integer k and a list of integers A of size n, find the product of all subsets in A of size k and sum them together.

For example,

k = 2
n = 4
A = 1 2 3 4

The subsets of size 2 and their products are

1 2 = 2
1 3 = 3
1 4 = 4
2 3 = 6
2 4 = 8
3 4 = 12

which sum together to 35.

Some test cases:

Input

A = 73 36 86 76 5 25 15 95 27 1
n = 10
k = 4

A = 7 16 56 83 14 97 71 24 65 32 75 61 64 73 94 34 10
n = 17
k = 3

Output

499369377

87409828

The input can be in whatever format suits your language best. You can have, for example, the variables A, n, and k set to the input already. The integers in A are not necessarily unique.

Constraints

Functions which solve this question are not allowed, as well as functions which generate subsets. Also, to avoid Θ(n^k) submissions, if a solution is made using a better approach, it will have a -30 character bonus. (-30 is subject to change)

The shortest solution is the winner.

Side Note: It's okay to post solutions which do not follow the rules if it demonstrates the strengths of your language. It just won't be part of the scoring.

For example,

Mathematica (31)

Times@@#&/@A~Subsets~{k}//Total

Answer 1

R - 20

Since the OP said:

Side Note: It's okay to post solutions which do not follow the rules if it demonstrates the strengths of your language. It just won't be part of the scoring.

sum(combn(A,k,prod))

Answer 2

Ruby, O(n*k), 70 - 30 = 40 characters

@r={};r=->a,n,k{@r[[a,n,k]]||=k<1?1:n<1?0:r[a,n-=1,k]+a[n]*r[a,n,k-1]}

if the array can be made global and constant (or if we can ask the caller to clean our cache), we can save seven (or thirteen) more characters.

r=->n,k{@r[[n,k]]||=k<1?1:n<1?0:r[n-=1,k]+@a[n]*r[n,k-1]}

without memoisation, we're at 50 characters, but we don't qualify for the bonus:

r->a,n,k{k<1?1:n<1?0:r[a,n-=1,k]+a[n]*r[a,n,k-1]}

Spaced apart:

r = -> a, n, k {
  k<1 ? 1 :
  n<1 ? 0 :
  r[a, n-1, k] + a[n-1] * r[a, n-1, k-1]
}

With memoization, we get to O(n * k * cost_of_memoization). If the key cannot be hashed well, the cost of memoization quickly grows up. However, a key of the form [[?],#,#] can be hashed quite well, at least in theory. Let's also assume that Ruby arrays cache their hashes, so hashing the same array over and over again takes the same time as hashing it once - linear in size. Also, hash table lookup may be assumed constant-time. So, it is safe to assume that the cost of memoization is constant per lookup, and the initial cost for hashing the array is drowned in the rest of the lookup.

here is the iterative approach:

r={};0.upto(k){|k|0.upto(n){|n|r[[n,k]]=k<1?1:n<1?0:r[[n-=1,k]]+a[n]*r[[n,k-1]]}};r[[n,k]]

Yay! I've beaten Daniero's cheating solution

Answer 3

GolfScript, score 8 0 -3 (27 - 30)

1,*1+\{{*\(@+}+1$1>0+%+}/0=

Expects list a and k on the stack and returns the result.

Example (run online):

[73 36 86 76 5 25 15 95 27 1] 4
1,*1+\{{*\(@+}+1$1>0+%+}/0=
# 499369377

Answer 4

APL (31)

This assumes that A, k and n are already set.

+/{×/A[⍵]}¨({∧/2</⍵}¨∆)/∆←,⍳k⍴n

I.e.:

      A ← 73 36 86 76 5 25 15 95 27 1
      n ← 10
      k ← 4
      +/{×/A[⍵]}¨({∧/2</⍵}¨∆)/∆←,⍳k⍴n
499369377

Explanation:

• ∆←,⍳k⍴n: set ∆ to the flattened (,) coordinate vector (⍳) which is k-dimensional with size n in each dimension. I.e. if k=2 and n=3, you get (1 1) (1 2) (1 3) (2 1) (2 2) (2 3) (3 1) (3 2) (3 3).
• ({∧/2</⍵}¨∆)/: select only those coordinates where the value for the N-th dimension is larger than the value for the (N-1)-th dimension. (I.e. you get (1 2) (1 3) (2 3)). When these sets of coordinates are interpreted as lists of indexes into A, we get the desired subsets.
• {×/A[⍵]}¨: for each subset, get the values from A and multiply them together.
• +/: sum the given values

Answer 5

Python 2: 64-30=34

t=A
exec"t=[sum(t[:i])*A[i]for i in range(n)];"*~-k
print sum(t)

Input is expected as

A = [73, 36, 86, 76, 5, 25, 15, 95, 27, 1]
n = 10
k = 4

Then 499369377 gets printed.

Answer 6

Jelly, 5 bytes

œcP€S

Try it online!

Expects \$A\$ and \$k\$ as input.

Explanation:

œcP€S
œc        Combinations
  P€      Product of €ach
    S     Sum

Answer 7

I'm feeling too lazy to create the subsets on my own, so here's a quick cheating solution.

Ruby, 48 chars

A.combination(k).map{|x|x.inject :*}.inject :+

With A and k are predefined, like for instance so

A=[7,16,56,83,14,97,71,24,65,32,75,61,64,73,94,34,10]
k=3

the result is 87409828.

Answer 8

Python 2, 172-30=142

Similar buildup approach

r=range
m=[x[:]for x in[[0]*n]*k]
m[0][0]=A[0]
for i in r(1,n):m[0][i]=m[0][i-1]+A[i]
for j in r(1,n):
 for i in r(1,k):m[i][j]=m[i][j-1]+m[i-1][j-1]*A[j]
print m[k-1][n-1]

Answer 9

J, 35 bytes

[:+/(>@{[:(</.~+/"1)2#:@i.@^#)*/@#]

Generates the masks for the powerset of A in binary order, selects the masks for k, and operates on each subset.

Usage

   f =: [:+/(>@{[:(</.~+/"1)2#:@i.@^#)*/@#]
   2 f 1 2 3 4
35
   4 f 73 36 86 76 5 25 15 95 27 1
499369377
   3 f 7 16 56 83 14 97 71 24 65 32 75 61 64 73 94 34 10
87409828

Explanation

[:+/(>@{[:(</.~+/"1)2#:@i.@^#)*/@#]  Input: k on LHS, A on RHS
                            #        Get the size of A
                    2      ^         Get 2^len(A)
                        i.@          Get the range [0, 1, ..., 2^len(A)-1]
                     #:@             Convert each to binary
        [:     +/"1                  Take the sum of each binary digits
           </.~                      Partition the list of binary digits by their sum
                                     and box each group
       {                             Select the box at index k
     >@                              Unbox it to get the mask for subsets of size k
                                  ]  Get A
                                 #   Copy from A using each mask
                              */@    For each subset, reduce using multiplication
[:+/                                 Reduce the products using addition and return

Answer 10

APL(NARS), 47 chars, 98 bytes

{+/×/¨{w[⍵]}¨k/⍨{∧/</¨¯1↓{⍵,¨1⌽⍵}⍵}¨k←,⍳⍺⍴≢w←⍵}

I got the idea from "marinus" answer, i don't know if this is ok... test:

  f←{+/×/¨{w[⍵]}¨k/⍨{∧/</¨¯1↓{⍵,¨1⌽⍵}⍵}¨k←,⍳⍺⍴≢w←⍵}
  2 f 1 2 3 4
35
  3 f 7 16 56 83 14 97 71 24 65 32 75 61 64 73 94 34 10
87409828
  4 f 73 36 86 76 5 25 15 95 27 1
499369377

{∧/</¨¯1↓{⍵,¨1⌽⍵}⍵} find if index are all < each other for example

  {∧/</¨¯1↓{⍵,¨1⌽⍵}⍵} 1 2 3 4 5
1
  {∧/</¨¯1↓{⍵,¨1⌽⍵}⍵} 3 2 3 4 5
0
  {∧/</¨¯1↓{⍵,¨1⌽⍵}⍵} 1 3 2 4 5
0
  {∧/</¨¯1↓{⍵,¨1⌽⍵}⍵} 1 2 3 4 9
1

I would prefer this because this work on indices not on values...possible if some repetitions, for list has one meaning...

Answer 11

C# (Visual C# Interactive Compiler), 167 bytes

l=>l.Any()?A(l.Skip(1)).Select(x=>l.Take(1).Union(x)).Union(A(l.Skip(1))):new int[][]{new int[]{}};B=(n,l)=>A(l).Where(x=>x.Count()==n).Sum(x=>x.Aggregate((y,z)=>y*z))

Try it online!

//returns a list of all the subsets of a list
A=l=>l.Any()?A(l.Skip(1)).Select(x=>l.Take(1).Union(x)).Union(A(l.Skip(1))):new int[][]{new int[]{}};

//filter the subsets of the required size and return the sum of the products of their items
B=(n,l)=>A(l).Where(x=>x.Count()==n).Sum(x=>x.Aggregate((y,z)=>y*z))