Finding the optimal division of an array

I'm trying to write a function in Apps Script to take a large array of values that I'd like to split as evenly as possible into subarrays of values (a array of arrays). Each subarray would optimally be 15 values long. The maximum number of values in each array would be 20 and the minimum number of values would be 10.

If the value of the array were 21, you'd have an array of 10 and an array of 11. 22 would be two arrays of 11. And so on until you got to 36 (18, 18). At 37 you'd break out into (13, 13, 14). 38 would be (13, 14, 14)

My initial thought was to take the starting number and find the closest multiple of 15. So, if the number is 47, then 45 is the closest multiple. If the closest multiple is less than the starting number, use the factor of that multiple, then calculate the difference between the starting number and the multiple. Distribute that number one per array until the difference sum is reached. So 45 is a factor of 3. That means 3 arrays of 15, and then the difference between 47 and 45 is 2. So add one to the first array and one to the second to get 16, 16, 15.

If the closer multiple is higher than the starting number, use the factor of the higher multiple, then calculate the difference between the starting number and the higher multiple, subtract one from each subarray until that difference is exhausted. So for 43, the higher multiple is a 45 (15, 15, 15) The difference between the higher number is 2, so subtract 1 from the first two arrays and get (14, 14, 15).

So far I have this, which will tell me how many values each array should have. But it fails on numbers 21 and 22. I need something that will take the number of values in each array, X or Y, and populate X or Y values into that array. The final output being an array of arrays that, when read left to right, would maintain the same order as the original array, albeit subdivided into arrays.

function splitList(values) {
  const total = values.length;
  const optimalSize = 15;
  const minSize = 10;
  const maxSize = 20;

  if (total <= maxSize) {
    return [values];
  }

  let numSublists = Math.round(total / optimalSize);
  let sublistSize = Math.floor(total / numSublists);
  let remainder = total % numSublists;

  let result = [];
  let startIndex = 0;

  for (let i = 0; i < numSublists; i++) {
    let currentSize = sublistSize + (remainder > 0 ? 1 : 0);
    result.push(values.slice(startIndex, startIndex + currentSize));
    startIndex += currentSize;
    remainder--;
  }

  return result;
}

// Example usage:
const values = Array.from({
  length: 43
}, (_, i) => i + 1);
const sublists = splitList(values);
console.log(sublists);

Solution

The main problem in your algorithm arises for a low number of sublists, when there aren't enough of them to allocate the (total % optimalSize) values without exceeding your maximum size constraint.

Adding the following code before the for loop should solve the issue:

// If the sublists exceed the maximum allowed size,
while (sublistSize > maxSize) {
  // use one more sublist.
  numSublists++;
  // Recompute the variables.
  sublistSize = Math.floor(total / numSublists);
  remainder = total % numSublists;
}

However, I don't believe your approach is optimal. Indeed, rounding the total / optimalSize does not optimise the sublists' size. For example, running your algorithm for an initial array of length 37 will subdivide it into two subarrays of lengths 19 and 18, instead of three subarrays of lengths 12, 12, 13.

I would suggest replacing this:

let numSublists = Math.round(total / optimalSize);
let sublistSize = Math.floor(total / numSublists);
let remainder = total % numSublists;

; with this:

let numSublists = Math.floor(total / optimalSize);
if ((total % optimalSize) / numSublists > (optimalSize - (total % optimalSize)) / (numSublists+1)) {
  numSublists++;
}
let sublistSize = Math.floor(total / numSublists);
let remainder = total % numSublists;

That added if statement decides whether to use either numSublists = Math.floor(total / optimalSize) or numSublists = Math.ceil(total / optimalSize) by comparing in both situations the average overage/shortcoming in the sublists' size with respect to the optimal size.

If you do that, you'll find you don't need the while loop I mentioned earlier.

I'm not entirely confident of my answer - I haven't tried to prove it - but I believe it should work. And I'm sure there are better and more elegant ways to do this, but for that we'll have to wait for other answers :p