6
\$\begingroup\$

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
\$\endgroup\$
  • 1
    \$\begingroup\$ Please note big-oh denotes an upper bound, so any solution faster than n^k is also O(n^k). Did you mean theta(n^k)? \$\endgroup\$ – John Dvorak Aug 11 '13 at 4:49
  • \$\begingroup\$ Yes, I mean Θ(n^k). Thanks, now I relearned [big-small]-[oh-theta-omega]. \$\endgroup\$ – miles Aug 11 '13 at 5:36
  • \$\begingroup\$ You may use Tr[] instead of Total[] in your Mathematica non-competing example, gaining 3 chars. \$\endgroup\$ – Dr. belisarius Aug 12 '13 at 3:05
  • \$\begingroup\$ Tr[Times @@@ Subsets[A, {k}]] is only 26 ;) \$\endgroup\$ – Nasser Aug 13 '13 at 11:52
  • \$\begingroup\$ n as input of function can be omitted? \$\endgroup\$ – RosLuP Jul 3 at 8:50

11 Answers 11

1
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ You can require the stack to be k a n instead of k a and get rid of two characters. \$\endgroup\$ – John Dvorak Aug 11 '13 at 11:37
  • \$\begingroup\$ did you get inspired by my algorithm, by the way? \$\endgroup\$ – John Dvorak Aug 11 '13 at 11:38
  • \$\begingroup\$ @JanDvorak I though about that but found n being a useless parameter and thus should be omitted (even if the score is then 2 points higher). \$\endgroup\$ – Howard Aug 11 '13 at 12:16
  • \$\begingroup\$ @JanDvorak And the new versions don't even need the n. \$\endgroup\$ – Howard Aug 11 '13 at 12:49
5
\$\begingroup\$

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))
\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ Using r=->a,n,k{...} notation you can even save 5 more characters. Unfortunately, definiting r as hash directly (r=Hash.new{...}) doesn't reduce the character count. \$\endgroup\$ – Howard Aug 11 '13 at 8:28
  • \$\begingroup\$ @Howard I can't use the lambda notation because then r would be a Proc rather than a method, and I would have to call it via r.call. TIL you don't need parentheses around lambda arguments, however. \$\endgroup\$ – John Dvorak Aug 11 '13 at 10:26
  • \$\begingroup\$ Well done! +1 for not being lazy, and a nice explanation of the cost. \$\endgroup\$ – daniero Aug 11 '13 at 11:20
  • \$\begingroup\$ @JanDvorak Call it via r[a,n,k]. \$\endgroup\$ – Howard Aug 11 '13 at 12:14
  • \$\begingroup\$ @Howard ...wow. Thanks! \$\endgroup\$ – John Dvorak Aug 11 '13 at 12:23
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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]
\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

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

\$\endgroup\$
0
\$\begingroup\$

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))
\$\endgroup\$

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.