Word wrap to X lines instead of maximum width (Least raggedness)

Asked 2011-06-21T13:28:03.003

Does anyone know a good algorithm to word wrap an input string to a specified number of lines rather than a set width. Basically to achieve the minimum width for X lines.

e.g. "I would like to be wrapped into two lines"
goes to
"I would like to be
wrapped into two lines"

"I would like to be wrapped into three lines"
goes to
"I would like to
be wrapped into
three lines"

Inserting new lines as required. I can find other word wrap questions but they all have a known width and want to insert as many lines as needed to fit that width. I am after the opposite.

Answers preferable in a .NET language but any language would be helpful. Obviously if there is a framework way to do this I am not aware of let me know.

Edit I have found this since which I think the accepted answer is the solution to my problem but am having difficulty understanding it. Algorithm to divide text into 3 evenly-sized groups any chance someone could convert it to c# or vb.net.

algorithm word-wrap

Edit Report

2 Answers

There was a discussion about this exact problem (though it was phrased in a different way) at http://www.perlmonks.org/?node_id=180276.

In the end the best solution was to do a binary search through all possible widths to find the smallest width that wound up with no more than the desired number of columns. If there are n items and the average width is m, then you'll need O(log(n) + log(m)) passes to find the right width, each of which takes O(n) time, for O(n * (log(n) + log(m))). This is probably fast enough with no more need to be clever.

If you wish to be clever, you can create an array of word counts, and cumulative lengths of the words. Then use binary searches on this data structure to figure out where the line breaks are. Creating this data structure is O(n), and it makes all of the passes to figure out the right width be O(log(n) * (log(n) + log(m))) which for reasonable lengths of words is dominated by your first O(n) pass.

If the widths of words can be floating point, you'll need to do something more clever with the binary searches, but you are unlikely to need that particular optimization.

answered 2011-06-23T21:16:49.203

I just thought of an approach:
You can write a function accepting two parameters 1. String 2. Number of lines

Get the length of the string (String.length if using C#). Divide the length by number of lines (lets say the result is n)

Now start a loop and access each character of the string (using string[i]) Insert a '\n\r' after every nth occurrence in the array of characters.

In the loop maintain a temp string array which would be null if there is a blank character(maintaining each word).
If there is a nth occurrence and temp string is not null then insert '\n\r' after that temp string.

answered 2011-06-21T16:07:19.260

Word wrap to X lines instead of maximum width (Least raggedness)

2 Answers

Your Answer