“明智地”删除Python lis中的点

Question

假设我有两个数组，表示校准曲线的x和y坐标。在

X = [1,2,3,4,5,6,7,8,9,10,12,14,16,18,20,30,40,50]
Y = [2,4,6,8,10,12,14,16,18,20,24,28,32,36,40,60,80,100]

我上面的示例数组包含18个点。您将注意到x值不是线性间隔的；在x的较低值处有更多的点

假设我需要将校准曲线中的点数减少到13个点。显然，我可以去掉前五个或最后五个点，但这会缩短x值的整体范围。为了保持范围并最小化x值之间的间距，我会优先删除x=2,4,6,8,10的值。删除这些x点及其各自的y值将在曲线中按要求保留13个点。在

在Python中如何自动删除点？一、 e.是否有从列表中选择最佳x点的算法，其中“最佳”是指在保持整体范围和遵循新点数的同时，使点尽可能靠近。在

请注意，剩余的点必须在原始列表中，因此我无法将18点插值到13点网格上。在

Answer 1

这将使所选点之间的平方根距离最大化。从某种意义上讲，它尽可能地分散了观点。在

import itertools
list(max(itertools.combinations(sorted(X), 13), i
         key=lambda l: sum((a - b) ** 2 for a, b in zip(l, l[1:]))))

请注意，这只适用于小问题。选择k点的时间复杂度是O(k * (len(X) choose k))，因此基本上是O(exp(len(X))。所以不要考虑使用这个，例如len(X) == 100和{}。在

Answer 2

X = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 16, 18, 20, 30, 40, 50]
Y = [2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 24, 28, 32, 36, 40, 60, 80, 100]

assert len(X) == len(set(X)), "Duplicate X values found"

points = list(zip(X, Y))
points.sort()  # sorts by X

while len(points) > 13:
    # Find index whose neighbouring X values are closest together
    i = min(range(1, len(points) - 1), key=lambda p: points[p + 1][0] - points[p - 1][0])
    points.pop(i)

print(points)

输出：

^{pr2}$

如果您想再次使用原始系列：

X, Y = zip(*points)

Answer 3

一种可以实现这一点的算法：

1. 将每个数字转换为左、右数字的绝对差值之和。如果缺少一个数字，无论是第一个还是最后一个，则使用MAX_INT。例如，1将变为MAX_INT；2将变为2，10将变为3。在
2. 去掉第一个金额最小的案例。在
3. 如果需要删除更多数字，请转到1。在

这将删除2,4,6,8,10,3，。。。在