<p>If you can compute the raggedness of a line without knowing anything about the other lines, then you can model the problem as finding a minimum-weight $M$-link path in a graph. With concave integer weights for edges, there is <a href="http://dx.doi.org/10.1007/BF02574380" rel="nofollow">an algorithm</a> that solves the problem in $O(N \log U)$ time, where $U$ is the largest absolute edge weight. <a href="http://dx.doi.org/10.1006/jagm.1998.0955" rel="nofollow">Another algorithm</a> solves the problem in $N 2^{O(\sqrt{\log M \log \log N})}$ time for any concave edge weights, assuming $M = \Omega(\log N)$. Both algorithms assume that you can compute the weight of an edge in constant time.</p>

<p>You could also use binary search to find a line width such that SMAWK uses $M$ lines with it. In some cases, this algorithm does not guarantee a solution with exactly $M$ lines, however.</p>

CC BY-SA 3.0
2012-03-07T23:41:05.630Z
I'm very sorry but I don't think I follow. Is "edge weight" the length of a word? How does the "graph" look like? Is it just a linear graph where nodes are the breakpoints and edges are the lengths of words? And this "M-link path" breaks it up so that the resulting segments have minimal sum of edges? But most importantly, in the very first sentence - I'm not sure if I can compute the raggedness independently. It roughly is the difference between the longest line and the actual line so I need to know something about the other lines, no? More so for the last line, please see 15th comment above.
Ecir Hana
CC BY-SA 3.0
2012-03-08T13:42:14.540Z
@Ecir: We are looking for the minimum-weight path having exactly $M$ edges from node $1$ to node $N+1$. Having edge $(i,j)$ in the path means that words $i$ to $j-1$ form a single line, and the weight of the edge is the contribution of that line to the raggedness of the solution.
Jouni Sirén
CC BY-SA 3.0
2012-03-08T13:59:50.133Z
@Ecir: Essentially all algorithms based on dynamic programming require that you can compute the raggedness of a line independently. If that is not the case, you might want to use something like my second idea: guess a line width, compute a solution based on that width, and iterate to find better solutions.
Jouni Sirén
CC BY-SA 3.0
2012-03-10T17:53:12.473Z
thank you for the explanation. Please, I have two more question: when using the "binary search" option, is there anything I can do to guarantee the number M of lines? If I add small random epsilon to each line width so there would be no lines with the same width, I could gain more resolution over the placing of breaks.
Ecir Hana
CC BY-SA 3.0
2012-03-10T17:53:56.997Z
And in the case of "M-link path", both papers mention that "it is easy to show that the minimum K-link path can be computed in O(nK) time" - do you perhaps know what do they mean? I couldn't find any further information on it. The problem is, those papers are a tiny bit too complicated for my little head so I'm trying to find more information, an implementation maybe, ...
Ecir Hana
CC BY-SA 3.0
2012-03-11T19:12:54.003Z
@Ecir: Use binary search to find the range of line widths with which SMAWK finds a $M'$-line solution, for the largest $M' \le M$. Pick some line width from that range, and use the other algorithm to find an optimal $M$-line solution for that line width. You could also pick several different line widths and return the $M$-line solution with the least amount of raggedness.
Jouni Sirén
CC BY-SA 3.0
2012-03-07T16:21:39.310Z
2012-03-07T16:21:39.310Z
Jouni Sirén
<p>I don't know if this helps, but towards the end of <a href="http://www.php.net/manual/en/ref.strings.php#87116" rel="nofollow">this comment</a> someone implements what you want in PHP; maybe you can figure out the algorithm.</p>

CC BY-SA 3.0
2012-03-03T11:12:10.647Z
In the comment they just cut-off the remaining lines after the desired number of lines. They use PHP's `wordwrap()`, which in turn uses the greedy (i.e. no "evenly") algorithm for wrapping. Even then, the question remains how to "guess" the `$width` argument of `wordwrap()`. But thanks for the reply, anyway!
Ecir Hana
CC BY-SA 3.0
2012-03-03T10:43:33.477Z
2012-03-03T10:43:33.477Z
adrianp
<p>There is a linear time algorithm for breaking text evenly into lines of maximum width. It uses SMAWK (or Knuth &amp; Plass) and "evenly" means:
<a href="http://en.wikipedia.org/wiki/Word_wrap#Minimum_raggedness" rel="nofollow">http://en.wikipedia.org/wiki/Word_wrap#Minimum_raggedness</a></p>

