algorithm - 展开太接近的数组值

Question

我有一个数组中的值列表(从低到高排序)，我打算显示这些值分布在一条线上，但由于一些值很接近，所以点最终会重叠。由于确切的值并不重要，小的调整也无关紧要，我正在尝试编写一些代码来传播任何值簇，以便它们与任何其他值的距离小于 .5。

例如，假设我们有这个数组:

my_values = { 0.2, 1.3, 2.0, 2.1, 2.5, 3.6, 5.2 }

2.0、2.1 和 2.5 靠得太近了，所以我需要移动 使它们不比 .5 更近，但要尽可能接近实际值。所以最佳解决方案是这样的:

my_values = { 0.2, 1.1, 1.6, 2.1, 2.6, 3.6, 5.2 }

到目前为止，这是我的代码，它只是尝试了一个蹩脚的解决方案(我代码中列表中的实际项目是具有 get/set 函数的对象，但原理是相同的):

...
last_dot = -999 'Low enough
For Each dot In my_values
    If dot.getPos <= last_dot + 0.5 Then
        dot.setPos last_dot + 0.5
    End If
    last_dot = dot.getPos
Next dot

有件事我不确定如何解决:我喜欢将它们向上和向下展开，因此任何聚类的中心都不会真正移动。到目前为止，我所做的每一步都只是增加了值，并且集群的最后一个值比其他值偏移得更多，最好是任何向上移动的值都应该有另一个值向下移动。保持任何值的最大调整尽可能低。所以在上面的列表中，当 2.0 向下移动到 1.6 时，它太接近 1.3，所以必须移动到 1.1，但在我的代码中，我不知道在检查 1.3 项时。 (不确定我是否解释过以便任何人都能理解 =/)

任何帮助都适用!

Answer 1

整个数组的迭代松弛:

输入:

 { 0.2, 1.3, 2.0, 2.1, 2.5, 3.6, 5.2 }

功能:

    for (int j = 0; j < 100; j++)// 100 is extreme, maybe 20 is enough for short anomalies
    {
        for (int i = 0; i < t.Length - 1; i++)
        {
            if (t[i] > t[i + 1] - 0.5)
            {
                t[i] -= (t[i] - (t[i + 1] - 0.5)) * 0.1;
            }
        }
        for (int i = t.Length - 1; i >= 1; i--)
        {
            if (t[i] < t[i - 1] + 0.5)
            {
                t[i] -= (t[i] - (t[i - 1] + 0.5)) * 0.1;
            }
        }
    }

结果:

0,2
1,00031552491128
1,61163875308098
2,1160023905259
2,66
3,6
5,2

警告:当只有少数元素需要更改时，O(n) 效率不高。

编辑:将代码更正为 A.S.H.评论了。

新输出:

0,2
1,21857842635286
1,71823144559425
2,21771136663457
2,71733660405361
3,6
5,2

所以它现在看起来更加对称，更接近点 2.05，这是太近的点的中点。