Consider the problem of printing a paragraph neatly on a printer, with fixed width font.
The input text is a sequence of n words of lengths \(l_1, l_2, \dots, l_n\) . The line length
is \(M\) (the maximum number of characters per line). We expect that the paragraph is left justified,
that all first words on a line start at the leftmost position and that there is exactly one space
between any two words on the same line. We want the uneven right ends of all the lines to be together as
neat as possible. Our criterion of neatness is that we wish to minimize the sum, over all lines
except the last, of the cubes of the numbers of extra space characters at the ends of the lines. Note that
if a printed line contains words \(i\) through \(j\), then the number of spaces at the end of
the line is
$$
f(i, j) = M - j + i - \sum_{k=i}^{j}{l_k}
$$
This problem was sourced from http://www.cs.uiuc.edu/~jeffe/teaching/algorithms/ , thanks Mr. Erickson!
How do we position the line breaks? A recursive approach immediately springs in mind: we put а line break at some, yet undecided, place and then optimally break into lines the rest of the words:
How do we position the line breaks? A recursive approach immediately springs in mind: we put а line break at some, yet undecided, place and then optimally break into lines the rest of the words:
place_breaks (words[1..n]) t = choose_break_position() place_breaks (words[1..t])In a sequence of \(n\) words we may put a break before the first word, before the second word, before the third, ... and so on, for a total of \(n\) possible positions, as long as the words after the break fit on a single line, which is equivalent to the condition \(f(i,j) \gt 0\). Of all the allowed positions to place a break, we choose the position, which minimizes the cost of placing a break there. If we denote by \(C(k)\) the minimum cost of splitting words \(1\) through \(k\), we have for the cost function $$ C(k) = \min_{0 \le t < k, f(t,k-1) \ge 0} \lbrace C(t) + f(t, k-1)^3 \rbrace $$ However, note that the spaces at the end of our last line do not participate in evaluating neatness. Therefore, for the last line only, our cost function \(T(n)\) would look like $$ T(n) = \min_{0 \le t < n, f(t,n-1) \ge 0} \lbrace C(t) \rbrace $$ Boundary case for the cost function would be \(C(0) = 0\) and now we have all the ingredients for implementing an efficient and correct algorithm. The cost function can be evaluated bottom up (\(C(0), C(1), \dots , C(n)\)) using \(O(n)\) additional space for storing intermediate results and each time we choose a break position, we will record it.
class line_breaker {
public:
void break_lines (size_t, const std::vector<std::string> &);
protected:
long f (size_t, size_t);
void calculate_C (size_t);
size_t calculate_T (size_t);
std::vector<size_t> S;
struct solution {
long cost;
size_t pos;
};
std::vector<solution> C;
size_t M;
};
This is how the implementation will look like: we encapsulate the functions
and the additional space required in a class to avoid passing lots of parameters
around. The member function f is our penalty function, according the definition above
and the member functions calculate_T and calculate_C, well, calculate the cost
function for the last line break and for all the other line breaks, respectively.
To speed up the calculation of the penalty function, we use the well-known trick of keeping
in the vector S the accumulated lengths of the words, so \(S_i = \sum_{k=0}^i{l_k}\).
The implementation of the helper functions comes directly form the formulae above:
long
line_breaker::f (size_t i, size_t j) {
long x;
if (i >= j + 1)
return -1;
else {
long y = i == 0 ? S[j] : S[j] - S[i-1];
x = M - j + i - y;
return x * x * x;
}
}
void
line_breaker::calculate_C (size_t n) {
C[0].cost = 0;
C[0].pos = 0;
for (size_t i = 1; i <= n; ++i) {
size_t t, min_t = 0;
long min = LONG_MAX;
for (t = 0; t < i; ++t) {
if (f (t, i-1) >= 0 && C[t].cost + f (t, i-1) < min) {
min = C[t].cost + f(t, i-1);
min_t = t;
}
}
C[i].cost = min;
C[i].pos = min_t;
}
}
size_t
line_breaker::calculate_T (size_t n) {
size_t t, min_t = 0;
long min = LONG_MAX;
calculate_C (n);
for (t = 0; t < n; ++t) {
if (f(t, n-1) >= 0 && C[t].cost < min) {
min = C[t].cost;
min_t = t;
}
}
return min_t;
}
And now for the function, that performs the actual splitting of the text:
void
line_breaker::break_lines (size_t m, const std::vector<std::string> &text) {
We pass the length of a line in the parameter m and the text to format in the
parameter text
S.clear();
C.clear();
Clean up whatever is left from a previous invocation.
size_t s = 0, n;
for (const auto &str : text) {
n = str.size();
if (n > m)
return;
s += n;
S.push_back (s);
}
n = text.size();
C.resize (n+1);
M = m;
Prepare the various working areas. Note that we check that each word length is less than or equal to
the line length - this will guarantee that a solution to the problem in fact exists.
size_t t = calculate_T (n);
... and invoke the function to place the line breaks, starting from the last one.
std::vector<size_t>div;
div.push_back (n);
while (t > 0) {
div.push_back (t);
t = C[t].pos;
}
std::reverse (div.begin(), div.end());
The member function calculate_T will return the index of the last break placed. The corresponding element
of the vector C will give us the position of the previous break and so on, until we reach position zero.
Now we have collected all the line breaks in vector div and have only to reverse it ...
size_t i = 0;
for (auto j : div) {
while (i < j) {
std::cout << text[i] << " ";
++i;
}
std::cout << "\n";
}
std::cout << std::endl;
}
... and output the formatted lines. And that's it.
The source follows in its entirety.
#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>l
#include <string>
class line_breaker {
public:
void break_lines (size_t, const std::vector<std::string> &);
protected:
long f (size_t, size_t);
void calculate_C (size_t);
size_t calculate_T (size_t);
std::vector<size_t> S;
struct solution {
long cost;
size_t pos;
};
std::vector<solution> C;
size_t M;
};
long
line_breaker::f (size_t i, size_t j) {
long x;
if (i >= j + 1)
return -1;
else {
long y = i == 0 ? S[j] : S[j] - S[i-1];
x = M - j + i - y;
return x * x * x;
}
}
void
line_breaker::calculate_C (size_t n) {
C[0].cost = 0;
C[0].pos = 0;
for (size_t i = 1; i <= n; ++i) {
size_t t, min_t = 0;
long min = LONG_MAX;
for (t = 0; t < i; ++t) {
if (f (t, i-1) >= 0 && C[t].cost + f (t, i-1) < min) {
min = C[t].cost + f(t, i-1);
min_t = t;
}
}
C[i].cost = min;
C[i].pos = min_t;
}
}
size_t
line_breaker::calculate_T (size_t n) {
size_t t, min_t = 0;
long min = LONG_MAX;
calculate_C (n);
for (t = 0; t < n; ++t) {
if (f(t, n-1) >= 0 && C[t].cost < min) {
min = C[t].cost;
min_t = t;
}
}
return min_t;
}
void
line_breaker::break_lines (size_t m, const std::vector<std::string> &text) {
S.clear();
C.clear();
size_t s = 0, n;
for (const auto &str : text) {
n = str.size();
if (n > m)
return;
s += n;
S.push_back (s);
}
n = text.size();
C.resize (n+1);
M = m;
size_t t = calculate_T (n);
std::vector<size_t> div;
div.push_back (n);
while (t > 0) {
div.push_back (t);
t = C[t].pos;
}
std::reverse (div.begin(), div.end());
size_t i = 0;
for (auto j : div) {
while (i < j) {
std::cout << text[i] << " ";
++i;
}
std::cout << "\n";
}
std::cout << std::endl;
}
std::vector<std::string> text = {
"Lorem", "Ipsum", "is", "simply", "dummy", "text", "of", "the",
"printing", "and", "typesetting", "industry.", "Lorem", "Ipsum",
"has", "been", "the", "industry's", "standard", "dummy", "text",
"ever", "since", "the", "1500s", "when", "an", "unknown", "printer",
"took", "a", "galley", "of", "type", "and", "scrambled", "it", "to",
"make", "a", "type", "specimen", "book.", "It", "has", "survived",
"not", "only", "five", "centuries,", "but", "also", "the", "leap",
"into", "electronic", "typesetting,", "remaining", "essentially",
"unchanged.", "It", "was", "popularised", "in", "the", "1960s",
"with", "the", "release", "of", "Letraset", "sheets", "containing",
"Lorem", "Ipsum", "passages,", "and", "more", "recently", "with",
"desktop", "publishing", "software", "like", "Aldus", "PageMaker",
"including", "versions", "of", "Lorem", "Ipsum" };
int
main () {
line_breaker br;
br.break_lines (30, text);
}
