python - 将 float 列表与最近的整数匹配而不重复

Question

我有一个我正在尝试实现的算法，我正在努力寻找一种好的方法。目标是获取一个浮点数列表，并一对一映射到一个整数列表，这样不会有两个浮点数被映射到同一个整数，并且映射具有最小的可能误差(无论是就总数而言)误差或均方误差)。

因此，例如，假设我有数字 [2.1, 2.3, 2.4, 7, 7.5, 8.9, 9.3] .我希望它返回如下内容:

{
    2.1: 1,
    2.3: 2, 
    2.4: 3,
    7: 7,
    7.5: 8,
    8.9: 9,
    9.3: 10
}

请注意，聚集在 2 周围的数字必须分散到 1、2 和 3。

提到我在这里的动机是一个实用的音乐，可能会有所帮助:将微调音高列表(“裂缝之间”的音符)映射到钢琴的琴键。因此，一个“足够好”的问题解决方案确实是我所需要的，尽管真正的最佳解决方案会更令人兴奋!

另外，我正在使用 Python，但当然这里真正的问题不是特定于语言的。

Answer 1

也许不是最优雅、最高效的代码，但是:

它的多项式复杂性

它提供了一个全局最优

基本思路:

计算一些最坏情况的候选人范围(我们不能忘记任何潜在的改进候选人)

我没有投入太多 -> 一个“黑客”

计算距离矩阵

求解矩形 linear-assignment problem

代码:

import math
import numpy as np
from scipy.optimize import linear_sum_assignment
from scipy.spatial.distance import cdist

SQUARED_PENALTY = True

data = np.array([2.1, 2.3, 2.4, 7, 7.5, 8.9, 9.3])

# hacky safety-net -> which candidates to look at
min_ = math.floor(data.min())
max_ = math.ceil(data.max())
gap = max_ - min_

cands = np.arange(min_ - gap, max_ + gap)

cost_matrix = cdist(data[:, np.newaxis], cands[:, np.newaxis])

if SQUARED_PENALTY:
  cost_matrix = np.square(cost_matrix)

row_ind, col_ind = linear_sum_assignment(cost_matrix)

solution = cands[col_ind]

print(solution)
print('cost: ', np.round(cost_matrix[row_ind, col_ind].sum(), 3))

输出:l1-costs

[ 2  1  3  7  8  9 10]
cost:  3.3

输出:平方成本

[ 1  2  3  7  8  9 10]
cost:  2.41