给定两个相同长度的二进制列表，如何找到与交替列表中的一个对应的所有索引对？

Question

假设您有两个长度相同的列表 L1 和 L2，每个列表只有 0 和 1 值。如何有效地找到所有索引对 [i, j] 使得：

i < j
L1[i] == 1 and L2[j] == 1
对于满足 i < k < j 的任何 k 我们有 L1[k] == 0 and L2[k] == 0

示例：

L1 = [1,0,0,0,1,0,0,1,0]
L2 = [0,0,1,0,0,1,0,0,1]

预期输出：

[[0, 2], [4, 5], [7, 8]]

我的以下代码有效，但对于大型计算来说它非常慢。我正在寻找更快的解决方案。

import math

def getNext(ind,i):
    nextList = [idx for idx,x in enumerate(ind) if (x and idx>i)]
    if nextList:
        return min(nextList)
    else:
        return math.inf
    
def getPrevious(ind,i):
    previousList = [idx for idx,x in enumerate(ind) if (x and idx<i)]
    if previousList:
        return max(previousList)
    else:
        return -math.inf

def getIndices(list1,list2):
    indices = [[i,j] for i,x in enumerate(list1) 
                     for j,y in enumerate(list2)
                     if x and y and i<j and getNext(list1,i,'true') >= j
                        and getPrevious(list2,j,'true') <= i
              ] 
    return indices

Answer 1

你可以试试带生成器的版本：

L1 = [1, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0]
L2 = [0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1]


from itertools import count


def get_pairs(L1, L2):
    c = count(1)
    L2, L1 = zip(
        *[
            (next(c) if i == 1 else 0, next(c) if j == 1 else 0)
            for i, j in zip(L2, L1)
        ]
    )

    i1 = ((i, v) for i, v in enumerate(L1) if v != 0)
    i2 = ((i, v) for i, v in enumerate(L2) if v != 0)

    try:
        (idx1, v1), (idx2, v2) = next(i1), next(i2)
        while True:
            while v1 - v2 != -1:
                if idx1 < idx2:
                    idx1, v1 = next(i1)
                else:
                    idx2, v2 = next(i2)
            yield idx1, idx2
            idx1, v1 = next(i1)
    except StopIteration:
        pass


print(list(get_pairs(L1, L2)))

打印：

[(1, 3), (3, 4), (5, 7), (8, 10), (10, 11)]

Answer 2

您可以在执行单次迭代时跟踪第一个列表中引用 1 的 i。当您在此之后的下一次迭代中遇到另一个列表中的 1 时，您将有一个输出元组。每当你遇到这样的命中时，忘记 i（将其设置为 -1 或其他无效索引或 None）并继续：

def find_pairs(lst1, lst2):
    i = -1
    for j, (a, b) in enumerate(zip(lst1, lst2)):
        if b and i != -1: # End of a range
            yield i, j
            i = -1  # Invalidate starting index of range
        if a:  # Start a new range
            i = j

输入比您在问题中发布的更简单的调用示例：

lst1 = [1,1,0,1,1,1,0,0,1,0,1,0]
lst2 = [0,0,0,1,1,0,0,1,0,0,1,1]
print(list(find_pairs(lst1, lst2)))

输出：

[(1, 3), (3, 4), (5, 7), (8, 10), (10, 11)]

给定两个相同长度的二进制列表，如何找到与交替列表中的一个对应的所有索引对？

Given two binary lists of same length, how to find all the pair of indices corresponding to ones of alternating lists without ones in between?

python

binary

performance

function

list