Разбейте текст равномерно на определенное количество строк

Question

Существует линейный алгоритм времени (или алгоритм квадратичного времени Кнута и Пласса) для равномерного разбиения текста на строки максимальной ширины. Он использует SMAWK и «равномерно» означает:
http://en.wikipedia.org/wiki/Word_wrap#Minimum_raggedness

Существует ли алгоритм или вогнутая функция стоимости для алгоритма, описанного выше, которая учитывала бы количество строк, на которые я хотел бы разбить текст, вместо максимальной ширины строки?

Другими словами, я ищу алгоритм разрыва строки (или формирования абзаца, или переноса слов), в котором вводом является желаемое количество строк, а не желаемая ширина строки.

Просто для описания практически непригодного подхода: между каждой парой слов есть N слов и N-1 пробелов, M - желаемое количество строк (M <= N). После каждого пробела может быть не более одного (возможно, нулевого) переноса строки. Теперь алгоритм будет пытаться поместить разрывы в каждую возможную комбинацию, вычисляя «неровность» и возвращая лучшую. Как сделать это намного быстрее? </p>

Answer 1

Вы можете просто свести проблему достижения заданного количества строк к проблеме разбивания строк после максимальной длины, рассчитав максимальную длину как общую длину строки, деленную на количество строк, которое вы хотите. Поскольку фактическая длина линии во многих случаях будет меньше максимальной длины, вам, вероятно, потребуется вычесть 1 из необходимого количества строк.