2

There is a linear time algorithm (or quadratic time algorithm by Knuth & Plass) for breaking text evenly into lines of maximum width. It uses SMAWK 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?

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?

Ecir Hana
  • 10,864
  • 13
  • 67
  • 117
  • Can you explain about the "raggedness"? How do you decide which result is better then the other? Without an evaluation - you could just return a random insertion of line-breaks, but I assume this is not the case. – amit Mar 01 '12 at 18:53
  • The text is left-aligned - that is, there probably is leftover whitespace on the right, let's call it waste. In other words, waste is the difference between maximum (optimal, desired) line width and actual line width. Now we calculate the square root of the waste, so we punish really wrong ones, sum all the waste squares together and that's the "raggedness". We just try to avoid the gaps, i.e. we want the lines to have as similar widths as possible. Btw, it's all in the Wikipedia link above. – Ecir Hana Mar 01 '12 at 19:02

1 Answers1

0

You could simply reduce the problem of achieving a given number of lines to the problem of breaking lines after a maximum length by calculating the maximum length as the total length of the string divided by the number of lines you want. As the actual length of a line is going to be less than the maximum length in many cases, you would probably need to subtract 1 from the number of lines you want.

Lars Kotthoff
  • 107,425
  • 16
  • 204
  • 204
  • The problem is that such approach guarantees there wont be less lines that the quotient, i.e. it could happen there will be a few more than that. For example: I want 6 lines and the text is `a aaaaaa aaaaa aaaaaaaaa aaaaa aaaaaaaaaaa aaaaaaa aa a a a a a aaaaaa aaaaaa aaaaaaa aaaaaaa` but it creates 8 lines. – Ecir Hana Mar 01 '12 at 23:40
  • Yes, hence my suggestion to subtract 1. Unless you have very short lines (or very long words) you'd probably be fine in practice. – Lars Kotthoff Mar 02 '12 at 08:51
  • My point is, the subtraction seem rather arbitrary: it doesn't work for 3 rows and `aaaaa aaaaa aaaaaaaaa aaaaaaaaa aaaaaaaaa a a aaaa aaaaaaaaa aaa aaaaaa` – Ecir Hana Mar 02 '12 at 14:07
  • I agree; it's a heuristic and you might need to adjust it for your specific purpose. – Lars Kotthoff Mar 02 '12 at 19:59