Quick & Dirty Apportionment
Vector 3:1, page 109
Transcribed from the printed issue; not yet reviewed. Read it in the PDF of the issue, page 109
The apportionment problem is to divide an integer n into m integer parts.
This problem occurs in several different sorts of business applications – financial planning, sales plan allocations, and top-down budgeting to name a few. Apportionment might only play a small role in the overall system, but it is likely to be used extensively in the system, and must work correctly.
This paper presents “Quick and Dirty” APL functions for apportionment. The functions are quick and dirty in that they provide a plausible solution regardless of the application.
Example 1: Straight-line calendarization. A full-year budget of $n is to be evenly divided into 12 monthly amounts.
Solution:
∇ PORTIONS←SUM STRAIGHTLINE PARTS;APPROXIMATIONS;ROUNDERS
[1] APPROXIMATIONS←PARTS⍴⌊SUM÷PARTS
[2] ROUNDERS←(SUM-+/APPROXIMATIONS)DEALBITS PARTS
[3] PORTIONS←APPROXIMATIONS+ROUNDERS
∇
Will it work? SUM and PARTS are assumed to be scalar integers, with PARTS>0. The claim is that:
Informal proof:
By definition of floor:
So multiplied by PARTS:
Which is equivalent to:
So:
Will work and produce rounders such that:
So:
So, with all due apologies for abuses of notation and rigor, we have shown that STRAIGHTLINE will work properly as long as its arguments suit our assumptions about them. So, of all the things that could go wrong with the development of a planning system, we could at least be sure that STRAIGHTLINE will not be among them.
Example 2: Top-down allocation
The company’s objective is to sell n units of a product at its five stores. It will allocate the units according to respective percentage shares of 10 20 27 20 23.
Solution:
∇ PORTIONS←SUM PERCENTAGE PROPORTIONS;APPROXIMATIONS;ROUNDERS
[1] APPROXIMATIONS←⌊SUM×PROPORTIONS÷+/PROPORTIONS
[2] ROUNDERS←(SUM-+/APPROXIMATIONS)DEALBITS⍴APPROXIMATIONS
[3] PORTIONS←APPROXIMATIONS+ROUNDERS
∇
Will it work? SUM is again assumed to be a scalar integer, PROPORTIONS is assumed to be a vector of numbers, real or integer, with:
We again claim that:
Informal proof: If:
then by combination of fractions:
So we can equivalently write SUM as:
By the definition of floor:
and the rest of the proof follows the same reasoning as Example 1.
There is one condition, not uncommon, that PERCENTAGE does not meet: PORTIONS=0 wherever PROPORTIONS=0
This constraint can be taken care of by:
∇ PORTIONS←SUM NONZERO PROPORTIONS
[1] PORTIONS←(PROPORTIONS≠0)\SUM PERCENTAGE(PROPORTIONS≠0)/PROPORTIONS
∇
Example 3: Calendarization of a top-down allocation.
The company has allocated n units in two different ways:
- A full-year allocation to 5 stores.
- A monthly calendarization of the company’s total plan.
It would like to construct a 5 x 12 matrix containing the calendarized plan for each store.
The row totals of the matrix must be identical to the full-year allocation to the stores, and the column totals of the matrix must be identical to the calendarization of the company’s total plan.
Solution:
∇ MATRIX←ROWS CROSS COLUMNS;I;BITS
[1] BITS←ROWS≠0
[2] ROWS←BITS/ROWS
[3] MATRIX←((⍴ROWS),⍴COLUMNS)⍴0
[4] I←1
[5] LOOP:→LOOPEND IF I=⍴ROWS
[6] MATRIX[I;]←ROWS[I]NONZERO COLUMNS
[7] COLUMNS←COLUMNS-MATRIX[I;]
[8] I←I+1
[9] →LOOP
[10] LOOPEND:MATRIX[I;]←COLUMNS
[11] MATRIX←BITS⍀MATRIX
∇
Will it work? ROWS and COLUMNS are assumed to be vectors of non-negative integers, with:
and we claim that:
Informal proof:
The only thing that could go wrong is that some iteration of line 7 leaves some element of COLUMNS negative. At each iteration of line 6 since:
we have the special case of:
and so:
(PROPORTIONS[J]÷SUM) > PROPORTIONS[J]÷+/PROPORTIONS
APROXIMATIONS[J] < PROPORTIONS[J]
PORTIONS ≤ PROPORTIONS[J]
so no element of PORTIONS is greater than its respective PROPORTION, and so:
Examples of use follow:
1000 STRAIGHTLINE 12
83 84 83 83 83 84 84 83 83 84 83 83
¯50 STRAIGHTLINE 3
¯16 ¯17 ¯17
1000 PERCENTAGE 10 15 13
264 394 342
¯125 PERCENTAGE 10 15 13
¯33 ¯50 ¯42
V←10000 PERCENTAGE 10 15 13 11
V
2040 3061 2654 2245
W←10000 PERCENTAGE 10 10 10 12 12 13 15 16 17 17 17 20
W
592 591 591 710 711 770 888 947 1006 1006 1005 1183
Z←V CROSS W
Z
120 121 120 144 145 157 182 193 205 205 206 242
181 180 181 218 218 235 271 290 309 309 308 361
158 157 157 189 188 204 235 252 267 267 265 315
133 133 133 159 160 174 200 212 225 225 226 265
+/Z
2040 3061 2654 2245
V≡+/Z
1
W≡+⌿Z
1
W CROSS V
121 182 157 132
121 180 157 133
120 181 157 133
144 218 188 160
146 218 188 159
158 236 204 172
181 272 235 200
193 289 252 213
205 308 268 225
205 307 267 227
205 308 266 226
241 362 315 265