如何获取尊重所有已有划分的最粗集合划分？

问题本质 #

你需要找的是多个集合划分的最粗公共加细划分：该划分必须是每个输入划分的加细（即满足题目中的“尊重”规则——若元素在任意输入划分中不同组，则在最终划分中也不同组），同时是所有符合条件的划分中子集数量最少的（最粗的）。

核心判定规则：两个元素最终同组，当且仅当它们在每一个输入划分中都属于同一个子集。

实现方法 #

方法1：特征向量分组法 #

这是最直观的实现方式，适合小规模集合：

1. 为每个输入划分的每个子集分配唯一标识（比如用子集内的首个元素、哈希值或自增ID）。
2. 为每个元素生成特征元组：元组的第i项是该元素在第i个输入划分中所属子集的标识。
3. 将特征元组完全相同的元素归为一组，每组就是最终划分的一个子集。

示例验证

以题目中的案例为例：

• 集合：{1,2,3,4,5,6}
• Partition1：{{1,2,3}, {4,5,6}} → 子集标识分别设为P1_0、P1_1
• Partition2：{{1,2}, {3,4}, {5,6}} → 子集标识分别设为P2_0、P2_1、P2_2
• 各元素特征元组：
  • 1: (P1_0, P2_0)
  • 2: (P1_0, P2_0)
  • 3: (P1_0, P2_1)
  • 4: (P1_1, P2_1)
  • 5: (P1_1, P2_2)
  • 6: (P1_1, P2_2)
• 分组结果：{{1,2}, {3}, {4}, {5,6}}，完全符合要求。

方法2：并查集（Union-Find）法 #

适合元素数量较多的场景，时间复杂度接近线性：

1. 初始化并查集，每个元素单独构成一个集合。
2. 为每个输入划分建立元素→子集标识的映射表。
3. 创建一个辅助字典，键为特征元组，值为该元组对应的首个元素（作为连通分量的代表）。
4. 遍历每个元素：
   • 生成其特征元组。
   • 若元组未在字典中，将该元素存入字典（值为自身）。
   • 若元组已存在，将当前元素与字典中对应的代表元素合并。
5. 遍历结束后，并查集中的每个连通分量即为最终划分的子集。

总结 #

这个问题对应格论中**划分的交（Meet）**操作，上述两种方法都能高效解决需求：特征向量法简单直观，适合小规模场景；并查集法性能更优，适合大规模集合处理。

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