我要做出一个PHP自动换行算法。我想要拆分文本的小块（短语）的 N 的最大行的 M 的字符（ N 的没有给出，因此会有尽可能多的行作为需要的话）。特点是，线的长度（以字符为单位）必须尽可能跨行多少平衡。

I'm going to make a word wrap algorithm in PHP. I want to split small chunks of text (short phrases) in n lines of maximum m characters (n is not given, so there will be as much lines as needed). The peculiarity is that lines length (in characters) has to be much balanced as possible across lines.

输入文本的例子：

How to do things

错误输出（这是正常的自动换行行为）， M = 6 的：

How to
do
things

所需的输出，总的 M = 6 的：

How 
to do 
things

有没有人对如何实现这一功能的建议或指引？基本上，我在寻找的东西pretty的打印短语在两个或三个（尽可能）等长线路

更新：看来我在寻找确切的 最小毛糙自动换行算法 。但我不能找到一个真正的编程语言（任何人的话，我可以把它在PHP）的任何实施。

Update: It seems I'm searching exactly for a Minimum raggedness word wrap algorithm. But I can't find any implementation in a real programming language (anyone, then I can convert it in PHP).

更新2 ：我开始一个赏金这一点。难道不存在任何公开的实施最低毛糙算法在任何过程语言？我需要的东西写的方式，可以翻译成的程序指令的。所有我现在能找到的（通用）式只是一个bounch但是这需要一个最佳的搜索过程。我会很感激也为一个实现，只能近似的优化搜索算法。

Update 2: I started a bounty for this. Is it possible that do not exist any public implementation of Minimum raggedness algorithm in any procedural language? I need something written in a way that can be translated into procedural instructions. All I can find now is just a bounch of (generic) equation that however need a optimal searching procedure. I will be grateful also for an implementation that can only approximate that optimal searching algorithm.

推荐答案

快速和肮脏的，在C ++

Quick and dirty, in c++

#include <sstream>
#include <iostream>
#include <vector>
#include <cstdlib>
#include <memory.h>

using namespace std;

int cac[1000][1000];
string res[1000][1000];
vector<string> words;
int M;

int go(int a, int b){
    if(cac[a][b]>= 0) return cac[a][b];
    if(a == b) return 0;

    int csum = -1;
    for(int i=a; i<b; ++i){
    csum += words[i].size() + 1;
    }
    if(csum <= M || a == b-1){
    string sep = "";
        for(int i=a; i<b; ++i){
            res[a][b].append(sep);
            res[a][b].append(words[i]);
            sep = " ";
    }
    return cac[a][b] = (M-csum)*(M-csum);
    }

    int ret = 1000000000;
    int best_sp = -1;
    for(int sp=a+1; sp<b; ++sp){
    int cur = go(a, sp) + go(sp,b);
    if(cur <= ret){
        ret = cur;
        best_sp = sp;
    }
    }
    res[a][b] = res[a][best_sp] + "\n" + res[best_sp][b];
    return cac[a][b] = ret;
}


int main(int argc, char ** argv){
    memset(cac, -1, sizeof(cac));
    M = atoi(argv[1]);
    string word;
    while(cin >> word) words.push_back(word);
    go(0, words.size());
    cout << res[0][words.size()] << endl;
}

测试：

$ echo "The quick brown fox jumps over a lazy dog" |./a.out 10
The quick
brown fox
jumps over
a lazy dog

编辑：只是看着最低毛糙自动换行的维基百科页面。更改算法对给定的一个（与平方处罚）

just looked at the wikipedia page for minimum raggedness word wrap. Changed algorithm to the given one (with squared penalties)