PHP中的平衡自动换行（最小的不整洁度）

一尘不染

PHP中的平衡自动换行（最小的不整洁度）

algorithm

我将在PHP中创建自动换行算法。我想在最多 m个字符的 n 行中分割一小段文本（短短语）（未给出 n
，因此将根据需要提供尽可能多的行）。特殊之处在于，各行之间的行长（以字符为单位）必须尽可能保持平衡。

输入文字示例：

How to do things

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

How to
do
things

所需的输出，始终为 m = 6 ：

How 
to do 
things

是否有人对如何实现此功能有建议或指导？基本上， 我在两三个 （尽可能多） 等长的行 上搜索漂亮的短短语 。

更新：看来我正在精确寻找
最小衣衫症自动换行算法
。但是我找不到真正的编程语言的任何实现（任何人，然后我都可以将其转换为PHP）。

更新2 ：我为此开始赏金。可能没有任何程序语言不存在任何最小衣着算法的公共实现吗？我需要以可以翻译为 程序说明
的方式编写的东西。我现在所能找到的只是（通用）方程式的束缚，但是需要最佳的搜索过程。对于仅能近似最佳搜索算法的实现，我也将不胜感激。

阅读 255

2020-07-28

共1个答案

一尘不染

用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

编辑：只是在Wikipedia页面上查看了最低程度的衣衫wrap的自动换行。将算法更改为给定算法（惩罚为平方）

2020-07-28