Find fractions with common denominator for parcel areas , sum has to stay the same

Question

Lets say i have a parcel (a piece of land) that is 8027 square meters and i have more than one owner, but they don't own same amount of land.

Owner A has: 1003.5m2 Owner B has: 1003.5m2 Owner C has 1337m2 Owner D has 1338m2 Owner E has 1338m2 Owner F has 2007m2

As output i want to get whole numbers fraction with lowest possible common denominator, etc

1/8 1/8 .. .. ..

i know it is very unlikely it will be this small...

but when you divide fractions difference shouldn't exceed more than +/- 1m2 per owner

meaning if owner A has 1003.5m2 in beginning, and i got 1/8 8027/8=1003.35 that is OK, BUT, unfortunately big BUT! total SUM of all owners has to stay the same at the end :(

For now i was able to get lowest common denominator for owners individually and i'm not even sure what is next step in getting wanted result...

Any help is much appreciated!

gcd = function (a, b) {
    if (b < 0.0000001)
        return a;                         // Since there is a limited precision we need to limit the value.
    return gcd(b, Math.floor(a % b));     // Discard any fractions due to limitations in precision.
};

var total_area = 8027;
var area_parts = [1003.5, 1003.5, 1337, 1338, 1338, 2007];

ResaultArr = Array();

for (let i = 0; i < area_parts.length; i++) {
    var decimal_fraction = area_parts[i] / total_area;
    var denominator = Math.pow(10, 4);    
    var numerator = decimal_fraction * denominator;
    var divisor = gcd(numerator, denominator);

    numerator /= divisor;
    denominator /= divisor;

    var fraction = Math.floor(numerator) + '/' + Math.floor(denominator);
    var decimal_fraction_after = Math.floor(numerator) / Math.floor(denominator);
    var area_difference = area_parts[i] - (total_area * decimal_fraction_after);
    var area_part_after = total_area * decimal_fraction_after;

    ResaultArr[i] = {
        area_difference: area_difference,
        fraction: fraction,
        decimal_fraction: decimal_fraction,
        decimal_fraction_after: decimal_fraction_after,
        area_part: area_parts[i],
        area_part_after: area_part_after,
        total_area: total_area
    };
}

console.log(ResaultArr);

Answer 1

A brute-force approach simply tries successive denominators until it finds one that works:

const makeFractions = (xs, tolerance = 1, n = xs .length) => {
  const total = xs .reduce ((a, b) => a + b, 0)
  const numerators = xs .map (x => Math .round (x * n / total))
  const denom = numerators .reduce ((a, b) => a + b, 0)
  const candidates = numerators .map (y => y * total / denom)
  return candidates .some ((y, i) => Math .abs (y - xs [i]) > tolerance) 
    ? makeFractions (xs, tolerance, n + 1) 
    : numerators .map (y => `${y}/${denom}`)
}


const parts = [1003.5, 1003.5, 1337, 1338, 1338, 2007], total = 8027

const results = makeFractions (parts)

console .log ('parts: ', parts)
console .log ('fractions:', results)
console .log ('exact values: ', results .map (
  s => s .split('/').map (Number)) .map (([n, d]) => n * total / d
))

.as-console-wrapper {max-height: 100% !important; top: 0}

Here we start with n of 6, the length of the array, and then round the values by how many 6ths of the total they approximate, getting potential numerators of [1, 1, 1, 1, 1, 2], which totals to give us a denominator of 7, and a candidate breakdown of [1146.7142857142858, 1146.7142857142858, 1146.7142857142858, 1146.7142857142858, 1146.7142857142858, 2293.4285714285716]. At least one of these is too far from our target numbers -- in fact, all of them are, in this case -- so we try again with 7 for n. We get the same breakdown, and again the same breakdown for 8. When we hit 9, we get a denominator of 9 and candidates of [891.8888888888889, 891.8888888888889, 891.8888888888889, 1783.7777777777778, 1783.7777777777778, 1783.7777777777778]}. These are still too far, and we keep trying. Eventually, we hit n of 22, which gives us potential numerators of [3, 3, 4, 4, 4, 6]], and hence a denominator of 24 with candidate values of [1003.375, 1003.375, 1337.8333333333333, 1337.8333333333333, 1337.8333333333333, 2006.75]. Each of these is within our 1 tolerance of the target numbers and we stop here, returning the fractions [3/24, 3/24, 4/24, 4/24, 4/24, 6/24].

---

It probably makes sense to extract a sum function and to store the calculated total which won't change per recursive invocation, so this is perhaps a bit cleaner:

const sum = (ns) => ns .reduce ((a, b) => a + b, 0)

const makeFractions = (xs, tolerance = 1, total = sum (xs), n = xs .length) => {
  const numerators = xs .map (x => Math .round (x * n / total))
  const denom = sum (numerators)
  const candidates = numerators .map (y => y * total / denom)
  return candidates .some ((y, i) => Math .abs (y - xs [i]) > tolerance) 
    ? makeFractions (xs, tolerance, total,  n + 1) 
    : numerators .map (y => `${y}/${denom}`)
}

Update

A comment asked how to avoid stack overflow with this technique with a tolerance of zero. We can easily convert this recursion to a while loop, as follows:

const makeFractions = (xs, tolerance = 1) => {
  const total = xs .reduce ((a, b) => a + b, 0)
  let n = xs .length, numerators, denom, candidates
  
  do {
    n += 1
    numerators = xs .map (x => Math .round (x * n / total))
    denom = numerators .reduce ((a, b) => a + b, 0)
    candidates = numerators .map (y => y * total / denom)
  } while (candidates .some ((y, i) => Math .abs (y - xs [i]) > tolerance)) 

    return numerators .map (y => `${y}/${denom}`)
}

But now we seem to be asking a different question that is probably better answered with other techniques.

Although the sample is still answered quickly, that's because the numbers are quite amenable to it. With more random numbers, that could take quite a while.

Answer 2

In your example the proportions are approximately 1/8,1/8,1/6,1/6,1/6 and 1/4, we can give these a common denominator of 24, so the fractions become 3/24, 3/24, 4/24, 4/24 and 6/24 giving areas 1003.375, 1003.375,1337.833333,1337.833333,1337.833333, 2006.75 that sum exactly to 8027.

This gives us a hit as to how to define the problem better. Find the set of fraction a/n, b/n, c/n, d/n, e/n, f/n such that their sum is 1 and that the product 8027 * a/n are within your desired error bounds. e.g. | 8027*a/n - 1003.5 | < bound, etc. Find the smallest n satisfying this property.

A simple-minded approach is to work iteratively on n.

for(n=1;n<limit;++n) {
    a = round(n * 1003.5 / 8027);
    b = round(n * 1003.5 / 8027);
    c = round(n * 1337 / 8027);
    d = round(n * 1338 / 8027);
    e = round(n * 1338 / 8027);
    f = round(n * 2007 / 8027);
    errA = abs(8027*a/n - 1003.5);
    ....
    if(a+b+c+d+e+f==n && errA < bound && ... ) break;
}