按重叠范围对行进行分组

我有一个数据框，其中left列是对象最左边的位置，并且right列是最右边的位置。如果对象重叠，或者它们重叠重叠的对象（递归地），我需要对它们进行分组。 因此，例如，如果这是我的数据框：

     left  right
0      0    4
1      5    8
2      10   13
3      3    7
4      12   19      
5      18   23
6      31   35

所以行0 and 3重叠 - 因此它们应该在同一组中，并且也在同一行1是重叠线3- 因此它加入了该组。

因此，对于这个例子，输出应该是这样的：

     left  right    group
0      0    4         0
1      5    8         0
2      10   13        1
3      3    7         0
4      12   19        1
5      18   23        1
6      31   35        2

我想过各种方向，但没有想通（没有丑陋的for）。 任何帮助将不胜感激！

我发现接受的解决方案（更新：现已删除）具有误导性，因为它无法推广到类似的情况。例如对于以下示例：

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

建议的聚合函数输出以下数据帧（请注意，18-23 应与 12-19 一起位于组 1 中）。

一种解决方案是使用以下方法（基于组合间隔的方法）由@CentAu 发布 https://stackoverflow.com/questions/15273693/python-union-of-multiple-ranges):

# Union intervals by @CentAu
from sympy import Interval, Union
def union(data):
    """ Union of a list of intervals e.g. [(1,2),(3,4)] """
    intervals = [Interval(begin, end) for (begin, end) in data]
    u = Union(*intervals)
    return [u] if isinstance(u, Interval) \
        else list(u.args)

# Create a list of intervals
df['left_right'] = df[['left', 'right']].apply(list, axis=1)
intervals = union(df.left_right)

# Add a group column
df['group'] = df['left'].apply(lambda x: [g for g,l in enumerate(intervals) if 
l.contains(x)][0])

...输出：