title: Break text evenly into certain number of lines
body: <p>There is a linear time algorithm (or quadratic time algorithm by Knuth &amp; Plass) for breaking text evenly into lines of maximum width. It uses SMAWK and "evenly" means:<br>
  <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?</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>