时间戳

首页 > 解决方案 > 将浮点数列表匹配到最接近的整数而不重复

python - 将浮点数列表匹配到最接近的整数而不重复

问题描述

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

因此，例如，假设我有 numbers [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，但这里真正的问题当然不是特定于语言的。

标签： pythonalgorithmmappingroundingmathematical-optimization

解决方案

也许不是最优雅和最有效的代码，但是：

  • 它具有多项式复杂性
  • 它提供了全局最优

基本思路：

  • 计算候选人的一些最坏情况范围（我们不能忘记任何潜在的改进候选人）
    • 我并没有投入太多 -> 一个“黑客”
  • 计算距离矩阵
  • 解决矩形线性分配问题

代码：

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-成本

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

输出：平方成本

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

推荐阅读