基于Item关联的Person分组：生成Group列的技术需求

核心思路 #

你的需求本质是基于Item的共享关系构建Person的连通分组：

• 若两个Person共享至少一个Item，或拥有完全相同的Item集合，则归为同一组
• 无共享Item的Person分属不同组

可以用**并查集（Union-Find）**数据结构高效处理这种连通性问题，步骤如下：

1. 为每个Person建立其对应的Item集合映射
2. 遍历所有Item，将拥有该Item的所有Person进行合并（归为同一组）
3. 最后为每个Person分配对应的组ID

代码实现（Python + Pandas） #

import pandas as pd
from collections import defaultdict

class UnionFind:
    def __init__(self, elements):
        self.parent = {elem: elem for elem in elements}
    
    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

# 示例数据（以示例1为例）
data = pd.DataFrame({
    'Person': [1,1,2,2,3],
    'Item': ['a','b','a','b','a']
})

# 1. 构建Person到Item集合的映射
person_items = data.groupby('Person')['Item'].apply(set).to_dict()

# 2. 构建Item到Person列表的映射
item_persons = defaultdict(list)
for idx, row in data.iterrows():
    item_persons[row['Item']].append(row['Person'])

# 3. 初始化并查集
uf = UnionFind(data['Person'].unique())

# 4. 合并共享同一Item的Person
for item, persons in item_persons.items():
    if len(persons) >= 2:
        first_person = persons[0]
        for p in persons[1:]:
            uf.union(first_person, p)

# 5. 生成组ID：将根节点映射为组号
root_to_group = {}
current_group = 1
for person in data['Person'].unique():
    root = uf.find(person)
    if root not in root_to_group:
        root_to_group[root] = current_group
        current_group += 1

# 6. 为原数据添加Group列
data['Group'] = data['Person'].map(lambda x: root_to_group[uf.find(x)])

print(data)

验证示例结果 #

• 示例1运行后输出与你给出的表格完全一致：

• 示例2中，Person1、2、3无共享Item，因此会生成3个独立组，结果符合预期。
• 示例3中，Person1和2的Item集合完全相同，共享所有Item，因此会被合并为同一组，结果符合预期。

扩展说明 #

• 该方法支持大规模数据集，时间复杂度主要由并查集操作决定，接近O(n)
• 如果需要优先按"完全相同的Item集合"分组，可在合并前先将Item集合相同的Person提前合并：

  # 提前合并Item集合相同的Person
  item_set_to_persons = defaultdict(list)
  for person, items in person_items.items():
      # 将集合转为可哈希的元组作为键
      item_set_to_persons[tuple(sorted(items))].append(person)
  
  for persons in item_set_to_persons.values():
      if len(persons) >=2:
          first_p = persons[0]
          for p in persons[1:]:
              uf.union(first_p, p)
  

  这段代码需要放在步骤4之前，确保Item集合完全相同的Person先归为一组。

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