2

好的，所以均匀点分布的问题由一些众所周知的算法（Hammersley、Monte Carlo 等）解决。但是，我的情况有点不同：假设我有一组值（2、8、1、5、4、7、3、6）。这些值按索引顺序访问（从 2 开始）。如果它们映射在 x 轴上（通过访问模式，即 0 为 2，1 为 8），我必须找到它们对应的 y 值，这样：

  • 整个点集（考虑 x 和 y 坐标）不是低差异序列；
  • 任何一对 x 值（输入集）必须具有它们对应的 y 值，并且它们之间的距离最大；

结果是另一个以混合整数 [1..8] 作为第一个集合b，因此每个元组 (ai, bi) 都遵循上述两个规则。

总结一下：我有一个轴上的分布（无论哪个轴），需要找到另一个轴上的分布，这样连续的点在访问时彼此相距很远，但整体上形成了整体上的均匀分布正方形。

一个例子

给定 4 个元素的输入集 (3,1,4,2)，一个好的结果集是 (xy 合并)：((3,1),(1,4),(4,2),(2,3 )) 这很好，因为当您访问这些点（从 3,1 到结束）时，您访问的每个新点都会在两个轴上实现重大飞跃，这是总体平均分配的目标。相同输入集的错误结果情况是：((3,1),(1,2),(4,3),(2,4))，因为现在我们连续访问 y 值（尽管 x 值可以） .

这都是填写将用于采样的预计算表所必需的，因此任何最终算法的速度都无关紧要（当然，只要不需要 2 年）。任何帮助表示赞赏。

谢谢

4

1 回答 1

0

您可能可以使用分而治之的策略来实现这一目标。基本上，如果你想要一个 1:n 的排列，那么创建一个 1:n/2 和 (n/2+1):n 的排列，并随机散布它们。

以下是如何随机散布它们：

function permute(x,y):
    L1 = permute(x, (x+y)/2)
    L2 = permute((x+y)/2+1, y)
    spin = randomlyselectfrom(-1,1)
    L = []
    while L1 and L2 are not empty:
        if spin<0:
            L.enqueue(L1.dequeue)
        else:
            L.enqueue(L2.dequeue)
        if random()<0.9:
            spin = -spin
    return L

我没有检查边界条件等，如果您不知道如何处理该部分，请随时问我。

一旦您以上述方式获得两个随机序列，将其中一个反转并将它们配对，您将获得所需的配对序列。

于 2012-01-07T02:39:19.843 回答