4
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ It is very unclear what you mean, but maybe you are looking for this: en.wikipedia.org/wiki/Newton's_identities $\endgroup$ – Sasho Nikolov Jun 18 '14 at 18:54
  • 1
    $\begingroup$ @Kaveh: I tried to edit the wording to clarify what I am looking for. This should be something rather basic math, I am sure. $\endgroup$ – Alexander Galkin Jun 18 '14 at 19:38
  • $\begingroup$ 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. $\endgroup$ – D.W. Jun 18 '14 at 21:24
  • $\begingroup$ Sum of all nonempty subset products? Dynamic programming. SubSum(N) = $s_{n}$ * SubSum(N-1) + SubSum(N-1) + $s_{n}$ $\endgroup$ – Chad Brewbaker Jun 21 '14 at 20:26
  • $\begingroup$ One question. Is $k$ fixed or does $k$ go from 1...n? $\endgroup$ – Chad Brewbaker Jun 21 '14 at 20:28
10
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
7
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ 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." $\endgroup$ – Joshua Grochow Jun 18 '14 at 22:48

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.