gpt4 book ai didi

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

转载 作者:塔克拉玛干 更新时间:2023-11-03 04:47:35 27 4
gpt4 key购买 nike

给定两个长度相同的 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

?

最佳答案

算法

您可以通过修改 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 个字符。

关于python - 插入/删除列表之间的距离,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/18967316/

27 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com