<p>Is there an algorithm or a concave cost function for algorithm above which would take into account the number of lines I would like the text break into, instead of the maximum line width? Also in linear time?</p>

<p>In other words, I'm looking for a line breaking (or paragraph formation, or word wrapping) algorithm where the input is the desired number of lines, not the desired line width.</p>

<p>Just to describe a practically unusable approach: There are N words and N-1 spaces in-between each word pair, M is the desired number of lines (M &lt;= N). After each space there might be at most one (possibly zero) line-break. Now, the algorithm would try to place the breaks in each possible combination, calculating the "raggedness" and return the best one. How to do it much faster?</p>

<p>Also, does such a problem have a name? What "family" of problems does it belong to? (E.g. "bin packing") If I wouldn't need the perfectly optimal solution, just a very good one, is it possible to solve it much faster? (some form of heuristics could be usable, if for a given input there were always the same, possibly sub-optimal, solution).</p>

<p><strong>Update</strong></p>

<p>Chandra Chekuri suggested bellow "a problem in Kleinberg and Tardos chapter on dynamic programming". It was a good read but it deals with line breaking based on width rather than line count. It might be adaptable to this problem which is something I'm trying to figure out now. Here is a good link to the solution, they even claim to solve it in linear time:
<a href="http://web.media.mit.edu/~dlanman/courses/cs157/HW5.pdf" rel="nofollow">http://web.media.mit.edu/~dlanman/courses/cs157/HW5.pdf</a></p>

<p>Also, there is a chapter "8.5 The Partition Problem" in The Algorithm Design Manual by Skiena which seems to be exactly on-topic, I'm still reading it, tough. (Unfortunately, from what I understood it has quadratic time complexity)</p>

CC BY-SA 3.0
2012-03-07T07:26:55.080Z
Does the last line contribute to the cost, in your case?
Radu GRIGore
CC BY-SA 3.0
2012-03-07T09:24:52.930Z
That's a difficult question. Yes, but in different way than the other lines. I would prefer the last line not to contribute to the cost but I don't want it to be totally arbitrary. Perhaps there really should be a parameter of "optimal width" which would grow/shrink the last line based on its difference to the maximum width of the other lines. So for example: If I say "3 rows" then the maximum line width might be from interval 80-120 (last line as wide as the others-last line containing just one word), then "optimal width" of 120 would pick the later option.
Ecir Hana
CC BY-SA 3.0
2012-02-26T15:38:27.260Z
Nice dynamic programming problem!  I might use it as homework in my class next semester.
Jeffε
CC BY-SA 3.0
2012-02-26T16:03:27.853Z
What is the metric for "raggedness"? I assume it's the variance either of the number of characters in a line or the length of a line (if you're given a variable-width font)?
Peter Shor 
CC BY-SA 3.0
2012-02-26T17:30:06.413Z
"Raggedness" is the sum of squared differences between desired line length and actual line length. A line must not be longer than the desired length. So yes, you are right.
Ecir Hana
CC BY-SA 3.0
2012-02-26T18:07:37.727Z
@Eric: actually, I'm wrong ... if a line must not be longer than the desired length, it's a slightly different metric than the variance.
Peter Shor 
CC BY-SA 3.0
2012-02-27T07:58:17.533Z
@JɛﬀE if you want to use it for a homework problem, better close the question before the answer gets published on the web.
Joe
CC BY-SA 3.0
2012-02-27T09:22:12.193Z
@Joe: as someone really interested in the answer I would prefer the question to be answered, rather than closed.
Ecir Hana
CC BY-SA 3.0
2012-02-27T16:49:08.483Z
@Ecir: My intuition is that is shouldn't be hard to modify SMAWK or one of its variants to answer this, but I don't have time to work out the details right now.
Peter Shor 
CC BY-SA 3.0
2012-02-29T01:29:28.497Z
@EcirHana, Unfortunately, once it's implied that your question is "homework level" you are not likely to get a full answer here.
Joe
CC BY-SA 3.0
2012-02-29T09:43:13.687Z
@Joe: it's not a homework, I don't even study CS. What the "homework level" goes, I find it very interesting that some people cannot even image how to solve a problem, while other people consider it "homework level". That said, the answer could be erased in a week or sent to my email for example. And I would be thankful for not so "full answer", as well.
Ecir Hana
CC BY-SA 3.0
2012-03-01T03:40:34.630Z
@EcirHana you might have better luck asking on http://stackoverflow.com/faq
Joe
CC BY-SA 3.0
2012-03-02T07:50:01.300Z
@PeterShor you were right about the "raggedness". The "line must not be longer" is wrong because in that case it would be possible to set such a maximum width that it would be impossible to break the text into such-and-such number of lines. I mean, the maximum line width and row count depend on each other. So just the sum of squared differences.
Ecir Hana
CC BY-SA 3.0
2012-03-04T00:33:30.657Z
There is a problem in Kleinberg and Tardos chapter on dynamic programming which is to format in such a way as to minimize the sum of the slacks in the lines.
Chandra Chekuri
CC BY-SA 3.0
2012-03-04T09:32:10.247Z
@ChandraChekuri: thank you for the pointer, I'll have a look!
Ecir Hana
<ds.algorithms>
Break text evenly into certain number of lines
Ecir Hana
# Break text evenly into certain number of lines

