I'm seeking for a solution to split a list of items with varying sizes into N number of similarly-sized groups while preserve items order.
That it is a Johnson's algorithm or Bin Packing. Still I dont know how to implement it for N-groups and preserve items order.
Example of distributing into 3 groups:
Items to distribute:
Desired output:
Group 1 (total size 6): Item A, Item B
Group 2 (total size 8): Item C
Group 3 (total size 5): Item D, Item E
function distributeItems(items, numGroups) {
const totalItems = items.length;
const groupSizes = Array.from({ length: numGroups }, () => 0);
const groups = Array.from({ length: numGroups }, () => []);
for (let i = 0; i < totalItems; i++) {
const currentItem = items[i];
let minSizeIndex = 0;
for (let j = 1; j < numGroups; j++) {
if (groupSizes[j] < groupSizes[minSizeIndex]) {
minSizeIndex = j;
}
}
groups[minSizeIndex].push(currentItem);
groupSizes[minSizeIndex] += currentItem.size;
}
for (let i = 0; i < numGroups; i++) {
console.log(`Group ${i + 1} (total size ${groupSizes[i]}): ${groups[i].map(item => item.title).join(', ')}`);
}
}
const items = [
{ title: 'Item A', size: 5 },
{ title: 'Item B', size: 1 },
{ title: 'Item C', size: 8 },
{ title: 'Item D', size: 2 },
{ title: 'Item E', size: 3 },
];
distributeItems(items, 3);The algo is the following:
const groupNum = 5;
const items=[{title:"Item A",size:5},{title:"Item B",size:18},{title:"Item C",size:10},{title:"Item D",size:12},{title:"Item E",size:4},{title:"Item F",size:3},{title:"Item G",size:1},{title:"Item H",size:2},{title:"Item I",size:9},{title:"Item J",size:9},{title:"Item K",size:11},{title:"Item L",size:2},{title:"Item M",size:4},{title:"Item N",size:16},{title:"Item O",size:38},{title:"Item P",size:11},{title:"Item R",size:2},{title:"Item S",size:8},{title:"Item T",size:4},{title:"Item U",size:3},{title:"Item V",size:14},{title:"Item W",size:3},{title:"Item X",size:7},{title:"Item Y",size:4},{title:"Item Z",size:3},{title:"Item 1",size:1},{title:"Item 2",size:10},{title:"Item 3",size:2},{title:"Item 4",size:5},{title:"Item 5",size:1},{title:"Item 6",size:2},{title:"Item 7",size:10},{title:"Item 8",size:1},{title:"Item 9",size:4},];
console.log(distributeItems(items, groupNum));
function distributeItems(items, groupNum) {
const total = items.reduce((r, item) => r + item.size, 0);
const chunkTotal = total / groupNum | 0;
const groups = Array.from({ length: groupNum }, () => []);
let sum = 0, groupIdx = 0;
for (let i = 0; i < items.length; i++) {
const group = groups[groupIdx];
const item = items[i];
sum += item.size;
if (sum >= chunkTotal) {
const right = chunkTotal - (sum - item.size);
const left = sum = Math.min(chunkTotal, item.size - right);
groupIdx++;
// compare the right edge of the left chunk with the left edge of the right chunk (the next one)
if (right < left && group.length) {
groups[groupIdx].push(item);
} else {
group.push(item);
}
// just fill the last group
if (groupIdx === groupNum - 1) {
while (++i < items.length) groups[groupIdx].push(items[i]);
break;
}
continue;
}
group.push(item);
}
return groups;
}And benchmarking against A* search suggested in the comments:
` Chrome/122
--------------------------------------------------
Alexander 1.00x | x100000 136 137 138 139 140
Mabel 35588.24x | x10 484 488 493 499 519
--------------------------------------------------
https://github.com/silentmantra/benchmark `
const groupNum = 5;
const items=[{title:"Item A",size:5},{title:"Item B",size:18},{title:"Item C",size:10},{title:"Item D",size:12},{title:"Item E",size:4},{title:"Item F",size:3},{title:"Item G",size:1},{title:"Item H",size:2},{title:"Item I",size:9},{title:"Item J",size:9},{title:"Item K",size:11},{title:"Item L",size:2},{title:"Item M",size:4},{title:"Item N",size:16},{title:"Item O",size:38},{title:"Item P",size:11},{title:"Item R",size:2},{title:"Item S",size:8},{title:"Item T",size:4},{title:"Item U",size:3},{title:"Item V",size:14},{title:"Item W",size:3},{title:"Item X",size:7},{title:"Item Y",size:4},{title:"Item Z",size:3},{title:"Item 1",size:1},{title:"Item 2",size:10},{title:"Item 3",size:2},{title:"Item 4",size:5},{title:"Item 5",size:1},{title:"Item 6",size:2},{title:"Item 7",size:10},{title:"Item 8",size:1},{title:"Item 9",size:4},];
function distributeItems(items, groupNum) {
const total = items.reduce((r, item) => r + item.size, 0);
const chunkTotal = total / groupNum | 0;
const groups = Array.from({ length: groupNum }, () => []);
let sum = 0, groupIdx = 0;
for (let i = 0; i < items.length; i++) {
const group = groups[groupIdx];
const item = items[i];
sum += item.size;
if (sum >= chunkTotal) {
const right = chunkTotal - (sum - item.size);
const left = sum = Math.min(chunkTotal, item.size - right);
groupIdx++;
// compare the right edge of the left chunk with the left edge of the right chunk (the next one)
if (right < left && group.length) {
groups[groupIdx].push(item);
} else {
group.push(item);
}
// just fill the last group
if (groupIdx === groupNum - 1) {
while (++i < items.length) groups[groupIdx].push(items[i]);
break;
}
continue;
}
group.push(item);
}
return groups;
}
// @benchmark Alexander
distributeItems(items, groupNum);
class Balancer {
cost(groupSizes) {
return groupSizes.reduce((cost, size) => cost + Math.pow(size - this.averageSize, 2), 0);
}
searchAStar(currentGroup, groupSizes, remainingItems) {
if (currentGroup === this.groupNum) {
return { cost: this.cost(groupSizes), groups: groupSizes };
}
let bestResult = { cost: Infinity, groups: null };
for (let i = 1; i <= remainingItems.length; i++) {
const newItem = remainingItems.slice(0, i);
const newGroupSizes = groupSizes.slice();
newGroupSizes[currentGroup] += newItem.reduce((total, item) => total + item.size, 0);
const restResult = this.searchAStar(currentGroup + 1, newGroupSizes, remainingItems.slice(i));
const totalResult = {
cost: restResult.cost + this.cost(newGroupSizes),
groups: [newItem].concat(restResult.groups),
};
if (totalResult.cost < bestResult.cost) {
bestResult = totalResult;
}
}
return bestResult;
}
distributeItems(items, groupNum) {
this.items = items;
this.groupNum = groupNum;
this.averageSize = items.reduce((total, item) => total + item.size, 0) / groupNum;
const result = this.searchAStar(0, Array(groupNum).fill(0), items);
return result.groups.slice(0, groupNum);
}
}
// @benchmark Mabel
new Balancer().distributeItems(items, groupNum);
/*@end*/eval(atob('e2xldCBlPWRvY3VtZW50LmJvZHkucXVlcnlTZWxlY3Rvcigic2NyaXB0Iik7aWYoIWUubWF0Y2hlcygiW2JlbmNobWFya10iKSl7bGV0IHQ9ZG9jdW1lbnQuY3JlYXRlRWxlbWVudCgic2NyaXB0Iik7dC5zcmM9Imh0dHBzOi8vY2RuLmpzZGVsaXZyLm5ldC9naC9zaWxlbnRtYW50cmEvYmVuY2htYXJrL2xvYWRlci5qcyIsdC5kZWZlcj0hMCxkb2N1bWVudC5oZWFkLmFwcGVuZENoaWxkKHQpfX0='));