# 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

## 2 Answers

Have you considered using the total-fit line breaking algorithm(a) used by TeX(b) and developed by Donald Knuth and Michael Plass?

Edit:

The total-fit line breaking algorithm has already been implemented in many languages, including Java:

• The Knuth-Plass algorithm is also used in Adobe InDesign. – user207421 Mar 29 '20 at 6:35
• Wow, that paper is a fascinating reading, thanks for pointing it out. However, I am not really formatting text, but only boxes, with no space between them. So the concepts of hyphenation and shrinking and expanding glue make no sense in my case. I will soon need another version with spacing, but that's another question. Well, I guess that algorithm could work in both cases, but I just searched now and couldn't find a Java or C# version. I wouldn't really know how to translate from Rust or C. Translating that other one from Python was already troubling for me. – MarcG Mar 30 '20 at 2:42
• Do these take into account the fact that the number of lines is fixed? – MarcG Mar 28 '20 at 21:23
• @MarcG yes, they can easily handle that constraint. – D.W. Mar 28 '20 at 21:25