Algorithm to distribute variably-sized items into balanced groups preserving items order

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:

Item A - size 5
Item B - size 1
Item C - size 8
Item D - size 2
Item E - size 3

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

Solution

The algo is the following:

Calculate total size of all items
Get size of a group
Iterate items and push to groups according to the current sum of item sizes

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