如何对DataFrame中存在递归重叠范围的行进行分组？

嘿，这个区间连通分组的问题我之前也碰到过，不用写繁琐嵌套for循环的话，有两种很优雅的实现思路，刚好匹配你的需求：

并查集是专门解决连通分量问题的数据结构，刚好适合把直接/间接重叠的区间归为同一组。核心思路是：给每个区间分配初始的“父节点”，然后把所有重叠的区间合并到同一个集合里，最后每个区间的根节点就代表它的组。

import pandas as pd

# 构造你的示例DataFrame
df = pd.DataFrame({
    'left': [0,5,10,3,12,18,31],
    'right': [4,8,13,7,19,23,35]
})

# 实现轻量的并查集类
class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))  # 每个元素初始父节点是自己
    
    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

# 初始化并查集，大小等于DataFrame的行数
uf = UnionFind(len(df))

# 遍历所有区间对，判断重叠就合并
for i in range(len(df)):
    for j in range(i+1, len(df)):
        # 区间重叠判断条件：A的左边界 <= B的右边界，且B的左边界 <= A的右边界
        if df.loc[i, 'left'] <= df.loc[j, 'right'] and df.loc[j, 'left'] <= df.loc[i, 'right']:
            uf.union(i, j)

# 给每行分配组号，再把组号映射为从0开始的连续整数
df['group'] = df.index.map(lambda x: uf.find(x))
group_id_mapping = {old_id: new_id for new_id, old_id in enumerate(sorted(df['group'].unique()))}
df['group'] = df['group'].map(group_id_mapping)

print(df)

这种方法逻辑直观，容易理解，适合中小规模的数据。如果你的数据量特别大（比如上万行），双重循环会有点慢，那可以试试下面的方法。

这个方法利用排序+一次遍历的方式，先合并所有连通的区间，再把原索引映射回对应的组号，时间复杂度是O(n log n)（主要来自排序），效率更高。

import pandas as pd

df = pd.DataFrame({
    'left': [0,5,10,3,12,18,31],
    'right': [4,8,13,7,19,23,35]
})

# 保留原索引，按左边界排序
sorted_df = df.reset_index().sort_values('left')

# 合并连通区间，记录每个组包含的原索引
groups = []
# 初始化第一个组
current_group = {
    'indices': [sorted_df.iloc[0]['index']],
    'max_right': sorted_df.iloc[0]['right']
}

# 遍历排序后的区间，合并连通的
for _, row in sorted_df.iloc[1:].iterrows():
    if row['left'] <= current_group['max_right']:
        # 当前区间和组内区间连通，加入组并更新组的最大右边界
        current_group['indices'].append(row['index'])
        current_group['max_right'] = max(current_group['max_right'], row['right'])
    else:
        # 不连通，把当前组存入列表，新建组
        groups.append(current_group)
        current_group = {
            'indices': [row['index']],
            'max_right': row['right']
        }
# 别忘了把最后一个组加进去
groups.append(current_group)

# 构建原索引到组号的映射
index_to_group = {}
for group_id, group in enumerate(groups):
    for idx in group['indices']:
        index_to_group[idx] = group_id

# 给原DataFrame添加组号
df['group'] = df.index.map(index_to_group)

print(df)

这个方法不需要嵌套循环，只需要一次线性遍历，处理大数据量时优势很明显，而且输出的组号天然就是从0开始的连续整数，不需要额外映射。

两种方法都能得到你想要的结果，你可以根据自己的数据规模选合适的~

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