将有序字母列表分割为N个均匀分组的算法方案

问题需求 #

现有长度为L、已按字母顺序排序的姓名列表，需将其分割为N个分组，要求优先级从高到低如下：

1. 按分组顺序读取时，必须保留字母排序
2. 首字母相同的所有姓名必须处于同一分组
3. 每个分组的规模应尽可能均匀

是否存在简洁可行的算法实现该需求？

示例 #

假设我们有30个姓名的列表，需分割为3个分组/行：

Abel Alex Amir Aria Axel Cali Enzo Evan Ezra Finn Hank Ivan Jade Jake Joel June Kane Lara Leon Levi Liam Luca Milo Nico Noah Remy Rory Sage Sean Theo

朴素实现的结果 #

一种朴素实现方式是遍历列表，尝试在接近位置10和20处分割，得到如下分组：

第一个分组可在第10个姓名后分割，但第二个分割点需保证所有首字母为'L'的5个姓名同组。由于位置20后有2个'L'开头的姓名，前面有3个，因此分割点选在'Luca'之后、'Milo'之前。不过这种方式的分组均匀性并非最优。

更优的分组结果 #

将'Hank'从第二组移到第一组后，分组分布更均匀：

局限性 #

存在无法同时满足所有要求的场景：例如当所有姓名首字母相同且N>1时，均匀性要求无法实现，此时第一组长度为L，其余组长度为0。

均匀性定义补充 #

有反馈指出均匀性要求不够明确，这里给出几个可量化的优化方向（以实现美观的展示效果为目标）：

• 最小化最大分组的长度
• 最小化最大分组与最小分组的长度差
• 以表格形式展示时，最小化空单元格数量

可行算法思路 #

以下是一种简洁的分步实现算法：

1. 预处理：按首字母聚类
   先将原有序列表按首字母拆分，得到若干个首字母块，每个块包含所有相同首字母的姓名，且块的顺序严格保持原列表的字母排序。比如示例中的首字母块为：[A组(5人), C组(1人), E组(3人), F组(1人), H组(1人), I组(1人), J组(4人), K组(1人), L组(5人), M组(1人), N组(2人), R组(2人), S组(3人), T组(1人)]

2. 计算目标分组规模
   计算理想的每组人数：target = L / N，同时记录每个首字母块的长度。

3. 贪心分配首字母块
   遍历所有首字母块，依次将块加入当前分组，直到当前分组的总人数加上下一个块的人数会严重偏离目标规模时，结束当前分组，开启新分组：

   • 维护当前分组的累计人数current_count，初始为0；
   • 对于每个首字母块block：
     • 如果current_count + len(block) <= ceil(target) 或者 current_count < floor(target)，则将该块加入当前分组，更新current_count；
     • 否则，将当前分组收尾，开启新分组，把该块加入新分组，重置current_count为len(block)；
   • 最后一个分组直接接收剩余所有块。

4. 微调优化（可选）
   如果分组后存在明显的不均匀，可尝试将末尾的小首字母块向前调整（前提是不打破首字母顺序和同首字母块不拆分的规则），比如示例中将H组从第二组移到第一组，让三组人数从10/12/8变为11/11/8，差距更小。

这种算法既严格满足前两个优先级要求，又能尽可能让分组均匀，实现逻辑简洁易懂。

内容的提问来源于stack exchange，提问作者Tomas Eklund