python - 插入/删除列表之间的距离

Question

给定两个长度相同的 1 和 0 列表 A 和 B，我想确定是否有某种方法可以将 n 个 1 或 0 恰好插入 A 并恰好将 n 个 1 或 0 插入 B 以使它们相同列表。 n 将始终小于列表的长度。

例如，设置 n = 2。让 A = [0,0,1,1,0,0] 和 B = [0,1,0,1,0 ,1]。我们可以通过插入一个 1 和一个 0 将 A 转换为 [0,1,0,1,0,1,0,0]。通过在右手端。

有没有已知的方法来计算这样的函数

def match(A,B,n):
    return True if A and B are exactly insertion distance n from a common list   

?

Answer 1

算法

您可以通过修改 standard edit distance algorithm 来解决这个问题找到使两个字符串相同的最小插入次数 (x)。

当且仅当 x<=2*n 时，你的问题是可解的。

Python代码:

A = [0,0,1,1,0,0]
B = [0,1,0,1,0,1]

def match(A,B,n):
    r = len(A)
    if r != len(B):
        return False
    DP = [ [0]*(r+1) for i in range(r+1) ]
    # DP[a][b] is min insertions to A to turn A[:a] and B[:b] into the same string
    for b in range(r+1):
        for a in range(r+1):
            if a>0 and b>0:
                best = DP[a-1][b-1]
                if A[a-1]!=B[b-1]:
                    best += 2 # inserting into both
            elif a==0 and b==0:
                best = 0
            else:
                best = 2*n+1

            if a>0:
                best = min(best,1+DP[a-1][b]) # inserting into A
            if b>0:
                best = min(best,1+DP[a][b-1]) # inserting into B
            DP[a][b] = best
    x = DP[r][r] # we have needed to make x insertions to get A and B to match
    # A and B are now the same length, so we must have made x/2 insertions to each
    return x<=2*n

print match(A,B,2)

解释

在您的例子中，您需要向 A 添加一个 1 和一个 0，向 B 添加两个 0，因此 x(插入的总数)将为 4。

请注意，您可能担心该算法不会为两个字符串提供相同数量的插入。例如，它可能会找到一个解决方案，将 3 个字符添加到 A，将 1 个字符添加到 B。但是，这不是解决方案，因为这样字符串将变得不同长度。

如果事实证明 x 小于 2*n，您可以简单地用相同的字符填充两个字符串，直到您设法向每个字符串添加恰好 n 个字符。