根据出现的距离和频率选择项目（来自一组项目）

Question

存在一组点（或项，无关紧要）。每个点a与该集合中的其他点相距特定距离。可以通过函数retrieve_dist(a, b)检索距离。

这个问题是关于编程（在Python中）一种算法，用于从这组点中选择一个点，并进行替换。挑选点：

i）必须与所有已经选定的点保持最大距离，同时遵守（ii）中的要求

ii）样品中已经选择的点出现的次数必须在该计算中带有重量。即应该更加频繁地权衡更频繁选择的点。

例如。想象a和b已被选中（分别为100和10次）。然后，当要选择下一个点时，它与a的距离比它与b的距离更重要，与已经选择的样本中a的出现频率一致。

---

我能尝试什么：

如果没有重量/频率，这将很容易实现。我可以：

distances = defaultdict(int)
for new_point in set_of_points:
    for already_selected_point in selected_points:
        distances[new_point] += retrieve_dist(new_point, already_selected_point)

然后我按每个元组中的第二个条目对distances.items()进行排序，然后选择所需的项目。

然而，当已经选择的点的频率发挥作用时，我似乎无法绕过这个问题。

专家可以帮忙吗？提前致谢。

Answer 1

你的问题的解决方案是使selected_points成为list而不是set。在这种情况下，将每个新点与a和b（以及所有其他点）进行比较，就像它们已被发现的次数一样多。

如果通常多次发现每个点，则可以使用dict来改善性能，其中键是点，并且值是每个点被选择的次数。在那种情况下，我认为你的算法将是

distances = defaultdict(int)

for new_point in set_of_points:
    for already_selected_point, occurances in selected_points.items():
        distances[new_point] += occurances * retrieve_dist(new_point, already_selected_point)