将群组分成几乎相等的堆栈

Question

将群组分成几乎相等的堆栈

4

我有一份文档清单，想要在网页上按照名称首字母分组显示它们，并排成三列。

简而言之，就是像这样：

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

与Windows资源管理器视图样式不同的一个重要差别是我希望字母保持在一起，不要在组内中间断开。为了满足这一点，我不介意一个列高度多出几个条目。

我首先通过名称对文档数组进行排序并将它们拆分成嵌套数组。因此，我知道（或可以轻松找到）：

- 有多少个唯一的字母 - 每个组中有多少个字母 - 总共有多少条目 - 每列应该有多少值的平均值（理论上而非必须）

我不关心你的答案是什么形式的。我寻求的是算法而不是实现，所以你可以用任何你喜欢的编程语言（除Fortran之外）。HTML解释可能有些困难。

我邀请有兴趣的人疯狂使用标签，因为我想不到任何相关的标签。不，这不是作业，请不要把它标记为作业。

- Oli

7个回答

3

你可以预期每列都会有一些额外的行。我的意思是，如果你有2个A，2个B和33个C，那么第三列将与其他列相比相当高。

这不是背包问题，因为它们必须按顺序排列。

你可以这样做：

计算项目数量。
查看第三个部分将出现在哪里。
如果它恰好是一个字母更改的位置，则你很幸运：）
如果不是，则最小化第三个部分拆分点与前一个/后一个字母更改点之间的距离 - 即，如果有一个字母更改2个条目之前和10个条目之后，则选择前一个。
最后，取剩下的部分，除以二，然后按照相同的逻辑尽可能靠近平均值进行拆分。

- SebaGR

更像是一种打包问题，它是背包问题的一个派生，它们都属于组合数学（或者你称之为那个名字）。 - leppie

3

给定您的约束条件，这个问题没有通用解决方案，除非输入也有限制。例如，考虑一个仅包含以字母A、B、C、E和F开头的单个文档和15（或一百万）个以D开头的文档的集合。为了将所有的D分组在一列中，该列的长度必须至少为15。如果使用超过两列，则最好的情况是第一列的长度为3，第二列的长度为15（或一百万），第三列的长度为2。这违反了您的“在几个条目内”的约束。

您需要决定，在列不中断字母的约束条件下，是否重要到值得容忍列大小之间的潜在巨大差异，或者输入受到限制，使得问题可能可通过给定的约束条件解决。就我个人而言，我会重新思考界面，因为解决一个优化问题只为保持字母在一起似乎过于复杂。

- tvanfosson

0

这个问题适合使用递归解决——可能是经典的动态规划，尽管我还没有完全解决它。

你有固定数量的潜在分割点和一定数量的分割要做。你应该能够得到类似以下的东西：

(splits, max_ht, min_ht) = split_list(list, requested_splits, 
                                      curr_max, curr_min)

该函数应迭代潜在的分割点，并在列表的其余部分上递归调用自身（请求的分割减少一个）。例如：

def split_list(list, requested_splits, curr_max, curr_min):
    best_splits = []
    best_split_len = curr_max-curr_min
    best_max = curr_max
    best_min = curr_min

    if requested_splits == 0:
        return (best_splits, curr_max, curr_min)
    for candidate in candidate_split_points:
        this_max = max(curr_max, len(<list up to split point>)
        this_min = min(curr_min, len(<list up to split point>)
        (splits, new_max, new_min) = split_list(<list after split point>,
                                                requested_splits-1,
                                                this_max, this_min)
        if (new_max-new_min) < best_split_len:
            best_split_len = new_max - new_min
            best_max = new_max
            best_min = new_min
            best_splits = [candidate] + splits
    return (best_splits, best_max, best_min)

- zweiterlinde

0

我认为你应该从定义一种“度量”开始，它将告诉你哪种布局是最好的，例如对所有列取（平均大小-实际大小（列））^2 的总和。然后，因为你总是有3列（是吗？），所以找到所有可能的分割并找到最大化你的度量的那个应该是相当快的。

- Grzenio

0

首先，遍历文档以构建字母->计数元组的数组。

第一个条目是（数组中的第一个字母）->文档0

然后通过遍历数组找到应出现在第二列和第三列中的条目，将计数相加，但在接近第2列和第3列的阈值时停止（这是总计数的1/3和2/3）。

- Denis Hennessy

0

这里有一个你可以尝试的方法。既然你知道你理想的列数（n），那么一开始把所有元素都放在第一列。

重复下面的步骤，直到满意为止...... 这是一个迭代算法，所以在前几次迭代中结果会很快变好，然后收益就开始减少了。

按顺序遍历各列。

让当前列中的项数为numCurrent。

如果numCurrent < n，则跳过此列。

追踪以当前列的第一个字母（groupFirst）和最后一个字母（groupLast）开头的元素。

计算前一列（如果存在）的项目数（numPrev）。如果abs（n-numCurrent）> abs（n-numPrev+groupFirst），则将groupFirst移动到前一列。

重新计算numCurrent。

像之前一样，如果有下一列，则如果abs（n-numCurrent）> abs（n-numNext+groupLast），则将groupLast移入下一列。

反复操作。洗涤次数越多，效果应该越好。会有一个点，在该点上不再可能进行更多的更改，也有一些点可以继续进行下去。您决定进行多少次迭代。

- Sudhir Jonathan

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- schnaader · Accepted Answer

也许从这个角度来看问题会更容易理解：

以你的例子为例，你有一个像这样的字符串：

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

这可能不会导致最优的解决方案，但我认为这是一种简单易行的方法来解决你的问题。