将按字母顺序排列的列表拆分为相等块

我的任务是将名称目录拆分为四个（近似）相等的块。该目录实际上是一个已经alphebatised的电话簿。解决方案必须是通用的，并且适用于任何目录，而不仅仅是一个特定目录。如果它帮助目录是一个字符串数组。将按字母顺序排列的列表拆分为相等块

例如四大块为一个目录可能是：

A-E, F-L, M-S and T-Z

而另一个可能是

A-B, C-D, E-F and G-Z

我已经考虑刚刚分裂4目录的大小，然后计数直到达到这个数字，并注意到入口开始的字母，但这不是特别优雅。

我的意思是：将目录设为100个条目。我可以将它除以4得到25（每个块应该有多少条目）。通过条目到25，然后采取该条目应该给我在第一个块的最后一项。但是，如果字母表中每个字母的条目数量差别很大，则这不起作用。 A-J都可以有一个条目，K可以有32个条目，这会使我的过程无用。

有伪代码而不是特定的C实现将是有帮助的，但真正在正确的方向上的一个点将是一个很大的帮助。

来源

2015-06-30 mforrest

这不是一个C-相关的问题，而是你所要求的我们给你的算法？ – Eregrith

@Eregrith我会在C中这样做，但我提到了伪代码，因为我认为它对我来说实际上知道发生了什么会更有用，而不仅仅是复制和破解别人的实现。 – mforrest

该目录已经排序。这样你就可以轻松地将它们分为四个如果考虑额外的字母作为键，如（A-AE，AF-AZ等）的基本思想是

Store中的一些数据结构词典（说阵列）在排序顺序
现在将数组的长度除以4，并分别制作四个索引。
在每个索引处检查带有上一个索引词的字母。
- 如果第一个索引词是“Abandon”并且第二个索引词是“Ascension” 那么第一个键将是“Ab”，第二个索引词将是“As”。
- 因此，范围内的所有单词（Ab-As）将出现在按键之间。
- 如果前两个字母与你所期望的字典部分分布相同，那么请为该密钥另外写一个字母。（如阿坝 - 阿布斯）

来源

2015-06-30 10:45:33

感谢您的回答，我试图通过坚持单个字符范围尽可能简化为最终用户，但如果我不能得到这个工作，我会看看使用您的方法肯定：） – mforrest

这是三个变量的优化问题;四大块之间的界限。如果我们表示边界X，ÿ，ž与块半开区间A - X，XY，YZ，ž - Z那么只会进一步约束是x < = y < = z，给出3276个可能性为x，y，z这就是无足轻重的搜索。

然后，您只需要一种方法来评估一种配置比另一种更好或更差;我建议使用平方和的误差例如对于块长度20, 26, 32, 24，平方误差为(20-25)^2 + (26-25)^2 + (32-25)^2 + (24-25)^2 = 76。

把这个放在一起，你可以使用嵌套循环写穷举搜索：

best, best_error = Nothing, +Inf 
for A <= x <= Z: 
    for x <= y <= Z: 
     for y <= z <= Z: 
      error = (sum(lengths[i] for A < i <= x) - 25)^2 
        + (sum(lengths[i] for x < i <= y) - 25)^2 
        + (sum(lengths[i] for y < i <= z) - 25)^2 
        + (sum(lengths[i] for z < i <= Z) - 25)^2 
      if error < best_error: 
       best, best_error = (x, y, z), error

来源

2015-06-30 10:46:53 ecatmur

我主要了解你的建议，看起来它可能是一个好方法。但是，我在你的实现中对for循环有些困惑。如果你能更详细地解释它们，我将非常感激。 – mforrest

@mforrest很好，这是一个详尽的搜索，所以* x *的范围可以从'A'到'Z'的任何地方。假设，* y *可以从* x *到'Z'和* z *中的任意位置，从* y *到'Z'的任意位置。嵌套for循环是它的自然表示。 – ecatmur

好的，这是有道理的。我来自Java背景，我正在努力按原样实现您的解决方案。这是伪代码还是工作实现？对于A <= X <= Z'和'sum（长度[i]为A mforrest

将按字母顺序排列的列表拆分为相等块

回答

相关问题