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

2

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

New contributor

user27425627 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

1

Trang chủ Giới thiệu Sinh nhật bé trai Sinh nhật bé gái Tổ chức sự kiện Biểu diễn giải trí Dịch vụ khác Trang trí tiệc cưới Tổ chức khai trương Tư vấn dịch vụ Thư viện ảnh Tin tức - sự kiện Liên hệ Chú hề sinh nhật Trang trí YEAR END PARTY công ty Trang trí tất niên cuối năm Trang trí tất niên xu hướng mới nhất Trang trí sinh nhật bé trai Hải Đăng Trang trí sinh nhật bé Khánh Vân Trang trí sinh nhật Bích Ngân Trang trí sinh nhật bé Thanh Trang Thuê ông già Noel phát quà Biểu diễn xiếc khỉ Xiếc quay đĩa Dịch vụ tổ chức sự kiện 5 sao Thông tin về chúng tôi Dịch vụ sinh nhật bé trai Dịch vụ sinh nhật bé gái Sự kiện trọn gói Các tiết mục giải trí Dịch vụ bổ trợ Tiệc cưới sang trọng Dịch vụ khai trương Tư vấn tổ chức sự kiện Hình ảnh sự kiện Cập nhật tin tức Liên hệ ngay Thuê chú hề chuyên nghiệp Tiệc tất niên cho công ty Trang trí tiệc cuối năm Tiệc tất niên độc đáo Sinh nhật bé Hải Đăng Sinh nhật đáng yêu bé Khánh Vân Sinh nhật sang trọng Bích Ngân Tiệc sinh nhật bé Thanh Trang Dịch vụ ông già Noel Xiếc thú vui nhộn Biểu diễn xiếc quay đĩa Dịch vụ tổ chức tiệc uy tín Khám phá dịch vụ của chúng tôi Tiệc sinh nhật cho bé trai Trang trí tiệc cho bé gái Gói sự kiện chuyên nghiệp Chương trình giải trí hấp dẫn Dịch vụ hỗ trợ sự kiện Trang trí tiệc cưới đẹp Khởi đầu thành công với khai trương Chuyên gia tư vấn sự kiện Xem ảnh các sự kiện đẹp Tin mới về sự kiện Kết nối với đội ngũ chuyên gia Chú hề vui nhộn cho tiệc sinh nhật Ý tưởng tiệc cuối năm Tất niên độc đáo Trang trí tiệc hiện đại Tổ chức sinh nhật cho Hải Đăng Sinh nhật độc quyền Khánh Vân Phong cách tiệc Bích Ngân Trang trí tiệc bé Thanh Trang Thuê dịch vụ ông già Noel chuyên nghiệp Xem xiếc khỉ đặc sắc Xiếc quay đĩa thú vị
Trang chủ Giới thiệu Sinh nhật bé trai Sinh nhật bé gái Tổ chức sự kiện Biểu diễn giải trí Dịch vụ khác Trang trí tiệc cưới Tổ chức khai trương Tư vấn dịch vụ Thư viện ảnh Tin tức - sự kiện Liên hệ Chú hề sinh nhật Trang trí YEAR END PARTY công ty Trang trí tất niên cuối năm Trang trí tất niên xu hướng mới nhất Trang trí sinh nhật bé trai Hải Đăng Trang trí sinh nhật bé Khánh Vân Trang trí sinh nhật Bích Ngân Trang trí sinh nhật bé Thanh Trang Thuê ông già Noel phát quà Biểu diễn xiếc khỉ Xiếc quay đĩa
Thiết kế website Thiết kế website Thiết kế website Cách kháng tài khoản quảng cáo Mua bán Fanpage Facebook Dịch vụ SEO Tổ chức sinh nhật