CODEWITHSUNDEEP
algorithmcomplexity-theorycomputation-theory
Gordak
Gordak

Reputation: 2070

Algorithm: separate a list of values into subsets by minimizing the maximal difference in the sums of elements between all sublists

I have a list of values (integers) that I would like to split into B non-empty sublists without changing their initial order. The goal is to adjust the size of text to fit it into a defined area.

Each sublist will have one metric associated to it : the sum of its values. I would like to minimise the difference DIFF between the biggest sum and smallest sum among all the sublists. This would allow me to divide text into lines with approximately the same amount of text.

EDIT

As suggested, it would also work to minimise the maximal sum, as that would result in minimising the maximal length of a line of text.

Examples:

Given the list L = {2,3,4,5,6} and B = 2.

Solution : L1 = {2,3,4} and L2 = {5,6}. Sum(L1) = 9, Sum(L2) = 11 and DIFF = 2

Given the List L = {1,1,8,1,1,1,8,1} and B = 3

Solution : L1 = {1,1,8}, L2 = {1,1,1} and L3 = {8,1}.Sum(L1) = 10, Sum(L2) = 3, Sum(L3) = 9 and DIFF = 7

My suggestion

As I don't have an IT background, I'm not sure how to approach this. First, I tried to figure out the number of combinations I could split my original set into B sublists. The number of elements in the original list is N, then there would be a number of possible splits equal to:

equation

Then I tried to see what would be an appropriate algorithm to find the global minimum. I thought that if I ran into a situation where both of the conditions below are respected, I would have hit the global minimum.

(As the sublists must not be empty, moving an element from a sublist with only one element requires to change several sublists)

Questions

Are the two conditions mentioned sufficient to guarantee a global minimum (for DIFF) ?

Do you know / remember an algorithm solving this problem ? Or do you have a suggestion to solve this ?

Do you have any reading recommendations to help me to tackle this kind of problem ?

As I said, I don't have an It background and don't have much experience with such computer theory problems.

Thank you !

Upvotes: 2

Views: 308

Answers (1)

RBarryYoung
RBarryYoung

Reputation: 56725

Q: Are the two conditions mentioned sufficient to guarantee a global minimum (for DIFF) ?

A: NO

consider the following list: {6,5,2,4,3,7} with B=3

and the following potential solution:

{6} {5,2,4} {3,7};  Sums=(6,11,10),  DIFF = 11-6 = 5

All one-element changes from the largest group make DIFF worse, or leave it the same:

{6,5} {2,4} {3,7};  Sums=(6,11,10),  DIFF = 11-6 = 5
{6} {5,2} {4,3,7};  Sums=(6,7,14),  DIFF = 14-6 = 8
{6} {5,2,4,3} {7};  Sums=(6,14,7),  DIFF = 14-6 = 8

But there is a better solution:

{6,5} {2,4,3} {7};  Sums=(11,9,7),  DIFF = 11-7 = 5

So your method only finds local minima, not global ones.

Upvotes: 2

Related Questions