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?

Efficiently finding the closest value - easy. Doing so such that each number gets used at most once - a bit more difficult. — Bernhard Barker
What's the problem with [1000, 500, 200]? The sum of differences is the same as for [200, 500, 1000] so I don't see how it's suboptimal. Please define a measure you want to optimize — Niklas B.
what if we sort the input in descending and follow your process. like [3000,2000,1000] - and obvious your have start compare from last in your base to get faster. — Mani
@NiklasB. The problem is that the numbers define ranges and I'm getting negative ranges with the backwards list. — John NoCookies
Ok so you want non-decreasing order. What measure do you want to minimize? — Niklas B.

Peter de Rivaz Peter de Rivaz · Accepted Answer · 2014-02-14T15:05:17

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.

Algorithm for scaling one list of ranges to another

1 Answers

Approach 1

Approach 2