CODEWITHSUNDEEP
algorithmsortinggrouping
Richard Hulse
Richard Hulse

Reputation: 10493

How do I calculate optimal grouping of objects?

I need to be able to allocate a set of objects of known size into 3 groups. For example, given an ordered list like the following, I want to find two division or separation points to make three groups with similar sums.

75, 67, 54, 40, 51, 48, 49, 47

The sum of each group must be roughly equal, and sums of groups 2 and 3 cannot exceed that of the first group by more than a defined amount (say 10). Ideally the first group is slightly larger than the others. The order of items cannot be changed. Each group is formed from consecutive elements of the original list. Each element is placed in one group.

The expected solution in this case would be:

Groups: [75, 67], [54, 40, 51], [48, 49, 47]

Sums: 142, 145, 144

The use-case is pre-calculating (server-side) the allocation of prioritised stories into columns, based on their known height in the front-end layout. I already have code that gives me close-enough heights for the content (proportionally speaking), but I'm struggling with an efficient way to do the grouping. There are good reasons why this is not being done on the front end, but presumably a general solution could be used there too.

Upvotes: 0

Views: 1156

Answers (1)

Zim-Zam O'Pootertoot
Zim-Zam O'Pootertoot

Reputation: 18148

Given that you know approximately how much you want allocated to each group (total / 3), why not just iterate through the list and allocate objects to group 1 until its total reaches (total / 3), then do the same for group 2, then the remainder goes to group 3. The end result might not fit your parameters e.g. group 2 might exceed group 1 by more than epsilon, in which case you swap one or two elements from group 3 to group 2 if need be, and then if need be swap one or two elements from group 2 to group 1. The whole thing should run in O(n) with the expectation that you'll need to swap fewer than a dozen elements at the end.

Upvotes: 1

Related Questions