(Asked by: username_0 on 2012-02-26)

There is a linear time algorithm for breaking text evenly into lines of maximum width. It uses SMAWK (or Knuth & Plass) and "evenly" means:
<http://en.wikipedia.org/wiki/Word_wrap#Minimum_raggedness>

Is there an algorithm or a concave cost function for algorithm above which would take into account the number of lines I would like the text break into, instead of the maximum line width? Also in linear time?

In other words, I'm looking for a line breaking (or paragraph formation, or word wrapping) algorithm where the input is the desired number of lines, not the desired line width.

Just to describe a practically unusable approach: There are N words and N-1 spaces in-between each word pair, M is the desired number of lines (M <= N). After each space there might be at most one (possibly zero) line-break. Now, the algorithm would try to place the breaks in each possible combination, calculating the "raggedness" and return the best one. How to do it much faster?

Also, does such a problem have a name? What "family" of problems does it belong to? (E.g. "bin packing") If I wouldn't need the perfectly optimal solution, just a very good one, is it possible to solve it much faster? (some form of heuristics could be usable, if for a given input there were always the same, possibly sub-optimal, solution).

**Update**

username_5 suggested bellow "a problem in Kleinberg and Tardos chapter on dynamic programming". It was a good read but it deals with line breaking based on width rather than line count. It might be adaptable to this problem which is something I'm trying to figure out now. Here is a good link to the solution, they even claim to solve it in linear time:
<http://web.media.mit.edu/~dlanman/courses/cs157/HW5.pdf>

Also, there is a chapter "8.5 The Partition Problem" in The Algorithm Design Manual by Skiena which seems to be exactly on-topic, I'm still reading it, tough. (Unfortunately, from what I understood it has quadratic time complexity)

**Tags:** ds.algorithms

> **Comments:**
> **username_2**: Nice dynamic programming problem!  I might use it as homework in my class next semester.  
> **username_3**: What is the metric for "raggedness"? I assume it's the variance either of the number of characters in a line or the length of a line (if you're given a variable-width font)?  
> **username_0**: "Raggedness" is the sum of squared differences between desired line length and actual line length. A line must not be longer than the desired length. So yes, you are right.  
> **username_3**: @Eric: actually, I'm wrong ... if a line must not be longer than the desired length, it's a slightly different metric than the variance.  
> **username_4**: @JɛﬀE if you want to use it for a homework problem, better close the question before the answer gets published on the web.  
> **username_0**: @username_4: as someone really interested in the answer I would prefer the question to be answered, rather than closed.  
> **username_3**: @Ecir: My intuition is that is shouldn't be hard to modify SMAWK or one of its variants to answer this, but I don't have time to work out the details right now.  
> **username_4**: @EcirHana, Unfortunately, once it's implied that your question is "homework level" you are not likely to get a full answer here.  
> **username_0**: @username_4: it's not a homework, I don't even study CS. What the "homework level" goes, I find it very interesting that some people cannot even image how to solve a problem, while other people consider it "homework level". That said, the answer could be erased in a week or sent to my email for example. And I would be thankful for not so "full answer", as well.  
> **username_4**: @EcirHana you might have better luck asking on http://stackoverflow.com/faq  
> **username_0**: @PeterShor you were right about the "raggedness". The "line must not be longer" is wrong because in that case it would be possible to set such a maximum width that it would be impossible to break the text into such-and-such number of lines. I mean, the maximum line width and row count depend on each other. So just the sum of squared differences.  
> **username_5**: There is a problem in Kleinberg and Tardos chapter on dynamic programming which is to format in such a way as to minimize the sum of the slacks in the lines.  
> **username_0**: @ChandraChekuri: thank you for the pointer, I'll have a look!  
> **username_1**: Does the last line contribute to the cost, in your case?  
> **username_0**: That's a difficult question. Yes, but in different way than the other lines. I would prefer the last line not to contribute to the cost but I don't want it to be totally arbitrary. Perhaps there really should be a parameter of "optimal width" which would grow/shrink the last line based on its difference to the maximum width of the other lines. So for example: If I say "3 rows" then the maximum line width might be from interval 80-120 (last line as wide as the others-last line containing just one word), then "optimal width" of 120 would pick the later option.  

