python - 如何对齐两个数字列表
问题描述
我有两个排序的数字列表，A并且至少B与. 说：BA
A = [1.1, 2.3, 5.6, 5.7, 10.1]
B = [0, 1.9, 2.4, 2.7, 8.4, 9.1, 10.7, 11.8]
我想将每个数字A与一个不同的数字相关联，B但保持顺序。对于任何此类映射，我们将总距离定义为映射数字之间的平方距离之和。
例如：
如果我们将 1.1 映射到 0 0 那么 2.3 可以映射到从 1.9 开始的任何数字。但是如果我们将 1.1 映射到 2.7，那么 2.3 只能映射到 B 中从 8.4 开始的数字。
假设我们映射 1.1->0、2.3->1.9、5.6->8.4、5.7->9.1、10.1->10.7。这是一个有效的映射，距离为 (1.1^2+0.4^2+2.8^2+3.4^2+0.6^2)。
显示贪婪方法的另一个示例将不起作用：
A = [1, 2]
B = [0, 1, 10000]
如果我们映射 1->1，那么我们必须映射 2->10000，这很糟糕。
任务是找到总距离最小的有效映射。
很难做到吗？当列表长度为几千时，我对一种快速的方法感兴趣。
解决方案
这是一个O(n)解决方案！（这是最初的尝试，固定版本见下文。）
思路如下。我们首先解决每个其他元素的问题，将其转化为非常接近的解决方案，然后使用动态规划找到真正的解决方案。这是先解决一半大小的问题，然后是O(n)工作。利用事实证明x + x/2 + x/4 + ... = 2x这是O(n)可行的。
这非常非常需要排序列表。做一个 5 跨的乐队是矫枉过正的，它看起来很像一个 3 跨的乐队总是给出正确的答案，但我没有足够的信心去做。
def improve_matching (list1, list2, matching):
# We do DP forward, trying a band that is 5 across, building up our
# answer as a linked list. If our answer changed by no more than 1
# anywhere, we are done. Else we recursively improve again.
best_j_last = -1
last = {-1: (0.0, None)}
for i in range(len(list1)):
best_j = None
best_cost = None
this = {}
for delta in (-2, 2, -1, 1, 0):
j = matching[i] + delta
# Bounds sanity checks.
if j < 0:
continue
elif len(list2) <= j:
continue
j_prev = best_j_last
if j <= j_prev:
if j-1 in last:
j_prev = j-1
else:
# Can't push back this far.
continue
cost = last[j_prev][0] + (list1[i] - list2[j])**2
this[j] = (cost, [j, last[j_prev][1]])
if (best_j is None) or cost <= best_cost:
best_j = j
best_cost = cost
best_j_last = best_j
last = this
(final_cost, linked_list) = last[best_j_last]
matching_rev = []
while linked_list is not None:
matching_rev.append( linked_list[0])
linked_list = linked_list[1]
matching_new = [x for x in reversed(matching_rev)]
for i in range(len(matching_new)):
if 1 < abs(matching[i] - matching_new[i]):
print "Improving further" # Does this ever happen?
return improve_matching(list1, list2, matching_new)
return matching_new
def match_lists (list1, list2):
if 0 == len(list1):
return []
elif 1 == len(list1):
best_j = 0
best_cost = (list1[0] - list2[0])**2
for j in range(1, len(list2)):
cost = (list1[0] - list2[j])**2
if cost < best_cost:
best_cost = cost
best_j = j
return [best_j]
elif 1 < len(list1):
# Solve a smaller problem first.
list1_smaller = [list1[2*i] for i in range((len(list1)+1)//2)]
list2_smaller = [list2[2*i] for i in range((len(list2)+1)//2)]
matching_smaller = match_lists(list1_smaller, list2_smaller)
# Start with that matching.
matching = [None] * len(list1)
for i in range(len(matching_smaller)):
matching[2*i] = 2*matching_smaller[i]
# Fill in the holes between
for i in range(len(matching) - 1):
if matching[i] is None:
best_j = matching[i-1] + 1
best_cost = (list1[i] - list2[best_j])**2
for j in range(best_j+1, matching[i+1]):
cost = (list1[i] - list2[j])**2
if cost < best_cost:
best_cost = cost
best_j = j
matching[i] = best_j
# And fill in the last one if needed
if matching[-1] is None:
if matching[-2] + 1 == len(list2):
# This will be an invalid matching, but improve will fix that.
matching[-1] = matching[-2]
else:
best_j = matching[-2] + 1
best_cost = (list1[-2] - list2[best_j])**2
for j in range(best_j+1, len(list2)):
cost = (list1[-1] - list2[j])**2
if cost < best_cost:
best_cost = cost
best_j = j
matching[-1] = best_j
# And now improve.
return improve_matching(list1, list2, matching)
def best_matching (list1, list2):
matching = match_lists(list1, list2)
cost = 0.0
result = []
for i in range(len(matching)):
pair = (list1[i], list2[matching[i]])
result.append(pair)
cost = cost + (pair[0] - pair[1])**2
return (cost, result)
更新
上面有个bug。可以用 来证明match_lists([1, 3], [0, 0, 0, 0, 0, 1, 3])。然而，下面的解决方案也是O(n)，我相信没有错误。不同之处在于，我不是寻找固定宽度的带，而是寻找由先前匹配动态确定的宽度。由于在任何给定位置最多可以匹配 5 个条目，因此它再次结束O(n)了这个数组和一个几何递减的递归调用。但是相同值的长时间延伸不会引起问题。
def match_lists (list1, list2):
prev_matching = []
if 0 == len(list1):
# Trivial match
return prev_matching
elif 1 < len(list1):
# Solve a smaller problem first.
list1_smaller = [list1[2*i] for i in range((len(list1)+1)//2)]
list2_smaller = [list2[2*i] for i in range((len(list2)+1)//2)]
prev_matching = match_lists(list1_smaller, list2_smaller)
best_j_last = -1
last = {-1: (0.0, None)}
for i in range(len(list1)):
lowest_j = 0
highest_j = len(list2) - 1
if 3 < i:
lowest_j = 2 * prev_matching[i//2 - 2]
if i + 4 < len(list1):
highest_j = 2 * prev_matching[i//2 + 2]
if best_j_last == highest_j:
# Have to push it back.
best_j_last = best_j_last - 1
best_cost = last[best_j_last][0] + (list1[i] - list2[highest_j])**2
best_j = highest_j
this = {best_j: (best_cost, [best_j, last[best_j_last][1]])}
# Now try the others.
for j in range(lowest_j, highest_j):
prev_j = best_j_last
if j <= prev_j:
prev_j = j - 1
if prev_j not in last:
continue
else:
cost = last[prev_j][0] + (list1[i] - list2[j])**2
this[j] = (cost, [j, last[prev_j][1]])
if cost < best_cost:
best_cost = cost
best_j = j
last = this
best_j_last = best_j
(final_cost, linked_list) = last[best_j_last]
matching_rev = []
while linked_list is not None:
matching_rev.append( linked_list[0])
linked_list = linked_list[1]
matching_new = [x for x in reversed(matching_rev)]
return matching_new
def best_matching (list1, list2):
matching = match_lists(list1, list2)
cost = 0.0
result = []
for i in range(len(matching)):
pair = (list1[i], list2[matching[i]])
result.append(pair)
cost = cost + (pair[0] - pair[1])**2
return (cost, result)
笔记
我被要求解释为什么这样有效。
这是我的启发式理解。在算法中，我们解决了一半的问题。然后我们必须解决全部问题。
问题是一个完整问题的最优解可以强制从最优解到半问题多远？list2我们通过让不在半问题中的每个元素尽可能大，并且不在半问题中的每个元素尽可能小来将其推到右侧list1。但是如果我们把半问题的那些推到右边，然后把重复的元素放在它们是模边界效应的地方，我们就得到了半问题的 2 个最优解，而且没有什么比下一个元素向右移动更多的了是在一半的问题。类似的推理适用于试图迫使解决方案离开。
现在让我们讨论这些边界效应。这些边界效应最后是 1 个元素。所以当我们试图把一个元素推到最后时，我们不能总是这样。通过查看 2 个元素而不是 1 个元素，我们也添加了足够的回旋空间来解决这一问题。
因此，必须有一个最佳解决方案，该解决方案非常接近以明显方式加倍的一半问题。可能还有其他人，但至少有一个。并且 DP 步骤会找到它。
我需要做一些工作才能将这种直觉转化为正式的证明，但我相信这是可以做到的。
推荐阅读
- file-upload - 有没有人能够找到使用 vue-apollo 上传图片的完整示例？
- php - 内容安全策略：页面设置阻止加载 domain.com 上的资源（“default-src”）
- matlab - 如何在 Matlab 中将字符串单元格数组转换为 int 和 NaN？
- typescript - 为什么打字稿试图加载错误的类型定义？
- bash - 移动多个文件名相似但相差 1 个字符的文件
- google-app-engine - 对于 GCS 图像 blob，images.get_serving_url 失败
- javascript - ComponentDidUpdate 中的无限循环
- html - css flexbox 3子div，中间div不应该改变
- laravel - Laravel nova，“在 null 上调用函数 tap()”
- regex - 正则表达式，用于将字符串与除特定大写之外的任何大写匹配