正方形上的随机均匀点分布（有捕获）

Question

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

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

结果是另一个集合 b ，其中混合整数 [1..8] 作为第一个，因此每个元组 (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 年）。任何帮助表示赞赏。

谢谢

Answer 1

您也许可以使用分而治之的策略来实现这一目标。基本上，如果您想要 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

我省略了对边界条件等的检查，如果您不知道如何处理该部分，请随时问我。

一旦你以上述方式获得了两个随机序列，反转其中一个并将它们配对，你就会得到你需要的配对序列。