Computing all possible partial sum-function of a given set of numbers

Question

Let there be $N$ positive numbers given as $\lambda_1\geq\dots\geq\lambda_N$. Now I am interested in the following numbers given as $$\alpha_i=\exp(\frac{\lambda_i}{\lambda})$$ for some positive constant $\lambda$. Define the function $\mathcal{S}(..)$ which takes a subset of these numbers (let me call me them as a sequence) and calculate their products. For example$$\mathcal{S}(\alpha_1,\alpha_2)=\alpha_1\alpha_2$$Also note that $$S(\alpha_1,\alpha_2,\alpha_3)=S(\alpha_1,\alpha_2)S(\alpha_3)$$Also $$\mathcal{S}(\alpha_1,\alpha_3,\alpha_4)={\mathcal{S}(\alpha_1,\alpha_2,\alpha_3,\alpha_4) \over \mathcal{S}(\alpha_2)}$$ and so on. For given $K$ and $N$, we have $NC_K$ possible subsequences of $\alpha_i$'s. Is there a really efficient way of computing $\mathcal{S}(.)$ for all such sequences.

Answer 1

There are ${N \choose K}$ subsequences of length $K$, so outputting $\mathcal{S}(\cdot)$ for all of them will certainly require an output of length at least ${N \choose K}$. Thus, the running time has to be at least ${N \choose K}$. Beware that this is potentially exponential in $N$, depending on the value of $K$, so for some choices of $N,K$ there is no hope for an efficient algorithm to compute all those values.

You can list all those values in approximately ${N \choose K}$ time. Take any algorithm for enumerating all $K$-size subsets of $\{1,2,\dots,N\}$; then it is easy to turn it into an algorithm to do what you want, by keeping track of the product associated with each subset. Note that when you add an element to a subset, with a single multiplication you can update the product (compute the product of the new subset, based on the product of the old subset multiplied by the new element that was added).