Skip to main content
 首页 » 编程设计

python之如何将 "union"重叠范围转为非重叠范围

2024年12月31日11fff_TT

问题: 任何人都可以建议更好或更 pythonic 的方法,将重叠范围对减少为非重叠范围对吗?

背景: 我有一个代表开始和结束对的元组列表。我试图从根本上完成所有开始结束对的联合。输入起始端对具有重叠值,输出应表示没有任何重叠的输入起始端对。

下面的代码很接近但错误,因为它输出了输入中没有的额外范围(我也意识到它不是很好,为什么它是错误的)。谁能提出更好的方法或我忽略的一些内置功能?

为基本问题道歉。 感谢您的帮助!

##create example data 
pairA =[(0,5),(10,12)] 
pairB =[(1,2),(11,15)] 
pairC =[(1,4),(10,12),(15,17)] 
 
#combine the lists to one list 
#ultimately may have n number of lists and felt it would be easier to 
merged = pairA + pairB +pairC 
# produce union of list * unpacks the arguments of a list 
listUnion= sorted(set().union(*merged)) 
 
#this is the piece of code I am looking at improving 
#it creates new start end pairs based on the union 
lastElement =listUnion[-1] 
outList=[] 
 
for item in listUnion: 
    #create start end pair from value i and i+1 
    if item != lastElement: 
        outList.append((item,listUnion[listUnion.index(item)+1])) 
    else: 
        #last element of the list, becomes the last element of list pair 
        #it can be ignored 
        pass 
print outList  
"""output: [(0, 1), (1, 2), (2,4), (4, 5), (5, 10), (10, 11), (11, 12), (12, 15), (15,  
17)] 
correct output: would not have (5,10) as there is no overlap here in the input """ 

编辑:添加了这个问题的可视化表示

请您参考如下方法:

这是一个解决方案。它可能不是很 pythonic,因为我使用 Python 的经验非常有限,但它确实有效。

pairs_a = [(0, 5), (10, 12)] 
pairs_b = [(1, 2), (11, 15)] 
pairs_c = [(1, 4), (10, 12), (15, 17)] 
 
merged = pairs_a + pairs_b + pairs_c 
merged.sort() 
 
set_list = [] 
cur_set = set() 
cur_max = merged[0][1] 
for pair in merged: 
    p0, p1 = pair 
    if cur_max < p0: 
        set_list.append(cur_set) 
        cur_set = set() 
    cur_set.add(p0) 
    cur_set.add(p1) 
    if cur_max < p1: 
        cur_max = p1 
set_list.append(cur_set) 
 
out_list = [] 
for my_set in set_list: 
    my_list = sorted(my_set) 
    p0 = my_list[0] 
    for p1 in my_list[1:]: 
        out_list.append((p0, p1)) 
        p0 = p1 
 
# more pythonic but less readable in spite of indentation efforts: 
# out_list = [pair 
#             for zipped in [zip(list[:-1], list[1:]) 
#                            for list in [sorted(set) 
#                                         for set in set_list]] 
#                 for pair in zipped] 
 
# alternate ending: 
# out_list = [sorted(set) for set in set_list] 
 
print(out_list) 

想法是先按第一项对所有范围对进行排序。这就是 merged.sort() 所做的(它使用连续的元组成员来消除歧义,但这在这里并不重要)。然后我们遍历排序的范围对,只要我们在一堆重叠范围内,我们就将所有开始和结束添加到当前集合。为了知道束何时结束,我们保留所有范围结束的最大值。一旦超出此最大值的范围开始到达,我们就会通过将其附加到列表来存储当前集合,并开始一个新集合。最后一组必须在循环后添加到列表中。现在我们有了一个集合列表,我们可以轻松地将其转换为列表列表或对列表。