0
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Do you think algorithms like binary indexed tree which compute partial sums can be helpful here? $\endgroup$ – dineshdileep Dec 16 '16 at 6:10

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.