4

The Problem

Suppose we are given a variable-length list of objects containing a fixed-length list of positive decimal numbers as attributes.

JSON Example

[
    {a: 0.1, b: 0.6, c: 0.0},
    {a: 1.0, b: 1.3, c: 0.2},
    {a: 1.2, b: 0.1, c: 0.3},
    {a: 0.2, b: 0.2, c: 0.5},
    {a: 0.8, b: 0.2, c: 0.6}
]

Create an quantity distribution to multiply each of the objects' attributes by to make the sum product of all objects multiplied by the distribution equals 1. I want to use as few objects as possible to create the total, rather than using small amounts of every object.

If the distribution was [1, 1, 1, 1, 1], the result would be {a: 3.3, b: 2.4, c: 1.6} because we would simply add up each of the attributes as they are all multiplied by 1.

A Solution

A perfect distribution in this case would be [0, 0.5, 0, 1.5, 0.25] yielding {a: 1, b: 1, c: 1}.

Creating an Algorithm

I want to create an algorithm that solves this number for much larger data sets with more attributes.

First Attempt

My first attempt was to start with an arbitrary value and add enough to bring just one attribute to 1. Then find the closest match for the missing attributes. At this point I would subtract from quantities to allow for the new quantity to be added without going over 1 in any category. Picking the right quantities to lower was difficult.

Second Attempt (removing the limit)

I then thought of removing the limit of 1 and making the algorithm stop once all sum products were relatively equal. That way increasing quantity of one decreases the relative quantity of all others. This will hopefully weed out bad values by making them have little significance on the final result. I would probably need a cutoff value to make sure I don't end up with a little of everything.

In our example, I found the distribution [0, 2, 0, 6, 1] resulted in {a: 4, b: 4, c: 4}. By dividing the distribution by 4, I got a perfect distribution of [0, 0.5, 0, 1.5, 0.25].

Other Solutions & Improvements

I'm looking for suggestions for improvement, concerns, or alternative solutions to this problem. Are there any related problems so that I can do more research on potential solutions?

  • 2
    In cases where a perfect distribution is not possible, is it preferable to have the sums closer to 1 or to use fewer objects? Also, how close to perfect is "close enough"? – Nathan Gerhart Jan 14 '16 at 2:50
  • By (quoting) "I want to use as few objects as possible to create the total, rather than using small amounts of every object", do you mean that you want to maximize the number of coefficients equal to zero for an ideal distribution? – YSharp Sep 1 '16 at 0:45
1

(Algorithm hint)

The example you posted seems equivalent to solving the following linear system, with 2 free variables in the solutions, say, by using Gaussian Elimination:

0.1 v + 1.0 w + 1.2 x + 0.2 y + 0.8 z = 1.0 (for vector "a")
0.6 v + 1.3 w + 0.1 x + 0.2 y + 0.2 z = 1.0 (for vector "b")
0.0 v + 0.2 w + 0.3 x + 0.5 y + 0.6 z = 1.0 (for vector "c")

There will be 2 free variables and 3 fixed for an infinity of solutions in general, because it is a case of an underspecified system of 5 unknowns appearing in 3 equations only.

There are answers on Math Overflow for a similar system where n (number of unknowns) is greater than m (the number of equations).

Also relevant: Transformation to Row Echelon Form

'HTH,

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.