Chunk a Parent Order

A parent order gets sliced across time buckets in proportion to the volume expected in each. The slices are lots, so they have to be whole numbers, and they have to add up to the parent exactly. Rounding each slice on its own fails both ways: round down and you under-fill the order, round to nearest and you can overshoot it.

This is the apportionment problem, and it has a standard answer.

Implement chunk_order(total, weights).

• total is a non-negative integer, the parent quantity.
• weights is a list of non-negative integers, the expected volume per bucket.

Bucket \( i \) is entitled to \( total \times w_i / W \) lots, where \( W \) is the sum of the weights. Allocate by largest remainder:

1. give every bucket the floor of its entitlement;
2. distribute the leftover lots one at a time to the buckets with the largest fractional part of their entitlement;
3. if two buckets tie on that fractional part, the earlier bucket wins.

Return the list of integer slices, in bucket order.

The returned list must sum to total exactly. That is the property being tested, and it is what makes the naive per-bucket rounding wrong.

Examples

chunk_order(100, [1, 1, 1])
# [34, 33, 33]

chunk_order(10, [1, 1, 1, 1])
# [3, 3, 2, 2]

In the first, each bucket is entitled to \( 33\tfrac{1}{3} \) lots. All three floor to 33, leaving one lot over, and all three tie on the remainder, so the earliest takes it.

Constraints

• 0 <= total <= 10^9 and 0 <= len(weights) <= 2 * 10^5.
• Compare fractional parts exactly, using the remainder of the integer division \( (total \times w_i) \bmod W \), never a float. With weights this large the floats collide and the tie-break becomes arbitrary.
• If every weight is 0, or the weight list is empty, there is nothing to apportion: return all zeros, or an empty list, rather than dividing by zero.
• A bucket with weight 0 always gets 0 lots.