Skip to main content
 首页 » 编程设计

python之在数组中查找非交叉对并在 Python 中迭代删除直到没有对为止

2024年10月25日10jpfss

我有一个元组列表,包含数组中成对的开始和结束索引点。

(2,72), (20,73),(22,70), (25,30) 

我想提取一对,比如 A,这样数组中没有其他对在 A 的范围内有开始或结束索引。例如这里,我第一次提取 (25,30) 因为没有其他对的起点或终点在 25 到 30 范围内。一旦我提取它,我就剩下:

(2,72), (20,73),(22,70) 

然后我提取 (22,70),列表中包含:

(2,72), (20,73) 

无法进一步提取对,因为 (2,72) 中包含 20,而 (20,73) 中包含 72。

蛮力法:

  1. 假设 list_tuple 是一个元组列表
  2. 根据起始索引对 list_tuple 进行排序
  3. 从列表中提取一个元素
  4. 如果这个提取的元素满足条件,则检查所有其他对
    1. 如果没有移动到排序列表的下一个元素
    2. 如果条件为真,提取元素,更改列表并用这个新列表重复


Checklist=[(2,72), (20,73),(22,70), (25,30)] 
sortedlist=sorted(Checklist,key=itemgetter(0)) 
i=0 
NewList=list() 
len_sortedlist=len(sortedlist) 
while i< len_sortedlist: 
    condition=True 
    checkpair =sortedlist[i] 
    removelist=copy.deepcopy(sortedlist) 
    del removelist[i] 
    for pair in removelist:# check for every pair if it is within checked pair list 
        if pair[0] in range(checkpair[0],checkpair[1]) or pair[1] in range(checkpair[0],checkpair[1]) : 
            condition=False 
            i=i+1 
            break     
    if condition==True: 
        NewList.append(checkpair) 
        sortedlist.remove(checkpair) 
        sortedlist=sorted(sortedlist,key=itemgetter(1)) 
        i=0 
        len_sortedlist=len(sortedlist) 

我想知道是否有更好更有效的方法来做到这一点?

请您参考如下方法:

如何使用像 ifilter 这样的 itertools 函数呢? ?

>>> import itertools 
>>>  
>>> def check_element(checkpair): 
...     for pair in checklist: 
...         if  checkpair != pair and (pair[0] in range(checkpair[0],checkpair[1]) or pair[1] in range(checkpair[0],checkpair[1]) ): 
...             return bool 
...  
>>> checklist = [(2,72), (20,73),(22,70), (25,30)] 
>>> print checklist 
[(2, 72), (20, 73), (22, 70), (25, 30)] 
>>> filtered = itertools.ifilter(check_element, checklist) #returns generator 
>>> checklist = list(filtered)                             #exahust iterator to create list 
>>> print checklist 
[(2, 72), (20, 73), (22, 70)] 
>>> _filtered = itertools.ifilter(check_element, checklist) 
>>> checklist = list(_filtered) 
>>> print checklist 
[(2, 72), (20, 73)]