python - 通过组合列表中的元组子集来获得满足位置标准的所有元组序列

Question

我有一个元组列表，每个元组包含以下信息:

(start_position,end_position,list of strings)

示例列表如下:

aList = [(6, 9, ['ataH']), 
(4, 9, ['svataH']), 
(0, 9, ['vEvasvataH']), 
(2, 5, ['vasu', 'vasU']), 
(1, 3, ['Eva', 'eva']), 
(0, 1, ['vA', 'vE'])]

我需要找到所有元组序列，这样每个序列都必须覆盖 start_position 中的所有位置至 end_position , 在这种情况下来自 0至 9 .在一个序列中，说 a , 相邻元组需要满足 a[i+1][0] - a[i][1] <= 1 的约束.

总的来说，输出应该如下:

[[(0, 1, ['vA', 'vE']), (2,5,['vasu', 'vasU']), (6, 9, ['ataH'])  ],
 [(0, 1, ['vA', 'vE']), (1, 3, ['Eva', 'eva']), (4, 9, ['svataH'])],
 [(0, 9, ['vEvasvataH'], [7])]]

我已经使用下面的代码来实现相同的目的。

maxVal = max(aList,key=lambda item:item[1])[1]
diffSets = list()

for i,item in enumerate(aList):
    if maxVal == item[1]:  
        _temp = [item]        
        currStart = item[0]
        for j,stuff in enumerate(aList):
            if i != j:
                if currStart == stuff[1] or currStart == stuff[1]+1:                    
                    _temp.append(stuff)
                    currStart = stuff[0]        
        diffSets.append(_temp) #the output needs to be reversed to get the sequence in the order as shown above

是否有更有效和更快速的方法来实现相同的目标，比如使用 itertools ？

Answer 1

以下是我的处理方式(并不是说它一定会更快)。首先，您可以根据开始和结束对数据进行排序。这意味着当我们稍后查看组合时，我们不必回溯到结果中的其他值(我们将知道 entry[i] 的开始必须小于或等于开始条目[i+1])

import itertools
import operator

data = [
    (6, 9, ['ataH']),
    (4, 9, ['svataH']),
    (0, 9, ['vEvasvataH']),
    (2, 5, ['vasu', 'vasU']),
    (1, 3, ['Eva', 'eva']),
    (0, 1, ['vA', 'vE'])
]

data = sorted(data, key=operator.itemgetter(0, 1))
start = min(data, key=operator.itemgetter(0))[0]
end = max(data, key=operator.itemgetter(1))[1]

现在我们已经对数据进行了排序，并且知道了我们的开始值和结束值。

要找到任意大小子集的所有数据组合，我们可以使用这个技巧:https://stackoverflow.com/a/5898031/3280538

def all_combinations(data):
    for i in range(len(data)):
        yield from itertools.combinations(data, r=i+1)

这里我们使用 yield 来避免创建昂贵的容器。现在我们编写另一个使用这些组合的方法，并为每个组合检查它的有效性:

def valid_combinations(data):
    for comb in all_combinations(data):
        if comb[0][0] != start or comb[-1][1] != end:
            continue
    
        for i in range(len(comb) - 1):
            if not 0 <= comb[i+1][0] - comb[i][1] <= 1:
                break
        else:
            yield comb

在这里，我使用了一个巧妙的 for 循环技巧。循环中的 else block 只有在 for 循环自然完成且没有中断时才会执行，如果我们没有中断，那么我们就知道每个项目都是有效的。

一起:

import itertools
import operator


def all_combinations(data):
    for i in range(len(data)):
        yield from itertools.combinations(data, r=i+1)


def valid_combinations(data):
    data = sorted(data, key=operator.itemgetter(0, 1))
    start = min(data, key=operator.itemgetter(0))[0]
    end = max(data, key=operator.itemgetter(1))[1]

    for comb in all_combinations(data):
        if comb[0][0] != start or comb[-1][1] != end:
            continue

        for i in range(len(comb) - 1):
            if not 0 <= comb[i+1][0] - comb[i][1] <= 1:
                break
        else:
            yield comb

获取结果:

from pprint import pprint
pprint(list(valid_combinations(
    [
        (6, 9, ['ataH']),
        (4, 9, ['svataH']),
        (0, 9, ['vEvasvataH']),
        (2, 5, ['vasu', 'vasU']),
        (1, 3, ['Eva', 'eva']),
        (0, 1, ['vA', 'vE'])
    ]
)))

[((0, 9, ['vEvasvataH']),),
 ((0, 1, ['vA', 'vE']), (1, 3, ['Eva', 'eva']), (4, 9, ['svataH'])),
 ((0, 1, ['vA', 'vE']), (2, 5, ['vasu', 'vasU']), (6, 9, ['ataH']))]