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);

CodePudding user response：

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;
}

CodePudding user response：

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}`)
}