1
$\begingroup$

I have sequence of integers $a_1, a_2, .., a_n$,
let $S_a = \sum_{i=1}^{N}{a_i}$,
for any $k \in (0; 1)$ I need an algorthim to that maps every $a_i$ into another integer $b_i$ with 2 requirements:

  1. $S_b = \sum_{i=1}^{N}{b_i}$ is as close as possible to $k \cdot S_a$, ideally $S_b = Round(k \cdot S_a)$
  2. $b_i$ is as close as possible to $k \cdot a_i$, ideally $b_i = Round(k \cdot a_i)$

The first requirement is more important.

The problem can be formulated in simpler words as following:
How to generate a sample of a defined size from $N$ bins of different sizes while mantaining the original ratio of elements.

$\endgroup$
0

2 Answers 2

3
$\begingroup$

Compute the prefix sum of the $a_i$, multiply all elements by $k$ and round. Now the desired integers are the pairwise differences of that sequence. The first condition is always honored.

E.g. $a=(3,6,2,7,9), k=0.8\to(3,9,11,18,27)\to(2,7,9,14,22)\to(2,5,2,5,8)$.

$\endgroup$
1
  • $\begingroup$ This is basically how I do geometry with an imprecise ruler, taking care of not accumulating the error. $\endgroup$
    – Stef
    Commented Jan 17, 2023 at 11:19
0
$\begingroup$

If $\sum_{i=0}^{n-1}b_i>k\sum_{i=0}^{n-1}a_i$ then $b_n = \lfloor ka_n\rfloor$, else $b_n = \lceil ka_n \rceil$. This requires only one pass through $\{a_n\}$.

$\endgroup$
3
  • $\begingroup$ This is equal to the accepted solution. $\endgroup$ Commented Jan 19, 2023 at 8:00
  • $\begingroup$ @AndreyGodyaev The accepted solution requires three passes through the data. $\endgroup$ Commented Jan 21, 2023 at 0:06
  • $\begingroup$ That's not true, it is obvious to reduce three passes into one. $\endgroup$ Commented Jan 23, 2023 at 15:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.