如何有效地找到理想的列数的一定宽度的字符串？ [英] How to efficiently find the ideal column count for strings of a certain width?

问题描述

我的 N 的不同长度的字符串取值<子> 1 ，S ₂ ，...，S <子> N 我要显示在的 C 的列的终端。该终端具有的 M 的字符的宽度。每列的我的具有一定的宽度的瓦特<子>我 的，它等于该列中的最长条目的宽度。每对列之间有一定量的空间的取值的。所有列包括空间之间不能比端子（宽度较大的总宽度的是W <子> 1 + W ₂ + ... + W <子>ç + 的（ç - 1 ）的·S≤米的）。每列应包含与lceil;的 N / C 的＆rceil;串，除了当的 N 的是不通过的 C 的，在这种情况下，最后的几列应是短了一个条目或只有最后一列均匀地可分割应或者是短视字符串是否跨过或向下。

I have n strings of different length s₁, s₂, …, s_n that I want to display on a terminal in c columns. The terminal has a width of m characters. Each column i has a certain width w_i which is equal to the width of the longest entry in that column. Between each pair of columns there is a certain amount of space s. The total width of all columns including the space between cannot be larger than the width of the terminal (w₁ + w₂ + … + w_c + (c - 1) · s ≤ m). Each column shall contain ⌈n / c⌉ strings, except when n is not evenly dividable by c, in which case the last few columns shall be shorter by one entry or only the last column shall either be shorter depending on whether the strings are arranged across or down.

是否有一个有效的（比如 0 的（ñ·W 的），其中的 W = 的最大值（是W <子> 1 < /分>，W ₂ ，...，W <子> N 的））算法计算出列的最大量，我可以融入的 C 的列，如果...

Is there an efficient (e.g. O(n·w) where w = max(w₁, w₂, …, w_n)) algorithm to figure out the maximal amount of columns that I can fit into c columns, if...

• 的字符串跨过

• the strings are arranged across

string1 string2  string3 string4
string5 string6  string7 string8
string9 string10

弦被安排下来

the strings are arranged down

string1 string4 string7 string10
string2 string5 string8
string3 string6 string9

我发现的取值的无所谓。这个问题的每一个实例，其中的 S> 0 的可以通过的取值字符，也扩大翻译成一个实例，其中的 S = 0 的该终端由宽度的取值的字符，以补偿额外的取值的屏幕的末端字符。

I found out that s doesn't matter. Each instance of the problem where s > 0 can be translated into an instance where s = 0 by expanding each string by s characters and also expanding the width of the terminal by s characters to compensate for the extra s characters at the end of the screen.

推荐答案

不幸的是，我认为最快的算法，你可以是O（n ^ 2）。这是因为，你可以决定是否配置有可能在列表中的单一套印C列，但你无法知道被多少变动c所以基本上你只需要尝试不同的值了。在大部分的算法将做到这一点n次。

Unfortunately I think the fastest algorithm you can have is O(n^2). This is because you can determine if a configuration is possible for c columns in a single pass of the list but you can't know by how much to change c so basically you'll just have to try a different value for it. At most your algorithm will do this n times.

这是伪$ C $下我会怎么办呢

This is pseudo-code for how I would do it

for c = n.size, c > 0, c --
  remainingDist = m - c*s
  for i = 1, i <= c, i ++ 
    columnWidth = 0
    for j = i, j <= n.size; j += c
      columnWidth = max(n[j], columnWidth)
    end
    remainingDist -= columnWidth
  end
  if remainingDist >= 0
    success
    columns = c
    break
  end
end

您可以通过跳跃的循环中途通过首先计算的项目的平均规模和图中的理想的列数从。

you could jump to midway through the loop by first computing an average size of the items and figure an "ideal" number of columns from that.

这篇关于如何有效地找到理想的列数的一定宽度的字符串？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！