# What's an efficient algorithm to calculate line breaks (word wrap) for balanced widths (minimum raggedness)?

This is a real-world application, not a student assignment.

• Suppose we have some numbered boxes which are to be laid out, in order, from left to right, top to bottom, with no space between them, into a column of fixed width and infinite height.
• The boxes have the same height, but variable width.
• When a box doesn't fit, it should wrap to the next line (just like text).
• After that, we fix the number of lines, and then lay out the boxes again so that the lines have a more balanced width, which means they try to be the same width, as much as possible.

The input is, simply:

double colWidth = …;
List<double> boxWidths = [ … ];


And the output could be:

List<int> result = [ … ]; // Number of boxes in each line.
double minWidth = …;


An example: Suppose the column has width = 11, and 5 boxes have widths [2, 3, 5, 2, 1], then the layout is this:

| ** *** ***** |
| ** *         |


This means we can fit the boxes into 2 lines, and line widths differ a lot. One is 10 and the other is only 3 (difference is 7).

Now we have to lay them out again in 2 lines, to achieve balanced width:

| ** ***       |
| ***** ** *   |


The result is 2 boxes in the first line, and 3 boxes in the second line: List<int> result = [2, 3]. Widths are now 5 and 8. Difference is 3, and minWidth is 8.

Please note, we cannot change their order. If we could, then the difference would be 1 and minWidth would be 7:

| ** *** *     |
| ***** **     |


My question:

What's the most efficient algorithm to solve this? I am interested in speed, and I don't care about memory usage.

• You'll have to decide how you want to measure how different the lengths are. Do you want to use max - min? Standard deviation? Something else? – D.W. Mar 28 '20 at 20:21
• @D.W. I know I want some "visually balanced" outcome for this, but I wouldn't know exactly how to define it. Maybe I could find the average line width, and then sum the square of the difference between the width of each line to this average. Maybe. I am open to suggestions. – MarcG Mar 28 '20 at 20:58
• You might want to wait at least 24 hours before accepting an answer to give at least everyone around the globe a chance to answer. – pipe Mar 29 '20 at 14:17