Python：在遍历范围时将范围添加到范围列表

Question

我遇到了一个问题，希望有人能给我一个提示来解决它。

我有一个 2D-python-列表（83 行和 3 列）。前两列是间隔的开始和结束位置。第三列是数字索引（例如：9.68）。该列表按第 3 列反向排序。我想得到索引最高的所有非重叠区间。

这是排序列表的示例：

504 789 9.68
503 784 9.14
505 791 8.78
499 798 8.73
1024 1257 7.52
1027 1305 7.33
507 847 5.86

这是我尝试过的：

# Define a function that test if 2 intervals overlap
def overlap(start1, end1, start2, end2):
        return not (end1 < start2 or end2 < start1)

best_list = [] # Create a list that will store the best intervals
best_list.append([sort[0][0],sort[0][1]]) # Append the first interval of the sorted list
# Loop through the sorted list
for line in sort:
    local_start, local_end = line.rsplit("\s",1)[0].split()
    for i in range(len(best_list)):
        best_start = best_list[i][0]
        best_end = best_list[i][1]
        test = overlap(int(best_start), int(best_end), int(local_start), int(local_end))
        if test is False:
            best_list.append([local_start, local_end])

我得到：

best_list = [(504, 789),(1024, 1257),(1027, 1305)]

但我想要：

best_list = [(504, 789),(1024, 1257)]

谢谢！

Answer 1

嗯，我对你的代码有一些疑问。由于 sort 包含字符串，那么这一行 append([sort[0][0],sort[0][1]]) 会做什么？

无论如何，对于主要部分，您的问题是，当您的列表中存在多个元素时，只需其中一个元素通过重叠测试即可添加到列表中（不是您想要的）。例如。当 (504, 789),(1024, 1257) 都存在时，(1027, 1305) 将被插入到列表中，因为它在与 (504, 789).

进行比较时通过了测试

所以，我做了一些更改，现在它似乎按预期工作了：

best_list = [] # Create a list that will store the best intervals
best_list.append(sort[0].rsplit(" ", 1)[0].split()) # Append the first interval of the sorted list
# Loop through the sorted list
for line in sort:
    local_start, local_end = line.rsplit("\s", 1)[0].split()
    flag = False # <- flag to check the overall overlapping
    for i in range(len(best_list)):
        best_start = best_list[i][0]
        best_end = best_list[i][1]
        test = overlap(int(best_start), int(best_end), int(local_start), int(local_end))
        print(test)
        if test:
            flag = False
            break
        flag = True
    if flag:
        best_list.append([local_start, local_end])

主要思想是检查每个元素，如果它通过所有重叠测试则添加它（我的代码代码的最后一行）。之前没有。

Answer 2

假设您解析了您的 csv 并且已经有了一个 [(start, stop, index), ....] 作为 [(int, int, float), ...] 的列表，那么您可以按以下方式对它进行排序：

from operator import itemgetter
data = sorted(data, key=itemgetter(2), reverse=True)

这意味着您按第三个位置排序，return结果按从大到小的倒序排列。

def nonoverlap(data):
    result = [data[0]]
    for cand in data[1:]:
        start, stop, _ = cand
        current_span = range(start, stop+1)
        for item in result:
            i, j, _ = item
            span = range(i, j+1)
            if (start in span) or (stop in span):
                break
            elif (i in current_span) or (j in current_span):
                break
        else:
            result.append(cand)
    return result

那么通过上面的函数你就可以得到想要的结果了。对于提供的片段，您将获得 [(504, 789, 9.68), (1024, 1257, 7.52)]。我在这里使用的事实是，您可以使用 1 in range(0, 10)，这将 return True。虽然这是一个天真的实现，但您可以将其用作起点。如果您只想 return starts 和 stops 将 return 行替换为 return [i[:2] for i in result].

注意：另外我想补充一点，你的代码有逻辑错误。你在每次比较后做出决定，但必须在与你的 best_list 中已经存在的所有元素进行比较后做出决定。这就是为什么 (504, 789) 和 (1027, 1305) 通过了你的测试，但不应该。希望这篇笔记对你有所帮助。

Python：在遍历范围时将范围添加到范围列表

Python: add ranges to a list of range while iterating over it

python

list

range

intervals

overlap