1

Topic: Re: accordion Extension

Hello, Kodt, you wrote: It is given: a dial-up of integer values X [] - width of some segments. And target value D - width of a total segment on which we project them so in the total they occupy it all - acquiring values W [] (D). Naturally, there are rounding off problems. It is necessary to make it as much as possible beautifully, that is, to observe a row of conditions: Same  1) the Monotonicity: at the monotonous magnification of the total each item too monotonically grow. Certainly, will tell more precisely - do not decrease, because at a total increment on 1 it is clear that this  will be given only to any one item.> the bad method W [i] = floor (D*X [i]/sum (X)) already therefore disappears - everything, except last, we give proportional values, approximating downwards> W [last] = D-sum (W [0. last)) - last we give all remained because it rakes up residual in a range (0. . n-1) where n - the amount of elements and as a result skips Besides, is the classical approach: you consider separately value how many it is necessary to select (D*X [i]/sum (X)) and how many  it is actually selected. You take a difference (it can be both positive, and negative) memberwise and you call it a deficit. And  it is necessary to add always to that element, at which a deficit the greatest. It gives observance both this requirement, and remaining. Well that is from this it is already possible to receive naive implementation. For example, you decompose D = sum (X) * Q + R. The first part sum (X) *Q  you arrange directly (there there will be no rounding-off errors). And residual from R  you arrange the above-stated method through a deficit (it is a maximum one sorting of elements according to a deficit after initiating allocation).

2

Re: Re: accordion Extension

