如何将存在重叠的购物物品分组为独立的新组？

你遇到的是典型的连通分量分组问题，不用纠结复杂的交叉连接或多层循环，用**Union-Find（并查集）**算法就能轻松搞定，这是专门处理这类"关联合并"场景的最优方案。

核心思路 #

每个顾客的购物列表里，所有物品都是互相关联的（比如买了A和B，就说明A和B属于同一组）；我们需要把所有有直接/间接关联的物品归为同一个独立组，本质就是找图中的连通分量。

具体步骤 #

1. 初始化并查集：把每个物品初始化为一个独立的集合。
2. 合并关联物品：遍历每个顾客的购物列表，将列表内的所有物品两两合并（或者逐个和列表第一个物品合并），建立关联关系。
3. 分组输出：最后把所有物品按它们的"根节点"（所属集合的标识）分组，每个组就是一个bag。

结合你的示例演示 #

• 初始状态：每个物品单独成集合 → {A}, {B}, {C}, {D}, {E}, {I}, {F}, {G}, {H}, {J}, {K}
• 处理顾客1的[B,A]：合并B和A → {A,B}, {C}, ...
• 处理顾客2的[C,A]：合并C和A → {A,B,C}, ...
• 处理顾客3的[E,I,D]：合并E、I、D → {E,I,D}, ...
• 处理顾客4的[F,G]：合并F和G → {F,G}, ...
• 处理顾客6的[F,H]：合并F和H → {F,G,H}, ...
• 处理顾客7的[J,A]：合并J和A → {A,B,C,J}, ...
• 处理顾客8的[K,J]：合并K和J → {A,B,C,J,K}, ...
• 最终分组：三个连通分量，对应你要的三个bag。

代码实现（Python示例） #

class UnionFind:
    def __init__(self):
        self.parent = {}
    
    # 查找根节点，带路径压缩优化
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    # 合并两个集合
    def union(self, x, y):
        x_root = self.find(x)
        y_root = self.find(y)
        if x_root != y_root:
            self.parent[y_root] = x_root

# 输入数据
customers = [
    [1, ['B', 'A']],
    [2, ['C', 'A']],
    [3, ['E', 'I', 'D']],
    [4, ['F', 'G']],
    [5, ['F']],
    [6, ['F', 'H']],
    [7, ['J', 'A']],
    [8, ['K', 'J']]
]

uf = UnionFind()

# 收集所有物品并初始化父节点
all_items = set()
for _, items in customers:
    all_items.update(items)
for item in all_items:
    uf.parent[item] = item

# 合并每个顾客的物品关联
for _, items in customers:
    if len(items) < 2:
        continue
    first_item = items[0]
    for item in items[1:]:
        uf.union(first_item, item)

# 按根节点分组
groups = {}
for item in all_items:
    root = uf.find(item)
    groups.setdefault(root, []).append(item)

# 整理成输出格式
print("| bag |          items |")
print("| ----| -------------- |")
for idx, items in enumerate(groups.values(), 1):
    print(f"| {idx:4d}| {str(sorted(items)):14s}|")

为什么之前的方法复杂？ #

你用的crossJoin、多层循环属于暴力遍历所有可能的关联，不仅效率低，还需要手动判断分组是否完成；而Union-Find通过树形结构管理集合，合并和查询操作都非常高效，能自动处理所有关联关系，完全不需要手动跟踪分组状态。

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