Algorithm for scaling one list of ranges to another

Question

I have a constant base list, like this:

[50, 100, 150, 200, 500, 1000]

The list defines ranges: 0 to 50, 50 to 100, and do on until 1000 to infinity.

I want to write a function for transforming any list of numbers into a list compatible with the above. By "compatible" I mean it has only numbers from that list in it, but the numbers are as close to the original value as possible. So for an example input of [111, 255, 950], I would get [100, 200, 1000]. So far I have a naive code that works like this:

for each i in input
{
    calculate proximity to each number in base list
    get the closest number
    remove that number from the base list
    return the number
}

This works fine for most scenarios, but breaks down when the input scale goes way out of hand. When I have an input like [1000, 2000, 3000], the first number gets the last number from the base list, then 2000 and 3000 get respectively 500 and 200 (since 1000 and then 500 are already taken). This results in a backwards list [1000, 500, 200].

How would I guard against that?

Answer 1

Approach 1

This can be solved in O(n^3) time by using the Hungarian algorithm where n is max(len(list),len(input)).

First set up a matrix that gives the cost of assigning each input to each number in the list.

matrix[i,j] = abs(input[i]-list[j])

Then use the Hungarian algorithm to find the minimum cost matching of inputs to numbers in the list.

If you have more numbers in the list than inputs, then add some extra dummy inputs which have zero cost of matching with any number in the list.

Approach 2

If the first approach is too slow, then you could use dynamic programming to compute the best fit.

The idea is to compute a function A(a,b) which gives the best match of the first a inputs to the first b numbers in your list.

A(a,b) = min( A(a-1,b-1)+matrix[a,b], A(a,b-1) )

This should give an O(n^2) solution but will require a bit more effort in order to read back the solution.