StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>First generate <code>n</code> random numbers <code>x[i]</code>, sum them up and then divide <code>budget</code> by the sum and you will get <code>k</code>. Then assign <code>k*x[i]</code> to each array element. It is simple and O(n).</p> <p>If you want there at least <code>min</code> value in each element you can modify above algorithm by filling all elements by <code>min</code> (or use <code>k*x[i] + min</code>) and subcontracting <code>n*min</code> from <code>budget</code> before starting above algorithm.</p> <p>If you need working with integers you can approach problem by using real value <code>k</code> and rounding <code>k*x[i]</code>. Then you have to track accumulating rounding error and add or subtract accumulated error from calculated value if it reach whole unit. You have to also assign remaining value into last element to reach whole <code>budget</code>.</p> <p>P.S.: Note this algorithm can be used with easy in pure functional languages. It is reason why I like this whole family of algorithms generating random numbers for each member and then do some processing afterward. Example of implementation in Erlang:</p> <pre><code>-module(budget). -export([distribute/2, distribute/3]). distribute(Budget, N) -> distribute(Budget, N, 0). distribute(Budget, N, Min) when is_integer(Budget), is_integer(N), N > 0, is_integer(Min), Min >= 0, Budget >= N*Min -> Xs = [random:uniform() || _ <- lists:seq(1,N) ], Rest = Budget - N*Min, K = Rest / lists:sum(Xs), F = fun(X, {Bgt, Err, Acc}) -> Y = X*K + Err, Z = round(Y), {Bgt - Z, Y - Z, [Z + Min | Acc]} end, {Bgt, _, T} = lists:foldl(F, {Rest, 0.0, []}, tl(Xs)), [Bgt + Min | T]. </code></pre> <p>Same algorithm in C++ (?? I dunno.)</p> <pre><code>private int[] distribute(int budget, int n, int min) { int[] subBudgets = new int[n]; double[] rands = new double[n]; double k, err = 0, sum = 0; budget -= n * min; for (int i = 0; i < n; i++) { rands[i] = random.nextDouble(); sum += rands[i]; } k = (double)budget/sum; for (int i = 1; i < n; i++) { double y = k*rands[i] + err; int z = floor(y+0.5); subBudgets[i] = min + z; budget -= z; err = y - z; } subBudgets[0] = min + budget; return subBudgets; } </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload