Word换行到X行而不是最大宽度(最小粗糙度)

Question

有没有人知道将输入字符串换行到指定行数而不是设置宽度的好算法.基本上要达到X线的最小宽度.

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"

根据需要插入新行.我可以找到其他自动换行问题,但它们都有一个已知宽度,并希望根据需要插入尽可能多的行以适应该宽度.我正好相反.

答案最好用.NET语言,但任何语言都会有所帮助.显然,如果有一个框架方式来做到这一点,我不知道让我知道.

编辑我发现了这个,我认为接受的答案是我的问题的解决方案,但我很难理解它.将文本划分为3个大小均匀的组的算法,任何人都可以将其转换为c#或vb.net.

Answer 1

解决这个问题的一种方法是使用动态编程,你可以使用动态编程解决这个问题,参见最小粗糙度算法.我使用了您在使用以下内容编辑帖子时添加的一些信息:算法将文本划分为3个大小合适的 组

符号:

让你的文字文件命名="word1 word2 .... wordp"

n =所需的行数

线宽= LEN(文件)/ n的

成本函数:

首先,你需要定义一个成本函数,在同一行中有单词[i]到单词[j],你可以采取与维基百科上的单词相同的一个,例如:p = 2:

它表示线的目标长度与实际长度之间的距离.

可以使用以下递归关系定义最优解的总成本函数:

解决问题:

您可以使用动态编程解决此问题.我从您提供的链接中获取了代码,并将其更改为a,以便您了解该程序正在使用的内容.

1. 在阶段k,你在k行添加单词.
2. 然后你看看在第k行有单词i到j的最优成本.
3. 一旦你从第1行到第n行,你将在最后一步中获得最小的成本,并获得最佳结果:

以下是代码的结果:

D=minragged('Just testing to see how this works.')

number of words: 7
------------------------------------
stage : 0
------------------------------------
word i to j in line 0       TotalCost (f(j))
------------------------------------
i= 0 j= 0           121.0
i= 0 j= 1           49.0
i= 0 j= 2           1.0
i= 0 j= 3           16.0
i= 0 j= 4           64.0
i= 0 j= 5           144.0
i= 0 j= 6           289.0
i= 0 j= 7           576.0
------------------------------------
stage : 1
------------------------------------
word i to j in line 1       TotalCost (f(j))
------------------------------------
i= 0 j= 0           242.0
i= 0 j= 1           170.0
i= 0 j= 2           122.0
i= 0 j= 3           137.0
i= 0 j= 4           185.0
i= 0 j= 5           265.0
i= 0 j= 6           410.0
i= 0 j= 7           697.0
i= 1 j= 2           65.0
i= 1 j= 3           50.0
i= 1 j= 4           58.0
i= 1 j= 5           98.0
i= 1 j= 6           193.0
i= 1 j= 7           410.0
i= 2 j= 4           26.0
i= 2 j= 5           2.0
i= 2 j= 6           17.0
i= 2 j= 7           122.0
i= 3 j= 7           80.0
------------------------------------
stage : 2
------------------------------------
word i to j in line 2       TotalCost (f(j))
------------------------------------
i= 0 j= 7           818.0
i= 1 j= 7           531.0
i= 2 j= 7           186.0
i= 3 j= 7           114.0
i= 4 j= 7           42.0
i= 5 j= 7           2.0
reversing list
------------------------------------
Just testing        12
to see how      10
this works.         11

• *因此最好的选择是在最后一行有5到7个单词.(参见stage2)
• 然后在第二行中的第2到第5行(cf stage1)
• 然后是第一行的0到2字(参见第0阶段).*

反过来,你会得到:

Just testing          12
to see how          10
this works.          11