---

## 2 answers

### Answer by username_6 on 2012-03-07. Score: 4 | Accepted answer

If you can compute the raggedness of a line without knowing anything about the other lines, then you can model the problem as finding a minimum-weight $M$-link path in a graph. With concave integer weights for edges, there is [an algorithm](http://dx.doi.org/10.1007/BF02574380) that solves the problem in $O(N \log U)$ time, where $U$ is the largest absolute edge weight. [Another algorithm](http://dx.doi.org/10.1006/jagm.1998.0955) solves the problem in $N 2^{O(\sqrt{\log M \log \log N})}$ time for any concave edge weights, assuming $M = \Omega(\log N)$. Both algorithms assume that you can compute the weight of an edge in constant time.

You could also use binary search to find a line width such that SMAWK uses $M$ lines with it. In some cases, this algorithm does not guarantee a solution with exactly $M$ lines, however.

> **Comments:**
> **username_0**: I'm very sorry but I don't think I follow. Is "edge weight" the length of a word? How does the "graph" look like? Is it just a linear graph where nodes are the breakpoints and edges are the lengths of words? And this "M-link path" breaks it up so that the resulting segments have minimal sum of edges? But most importantly, in the very first sentence - I'm not sure if I can compute the raggedness independently. It roughly is the difference between the longest line and the actual line so I need to know something about the other lines, no? More so for the last line, please see 15th comment above.  
> **username_6**: @Ecir: We are looking for the minimum-weight path having exactly $M$ edges from node $1$ to node $N+1$. Having edge $(i,j)$ in the path means that words $i$ to $j-1$ form a single line, and the weight of the edge is the contribution of that line to the raggedness of the solution.  
> **username_6**: @Ecir: Essentially all algorithms based on dynamic programming require that you can compute the raggedness of a line independently. If that is not the case, you might want to use something like my second idea: guess a line width, compute a solution based on that width, and iterate to find better solutions.  
> **username_0**: thank you for the explanation. Please, I have two more question: when using the "binary search" option, is there anything I can do to guarantee the number M of lines? If I add small random epsilon to each line width so there would be no lines with the same width, I could gain more resolution over the placing of breaks.  
> **username_0**: And in the case of "M-link path", both papers mention that "it is easy to show that the minimum K-link path can be computed in O(nK) time" - do you perhaps know what do they mean? I couldn't find any further information on it. The problem is, those papers are a tiny bit too complicated for my little head so I'm trying to find more information, an implementation maybe, ...  
> **username_6**: @Ecir: Use binary search to find the range of line widths with which SMAWK finds a $M'$-line solution, for the largest $M' \le M$. Pick some line width from that range, and use the other algorithm to find an optimal $M$-line solution for that line width. You could also pick several different line widths and return the $M$-line solution with the least amount of raggedness.  

---

### Answer by username_7 on 2012-03-03. Score: -3

I don't know if this helps, but towards the end of [this comment](http://www.php.net/manual/en/ref.strings.php#87116) someone implements what you want in PHP; maybe you can figure out the algorithm.

> **Comments:**
> **username_0**: In the comment they just cut-off the remaining lines after the desired number of lines. They use PHP's `wordwrap()`, which in turn uses the greedy (i.e. no "evenly") algorithm for wrapping. Even then, the question remains how to "guess" the `$width` argument of `wordwrap()`. But thanks for the reply, anyway!  

---

