algorithm - 将组分成几乎相等的堆栈

我有一个文档列表，我想在网页上按名称的第一个字母分组显示它们，分为三列。

简而言之，是这样的:

A | C | E
A | D | F
B | D | F
B | D | F
  | D |

与 Windows 资源管理器 View 样式的一个重要区别是，我希望字母彼此保持一致。没有打破中组。为了适应这一点，我不在乎一列是否有两个太高的条目。

我首先按名称对文档数组进行排序，然后将它们拆分为嵌套数组。所以我知道(或者很容易找到):

有多少个不同的字母

每组有多少个字母

总共有多少条目

每列中应该有多少个值的平均平均值(理想但不是必需的)

我不在乎你的答案是什么。我在寻找算法而不是实现，这样你就可以用你喜欢的任何东西编码(除了 Fortran)。 HTML 中的解释也可能是一个难题。

我邀请某人在标签上疯狂，因为我想不出任何相关的东西，不，这不是家庭作业，所以请不要这样标记。

最佳答案

如果您这样看问题，也许会有所帮助:

对于您的示例，您有一个这样的字符串:

AA BB C DDDD E FFF

空格位置是您可以开始新列的位置。在其他任何地方，您都不得在同一列中保留相同的字母。
所以你实际上可以像这样标记空间位置:

AA1BB2C3DDDD4E5FFF

现在您有 5 个位置，您可以在其中中断列或不中断列，因为这是一个二元决策，为此使用一串 0 和 1 并暴力破解每种可能的组合:

12345

00000 -> no break at all, column count = 1, max. lines = 13
...
01010 -> your example, column count = 3, max. lines = 5
...
11111 -> breaks everywhere, column count = 6, max. lines = 4

这是一个蛮力尝试，但您可以很容易地看到 1 的计数影响列计数(列计数 = 1 的数量 + 1)，并且您希望最小化最大值。行，这应该可以以某种方式计算而无需测试每个组合。

EDIT2:没有意识到你想要 3 列，这使得它更容易，因为你知道你只有 3 个 1，但它仍然是蛮力。

编辑:我喜欢的另一种方法:

像这样写信计数:

A B C D E F
2 2 1 4 1 3

您现在可以连接彼此相邻的字母。始终选择计数总和最低的两个字母:

2 2 1 4 1 3 - lowest = "2 1"
2  3  4 1 3 - lowest = "1 3"
2  3  4  4  - lowest = "2 3"
  5   4  4  - stop now, as we have 3 columns now

Result: AABBC, DDDD, EFFF

这可能不会导致最佳解决方案，但我认为这是解决您的问题的一种很好且简单的方法。

关于algorithm - 将组分成几乎相等的堆栈，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/634450/