Problem Detail: Say we have a set of numbers $A={a_1, a_2, dots, a_n}$, and we wish to sum over all possible combinations of $k$ terms to compute $$ sum_{substack{C subseteq {1,2,dots,n} |C|=k}} prod_{c in C} a_c $$ Naively this requires $O(kbinom{n}{k})$ operations. This is different from from computing the permanent where there are permutations. Is this problem known to be NP-hard when $n=2k$ or other conditions such as $n=Theta(k^2)$?
Asked By : Tianyang Li
Answered By : Yuval Filmus
You can compute the coefficient of $x^k$ in $$ prod_{i=1}^n (1+xa_i). $$ Alternatively, you can think of this as a dynamic programming algorithm. Let $b(m,ell)$ be the sum of $ell$-combinations of $a_1,ldots,a_m$. We have $$ b(m,ell) = b(m-1,ell) + a_m b(m-1,ell-1), $$ where $b(m,-1) = 0$, $b(0,0) = 1$, and $b(0,ell) = 0$ for $ell neq 0$. What you want is $b(n,k)$. In both cases, there is an optimization that only keeps track of $ell$-combinations for $ell leq k$. In the polynomial representation, it is enough to keep the monomials up to $x^k$. In the dynamic programming approach, we only compute the table up to $b(m,k)$.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/23683 Ask a Question Download Related Notes/Documents
