python - "Sensibly"删除 Python 列表中的点

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 中自动选择和删除这个点？ IE。是否有一种算法可以从列表中选择最佳 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 和 k == 10。