All possible linear combinations of positive half-integers with coefficients +/- 1

Question

This will be a simple problem on paper, but the brute force method is not really suitable for a computer, so I'm after a tricky algorithm that works in practice too: if $n$ positive half-integers $p_i$ are given, one can form $2^n$ linear combinations with coefficients $\pm 1$:

$$P = e_1 p_1 + \ldots + e_n p_n$$

Where $e_i = \pm 1$. With given $p_i$ one obtains $2^n$ values for $P$. Let's call $\mu(P)$ the multiplicity of $P$, the number of linear combinations that gives $P$. My goal is to know this $\mu(P)$. On a computer I could just loop over $2^n$ items given by n-length strings of +1 and -1's and record each $P$, but if $n$ is large ($n>64$) this becomes problematic if 64 bit integers are used (unsigned long long int in C). And also it becomes time consumong if $n$ is larger than 64 and some arbitrary precision library is used.

Is there a tricky way to obtain $\mu(P)$ that does not require a loop over $2^n$ elements?

Answer 1

Indeed it is the Subset Sum Problem (or closely related to it). This problem asks essentially whether $\mu(P)>0$. It is only weakly NP-complete, and there is a pseudopolynomial dynamic-programming algorithm for it. You can find it in any textbook on algorithm design. More precisely, if the sum of the $p_i$'s is $B$, you can solve it in $O(nB)$ time. Whether this is practical depends on the size of the numbers. (The other suggested solutions, which multiply polynomials, are another way to express the same algorithm. Your question suggests that $\mu(P)$ is not just 0 or 1, and apparently, the numbers are not so big.)

Answer 2

Hm, maybe rewriting this by adding $p_1+p_2+\dots$ on both sides, and dividing by two, then this is isomorphic to $P' = f_1 p_1 + \dotsc$ where $f_i$ is either 0 or 1. Thus, it is the number of ways to construct $P'$ as a sum using 0 or one $p_1.$ Thus, expand $\prod_i (1+x^{p_i})$ and look for the coefficient of $x^{P'}$ to find the number you are looking for.

I don't know if this helps you, but maybe this interpretation helps a bit. What do you know of the numbers $p_i$?

Answer 3

I don't know about tricky, but you can use Per's suggestion more directly. The problem is that is mu is uniform, you will have 2^n possiblities for P, and not enough memory to store them.

The idea is to compute product over i of (x^-p_i + x^p_i). If all the p_i are 1, this will have mu(P) resemble a row of Pascal's triangle, with each new row formed by adding translates of the previous row. This is the best case, since you will need to store O(n) coefficients. Hopefully, you will need as few as O(n^k) coefficients for small k, but there is the potential for exponentially many coefficients, one for each possible value of P. If the p_i occupy a small interval though, it should not be too bad.

Gerhard "Ask Me About System Design" Paseman, 2013.03.05

Answer 4

Your problem is equivalent to a well-known problem in banking. Transform your problem as suggested by Per. Now imagine a bank holding a portfolio of bonds issed by obligors numbered $i=1,2,,\ldots,n$ and the bank owns bonds worth $p_1,p_2,\ldots,p_n$ issued respectively by these obligors. The $f_i$ variables correspond to indicator variables: $f_i=1$ means obligor $i$ defaulted (in a twelve month period, say), otherwise the value is 0. The value $\mu(P')$ is proportional the probability that the portfolio will sustain a loss of $P'$.

This discrete distribution approaches a continuous curve as $n\to\infty$. There are well-known theories to estimate this curve which come under the heading "Saddlepoint Approximations". For example, see "Saddlepoint Approcimations with Applications" by Ronald Butler, publ by Cambridge Unic Press. The classic is "Saddlepoint Approximations" by Jens Lensen publ by Oxford, but it's expensive.