将组分成几乎相等的堆栈

Question

我有一个文档列表,我想在网页上显示按名称的第一个字母分组的三个列.

简而言之,这样的事情:

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

与Windows资源管理器视图风格的一个重要区别在于我希望字母相互保持一致.没有打破中间组.为了适应这种情况,我不在乎一列是否有一些条目太高.

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

• 有多少独特的字母
• 每组中有多少个字母
• 总共有多少条目
• 每列中应该有多少个值的平均值(理想情况但不是必须的)

我不关心你的答案是什么.我正在寻找算法而不是实现,所以你可以编写你喜欢的任何东西(除了Fortran).HTML中的解释也可能是一个棘手的问题.

我邀请有人在标签上疯狂,因为我想不出任何相关和不,这不是作业,所以请不要这样标记.

Answer 1

也许如果你看看这样的问题会有所帮助:

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

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),并且您希望最小化最大值.线,这应该可以以某种方式计算,而无需测试每个组合.

编辑2:没有认识到你想要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

这可能不会导致最佳解决方案,但我认为这是一种解决问题的好方法.