Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

We are given a list $S$ containing $n$ numbers $S=(s_1,\ldots, s_n)$. Let $S \choose k$ be the set of all possible $k$-combinations from $S$ (i.e. size $k$ subsets of $S$). We want to compute the following expression:

$$ \sum_{A\in {S \choose k}} \prod_{x \in A} x$$

Is there an algorithm for this problem that works much better than the trivial one which goes over all subsets and computing and summing up all products?

share|improve this question
1  
It is very unclear what you mean, but maybe you are looking for this: en.wikipedia.org/wiki/Newton's_identities –  Sasho Nikolov Jun 18 at 18:54
1  
@Kaveh: I tried to edit the wording to clarify what I am looking for. This should be something rather basic math, I am sure. –  Alexander Galkin Jun 18 at 19:38
    
@Kaveh: Great, thank you a lot!! –  Alexander Galkin Jun 18 at 20:03
    
You are asking for an efficient way to evaluate a specific multivariate symmetric polynomial at a specific input. There's lots known about symmetric polynomials; that might help you find a good solution. –  D.W. Jun 18 at 21:24
    
Sum of all nonempty subset products? Dynamic programming. SubSum(N) = $s_{n}$ * SubSum(N-1) + SubSum(N-1) + $s_{n}$ –  Chad Brewbaker Jun 21 at 20:26
show 1 more comment

2 Answers 2

up vote 10 down vote accepted

Consider the polynomial $p(t) = \prod_{i=1}^n (s_i t + 1)$. Then we want to compute the coefficient of $t^k$ in $p(t)$. We can compute $p(t)$ using fast polynomial multiplication and then output the coefficient of $t^k$.

Say, partition $n$ polynomials $s_i t + 1$ into pairs and multiply the product of polynomials in each pair (using the standard fast polynomial multiplication algorithm). Then divide the obtained $n/2$ polynomials into pairs, and compute the product in each pair. Repeat this step over and over until we get one polynomial. At each step we can get rid of terms of degree higher than $k$.

Also note that if $k$ is small, we can just use dynamic programming.

share|improve this answer
add comment

I guess the following trick is essentially "Newton's identities", but this seems a much more straightforward application to your question than what's on the wikipedia page. I've seen this mentioned on math.se before but don't know of a particular reference.

First, we write down the polynomial $$ p(x) = \prod_{i=1}^n (x + s_i) . $$

By simply multiplying out this polynomial (efficiently! it is $n$ products of degree $\leq n$ polynomials), we can write it as $$ p(x) = \sum_{j=1}^n \alpha_j x^j. $$ where $\alpha_j$ is the sum of all coefficients of $x^j$, that is, all possible products of $n-j$ of the $s_i$s. In particular, $$ \alpha_{n-k} = \sum_{A \in {S \choose k}} \prod_{s \in A} s .$$

share|improve this answer
1  
This is typically credited in the TCS literature to Ben-Or, viz. the private communication from Ben-Or to Nisan & Wigderson cited in "Lower bounds on arithmetic circuits via partial derivatives." –  Joshua Grochow Jun 18 at 22:48
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.