[FIXED] How to allocate list of product quantities connected with list of prices to list of customer orders

Issue

I have an allocation problem - I have a supply of product at different prices that I need to sell to people at first come first served principle, starting with the cheapest price.

I have 4 different lists/numpy arrays:

people = ['mark', 'greg', 'paul']       #This list is not needed, just for easier understanding
orders = np.array([21, 6, 3], dtype=np.int64)
quantity = np.array([16, 14], dtype=np.int64)
price = np.array([30.5, 35.5], dtype=np.double)

Sum of orders always equals sum of quantities. Lists people and orders are 'connected' and sorted based on descending orders: Mark wants to buy quantity of 21, Greg wants to buy 6 and Paul wants to buy 3. Lists quantity and price are also 'connected' and sorted based on price ascending: There is a supply of 16 at price $30.5 and supply of 14 at price $35.5.

What's the best way to calculate the average price for each buyer?

A naive solution that works would be:

import numpy as np

orders = np.array([21, 6, 3], dtype=np.int64)
quantity = np.array([16, 14], dtype=np.int64)
price = np.array([30.5, 35.5], dtype=np.double)

start = 0
supply = np.zeros((np.sum(quantity)), dtype=np.double)
for i, quant in enumerate(quantity):
    idx = start + quant
    supply[start:idx] = price[i]
    start = idx

print(supply)
# [30.5 30.5 30.5 30.5 30.5 30.5 30.5 30.5 30.5 30.5 30.5 30.5 30.5 30.5
# 30.5 30.5 35.5 35.5 35.5 35.5 35.5 35.5 35.5 35.5 35.5 35.5 35.5 35.5
# 35.5 35.5]

fin = []
start = 0
for order in orders:
    idx = start + order
    fin.append(np.mean(supply[start:idx]))
    start = idx

print(fin)
# [31.69047619047619, 35.5, 35.5]

but this is terrible, as the supply array could get extremely big. I know there must be a good way to do it with numpy functions/indexing but I can't figure out how to do it. What's the best way to do this? If anyone got any tips on how to handle floating point precision problems, that would be appreciated as well. (How to always make the: mean_prices * quantity == original_prices * quantities)

Solution

You can expand your prices with repeat, and sum per chunk using add.reduceat, then get the mean by dividing by the number of items:

out = np.add.reduceat(np.repeat(price, quantity),
                      np.r_[0, np.cumsum(orders)][:-1]
                     ) / orders

Output:

array([31.69047619, 35.5       , 35.5       ])

Answered By - mozway