Hello, Kodt, you wrote: you Consider, you save an error desiredW = 0.0f; for i in X {desiredW + = D*X [i]/sum (X); if i == X'last {W [i] = desiredW;} else {W [i] = floor (desiredW);} desiredW - = W [i];}

3

Re: Re: accordion Extension

Hello, Kodt, you wrote: W>> Besides, there is a classical approach: you consider separately value how many it is necessary to select (D*X [i]/sum (X)) and how many  it is actually selected. You take a difference (it can be both positive, and negative) memberwise and you call it a deficit. W>> and  it is necessary to add always to that element, at which a deficit the greatest. It gives observance both this requirement, and remaining.> That means "how many it is necessary to select" and "how many is actually selected"? Where here there are integer numbers and in what side there is a rounding off? I, perhaps, will answer with a code sketch: def stretch (weights, d): sum_w = sum (weights.values() q, r = divmod (d, sum_w) desire = {i:(d * float (weight) / sum_w) for (i, weight) in weights.items ()} result = {i:(weight * q) for (i, weight) in weights.items ()} def deficit (k): return desire [k] - result [k] while r> 0: inc_idx = max (weights, key=deficit) # TODO: use heap here result [inc_idx] = result [inc_idx] + 1 r = r - 1 return result items = {' a ':10, ' b ':20, ' c ':30, ' d ':1000} print (stretch (items, 5332)) a:50 b:101 c:151 d:5030 the Dial-up [10,20,30,1000] should be scaled the same as [1,2,3,100]. Well this property too is finite is fulfilled.

4

Re: Re: accordion Extension

In practice faced with similar, but there problems there was another. In  a file there was a dial-up of calls and their cost as there was a total cost. The problem was that cost was calculated to 4th sign after a comma, and in a file was saved to within the second. Total value was produced to within 4th sign with the subsequent rounding off. I.e. the condition  [x] = [S] 0.01 should be satisfied. A classical problem of accumulation of rounding error. But there the small chest simply opened, it was necessary to consider at addition of the next value the total approximated and the approximated total. If the difference became more than 0.01 to add or take away to the next approximated value 0.01 for compensating. At you a problem that lengths of segments are already approximated. But it is possible similar to apply something: int sum = 0; int cnt = (sizeof (X) / sizeof (X [0])); for (int i = 0; i <cnt; i ++) sum + = X [i]; double roundErr = double (D - sum) / cnt; double acc = 0; for (int i = 0; i <cnt; i ++) {acc + = roundErr; double comp = int (acc); X [i] + = comp; acc - = comp;}

5

Re: Re: accordion Extension

Hello, Kodt, you wrote: At me a problem in not simply to scatter the total on items but that for a series successively the going totals conditions - properties of a monotonicity and a priority just about it were satisfied. . I.e. that straight lines on the schedule did not turn to curves and on the contrary.

6

Re: Re: accordion Extension

Hello, Kodt, you wrote: Found a counterexample for your algorithm. About, I precisely was mistaken and did not understand at once your problem. It is possible to provide a monotonicity making a deficit incremental: def stretch (weights, d): sum_w = sum (weights.values ()) q, r = divmod (d, sum_w) result = {i:(weight * q) for (i, weight) in weights.items ()} def deficit (k): return weights [k] * (d - r + 1) - result [k] * sum_w while r> 0: inc_idx = max (weights, key=lambda i: (deficit (i), weights [i], i)) result [inc_idx] = result [inc_idx] + 1 r = r - 1 return result But it, of course, spoils trivial implementation with a heap (However, apparently, that is possible simply from approximate solution, and then it to "refine" that there was a monotonicity and other. Somehow so: def stretch (weights, d): sum_w = sum (weights.values ()) safe = d - 2 * len (weights) if safe> 0: result = {i:int (float (safe) * weight / sum_w) for (i, weight) in weights.items ()} else: result = {i:0 for i in weights} r = d - sum (result.values ()) def deficit (k): return weights [k] * (d - r + 1) - result [k] * sum_w while r> 0: inc_idx = max (weights, key=lambda i: (deficit (i), weights [i], i)) result [inc_idx] = result [inc_idx] + 1 r = r - 1 return result Here already r = O (|W |) and consequently expensive operations it is necessary to do a little.

7

Re: Re: accordion Extension

Hello, Kodt, you wrote: It is given: a dial-up of integer values X [] - width of some segments. And target value D - width of a total segment on which we project them so in the total they occupy it all - acquiring values W [] (D). #!/usr/bin/lua function garmoshka (x) local S,n=0,#x for i=1, n do S=S+x [i] end return function (D) local a, b, d = {}, {}, 0 for i=1, n do a [i] =math.floor (x [i] *D/S) b [i] = (x [i] *D) %S d=d+a [i] end while d <D do for i=1, n do b [i] =b [i] +x [i] if b [i]> =S then b [i] =b [i]-S a [i] =a [i] +1 d=d+1 if d> big_smile then break end end end end return an end end function write (f...) io.write (string.format (f...)) end function show (a) local S=0 for i=1,#a do write ("%d", a [i]) S=S+a [i] end write ("S = % d\n", S) end scale=garmoshka {30,3,3,31,30} for D=1,200 do show (scale (D)) end

8

Re: Re: accordion Extension

Hello, Kodt, you wrote: It is given: a dial-up of integer values X [] - width of some segments. And target value D - width of a total segment on which we project them so in the total they occupy it all - acquiring values W [] (D). Naturally, there are rounding off problems. Purely thought in air - can be, any of subtasks of package of a satchel approaches...

9

Re: Re: accordion Extension

10

Re: Re: accordion Extension

Too most, but for big n #include <stdio.h> #include <stdlib.h> int scale_cmp (const void* a, const void *b) {return * (int *) a> * (int *) b;} void scale (int n, int *x, int *w, int D, int *t) {int d, i, s, k; s=0; for (i=0; i <n; i ++) s + = x [i]; d=0; for (i=0; i <n; i ++) {d + = w [i] = (x [i] *D)/s; t [i] = (((w [i] +1) *s+x [i]-1)/x [i]) *n+i;} qsort (t, n, sizeof (*t), scale_cmp); for (k=0; d <D; k ++, d ++) {i=t [k] %n; w [i] ++; t [k] = (((w [i] +1) *s+x [i]-1)/x [i]) *n+i; if (t [k] <t [n-1]) {if (t [k]> t [k+1]) qsort (t+k, n-k, sizeof D); for (i=0; i <n; i ++) printf ("%2d", w [i]); printf ("\n");} return 0;}

11

Re: Re: accordion Extension

Hello, Kodt, you wrote: It is given: a dial-up of integer values X [] - width of some segments. skipped For extension by value R we multiply width of each segment on R, we receive dial-up X1 [], and X [] it is not touched. If R changes - the user tightens a slider besides we work with initial X []. Under comments more low - start up to itself twitches on the value, imperceptible to an eye. But the result will be already here and now.

12

Re: Re: accordion Extension