这是打印推理的代码,(在python中抱歉我不使用C#...但我实际上有人在C#中翻译了代码):

def minragged(text, n=3):


    P=2
    words = text.split()
    cumwordwidth = [0]
    # cumwordwidth[-1] is the last element
    for word in words:
        cumwordwidth.append(cumwordwidth[-1] + len(word))
    totalwidth = cumwordwidth[-1] + len(words) - 1  # len(words) - 1 spaces
    linewidth = float(totalwidth - (n - 1)) / float(n)  # n - 1 line breaks

    print "number of words:", len(words)
    def cost(i, j):
        """
        cost of a line words[i], ..., words[j - 1] (words[i:j])
        """
        actuallinewidth = max(j - i - 1, 0) + (cumwordwidth[j] - cumwordwidth[i])
        return (linewidth - float(actuallinewidth)) ** P

    """
    printing the reasoning and reversing the return list
    """
    F={} # Total cost function

    for stage in range(n):
        print "------------------------------------"
        print "stage :",stage
        print "------------------------------------"
        print "word i to j in line",stage,"\t\tTotalCost (f(j))"
        print "------------------------------------"


        if stage==0:
            F[stage]=[]
            i=0
            for j in range(i,len(words)+1):
                print "i=",i,"j=",j,"\t\t\t",cost(i,j)
                F[stage].append([cost(i,j),0])
        elif stage==(n-1):
            F[stage]=[[float('inf'),0] for i in range(len(words)+1)]
            for i in range(len(words)+1):
                    j=len(words)
                    if F[stage-1][i][0]+cost(i,j)<F[stage][j][0]: #calculating min cost (cf f formula)
                        F[stage][j][0]=F[stage-1][i][0]+cost(i,j)
                        F[stage][j][1]=i
                        print "i=",i,"j=",j,"\t\t\t",F[stage][j][0]            
        else:
            F[stage]=[[float('inf'),0] for i in range(len(words)+1)]
            for i in range(len(words)+1):
                for j in range(i,len(words)+1):
                    if F[stage-1][i][0]+cost(i,j)<F[stage][j][0]:
                        F[stage][j][0]=F[stage-1][i][0]+cost(i,j)
                        F[stage][j][1]=i
                        print "i=",i,"j=",j,"\t\t\t",F[stage][j][0]

    print 'reversing list'
    print "------------------------------------"
    listWords=[]
    a=len(words)
    for k in xrange(n-1,0,-1):#reverse loop from n-1 to 1
        listWords.append(' '.join(words[F[k][a][1]:a]))
        a=F[k][a][1]
    listWords.append(' '.join(words[0:a]))
    listWords.reverse()

    for line in listWords:
        print line, '\t\t',len(line)

    return listWords

Answer 2

以下是算法中接受的解决方案，将文本分为 3 个大小均匀的组，转换为 C#：

static List<string> Minragged(string text, int n = 3)
{
    var words = text.Split();

    var cumwordwidth = new List<int>();
    cumwordwidth.Add(0);

    foreach (var word in words)
        cumwordwidth.Add(cumwordwidth[cumwordwidth.Count - 1] + word.Length);

    var totalwidth = cumwordwidth[cumwordwidth.Count - 1] + words.Length - 1;

    var linewidth = (double)(totalwidth - (n - 1)) / n;

    var cost = new Func<int, int, double>((i, j) =>
    {
        var actuallinewidth = Math.Max(j - i - 1, 0) + (cumwordwidth[j] - cumwordwidth[i]);
        return (linewidth - actuallinewidth) * (linewidth - actuallinewidth);
    });

    var best = new List<List<Tuple<double, int>>>();

    var tmp = new List<Tuple<double, int>>();
    best.Add(tmp);
    tmp.Add(new Tuple<double, int>(0.0f, -1));
    foreach (var word in words)
        tmp.Add(new Tuple<double, int>(double.MaxValue, -1));

    for (int l = 1; l < n + 1; ++l)
    {
        tmp = new List<Tuple<double, int>>();
        best.Add(tmp);
        for (int j = 0; j < words.Length + 1; ++j)
        {
            var min = new Tuple<double, int>(best[l - 1][0].Item1 + cost(0, j), 0);
            for (int k = 0; k < j + 1; ++k)
            {
                var loc = best[l - 1][k].Item1 + cost(k, j);
                if (loc < min.Item1 || (loc == min.Item1 && k < min.Item2))
                    min = new Tuple<double, int>(loc, k);
            }
            tmp.Add(min);
        }
    }

    var lines = new List<string>();
    var b = words.Length;

    for (int l = n; l > 0; --l)
    {
        var a = best[l][b].Item2;
        lines.Add(string.Join(" ", words, a, b - a));
        b = a;
    }

    lines.Reverse();
    return lines;
}