EN VI

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

How to Javascript - 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:

Spread item indices by size
Make equal chunks of indices of the required group count
Compare edges of the chunks and cut smaller index count on edges of siblings chunks
Process equal size indices if found
Map the chunks into the final groups

I didn't test it with the equal edges, you could prepare a test data.

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

function distributeItems(items, groupNum) {
    const spread = items.reduce((r, item, i) => (r.push(...Array.from({ length: item.size }, () => i)), r), []);
    const chunks = [];
    let count = -1;
    const size = spread.length / groupNum | 0;
    while (++count < groupNum) chunks.push(spread.slice(size * count, count === groupNum - 1 ? undefined : size * (count + 1)));
    const equalEdges = [];

    for (let i = 1; i < chunks.length; i++) {
        const chunk = chunks[i - 1], edge = chunk.at(-1);
        const next = chunks[i], nextEdge = next[0];
        if (edge !== nextEdge) { // definite cut
            continue;
        }
        let size = 1;
        for (let j = chunk.length - 2; j >= 0; j--) {
            if (chunk[j] === edge) size++;
        }
        let nextSize = 1;
        for (let j = 1; j < next.length; j++) {
            if (next[j] === nextEdge) nextSize++;
        }
        if (size > nextSize) {
            next.splice(0, nextSize);
        } else if (size < nextSize) {
            chunk.splice(chunk.length - size, size);
        } else { // cut from bigger chunk, but that's known after all unequal edges are processed
            equalEdges.push([chunk, next, size]);
        }
    }

    // we have some equal edges, cut from a bigger chunk (not tested)
    do {
        count = equalEdges.length;
        for (let i = 0; i < equalEdges.length; i++) {
            const [chunk, next, size] = equalEdges[i];
            if (chunk.length > next.length) {
                chunk.splice(chunk.length - size, size);
                equalEdges.splice(i--, 1);
            } else if (chunk.length < next.length) {
                next.splice(0, size);
                equalEdges.splice(i--, 1);
            }
        }

    } while (count !== equalEdges.length);

    for (const [chunk, next, size] of equalEdges) {
        if (Math.random() * 2 | 0 === 0) {
            chunk.splice(chunk.length - size, size);
        } else {
            next.splice(0, size);
        }
    }

    return chunks.map(chunk => {
        let idx = chunk[0];
        const group = [items[idx]];
        for (let i = 1; i < chunk.length; i++) {
            const next = chunk[i];
            if (next !== idx) group.push(items[next]);
            idx = next;
        }
        return group;
    });
}