How to divide an integer into an array of roughly equal and evenly distributed parts that sum to the-CodePudding

Given an integer n, what is an algorithm that can divide it into an array of d parts, which has the properties that its members sum to the original integer n, are roughly equal in size, and are reasonably evenly distributed throughout the array? e.g. dividing 13 into 10 parts looks something like:

[1, 1, 2, 1, 1, 2, 1, 1, 2, 1]

CodePudding user response：

One way is to use a dynamic ratio (a/b) in relation to the ratio of the large values to small values (c/r) in order to decide the distribution of the remainder after division:

function split(n, d)
{
  if(d === 0)
    return [];

  // Integer division spelled in JavaScript
  const q = Math.floor(n / d);
  const r = n % d;
  const c = d - r;
  
  let out = Array(d);
  let a = 1;
  let b = 1;
  
  for(let i = 0; i < d; i  )
  {
    // Make the ratio a/b tend towards c/r
    if((a * r) < (b * c))
    {
      a  ;
      out[i] = q;
    }
    else
    {
      b  ;
      out[i] = q   1;
    }
  }
  
  // Check the array sums to n
  console.log(out, n === out.reduce((a, b) => a   b, 0));

  return out;
}

split(11, 10);
split(173, 9);
split(13, 10);
split(1773, 19);

This produces the output:

[1, 1, 1, 1, 1, 1, 1, 1, 2, 1], true
[19, 19, 19, 20, 19, 19, 19, 20, 19], true
[1, 1, 2, 1, 1, 2, 1, 1, 2, 1], true
[93, 93, 94, 93, 93, 94, 93, 93, 94, 93, 93, 94, 93, 93, 94, 93, 93, 94, 93], true