0
$\begingroup$

I have

  • $4$ variables $n_1, n_2, n_3, n_4 \in \mathbb N$ that sum to $N$.

  • $4$ positive real constants $c_1 < c_2 < c_3 < c_4$.

Given a particular tuple $(k_1,k_2,k_3,k_4)$, how do I find the partial sum of the ordered (w.r.t. the sum $c_1 n_1 + c_2 n_2 + c_3 n_3 + c_4 n_4$ in an increasing manner) sequence

$$\sum_{n}^{(k_1,k_2,k_3,k_4)} (c_1 n_1 + c_2 n_2 + c_3 n_3 + c_4 n_4)$$

from the minimum to the given $(k_1,k_2,k_3,k_4)$?

I think this problem involves some sorting algorithm. This should already be studied in some linear programming problem but I am just not aware of how to do this efficiently (e.g. using Python).

$\endgroup$
  • 2
    $\begingroup$ What does the notation $\sum_{n}^{(k1,k2,k3,k4)} (c1n1+c2n2+c3n3+c4n4)$ mean? What are the variables, and what are their lower and upper bounds? Perhaps the sum is over $n=(n_1,n_2,n_3,n_4)$, but what are the lower and upper bounds for this sum? What do you mean by "the ordered sequence $\sum \cdots$"? It's hard for me to understand what you are asking. $\endgroup$ – D.W. Jul 25 '17 at 16:05
  • $\begingroup$ @D.W. the summand is c1n1+c2n2+c3n3+c4n4, the lower bound is the min{c1n1+c2n2+c3n3+c4n4} and the upper bound is (k1,k2,k3,k4), the sum is starting from smallest possible (c1n1+c2n2+c3n3+c4n4) in an increasing manner, thus ordered. $\endgroup$ – Shadumu Jul 25 '17 at 20:18
1
$\begingroup$

There's a simple $O(N^3 \log N)$ algorithm, though you might be able to do much better. First, compute all $N^3$ quadruples, and the corresponding linear combinations $\sum_i c_i n_i$. Then sort them. Then find the location of the given quadruple. Then compute the running sum.

$\endgroup$
  • $\begingroup$ Thanks. I am thinking of N~10^5. How shall I do it in Python without occupying too much memory? $\endgroup$ – Shadumu Jul 25 '17 at 12:24
  • $\begingroup$ You will probably need to find a better algorithm first. Unfortunately, implementation is out of scope on this site. $\endgroup$ – Yuval Filmus Jul 25 '17 at 12:25

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.