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 回答