A property website colours a map by price band. The designer wants k bands whose prices are as tight as possible: sort all the prices, cut the sorted list into k non-empty consecutive pieces, and measure each piece by its sum of squared deviations from its own mean. The best cut is the one whose total over the k pieces is smallest.
Write natural_breaks(prices, k) that returns that smallest possible total, as a float.
Cutting at the biggest gaps between neighbouring prices is not always best, and with hundreds of prices there are far too many possible cuts to try them all.
The setup provides house_prices(n, seed), which returns n random prices (thousands of pounds) that come from a few neighbourhoods.
Examples
Input: prices = [2, 3, 10, 11, 12, 30], k = 3
Output: 2.5
Explanation: bands [2, 3], [10, 11, 12], [30] have sums of squared deviations
0.5, 2.0 and 0.0.
Input: prices = [2, 3, 10, 11, 12, 30], k = 2
Output: 89.2
Explanation: [2, 3, 10, 11, 12] and [30]: the first band has mean 7.6 and
31.36 + 21.16 + 5.76 + 11.56 + 19.36 = 89.2. The cut [2, 3] | [10, 11, 12, 30] gives 273.25.
Input: prices = [2, 3, 10, 11, 12, 30], k = 1
Output: 507.3333333333333
Constraints
1 <= k <= len(prices) <= 400, andk <= 8- every price is a whole number with
1 <= price <= 10**5 - floats are compared with a tolerance of
1e-6(relative)
Goals
- Measure how tight a group of values is by its sum of squared deviations
- Get any group's sum of squared deviations in O(1) from running sums of x and x²
- Search all ways of cutting sorted data into k bands without trying them one by one