正方形上的隨機均勻點分佈

好的，所以統一點分佈問題可以通過一些衆所周知的算法（Hammersley，Monte Carlo等）來解決。然而，我的情況有點不同：可以說我有設置值a值（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直到結束），每訪問一個新點，你都會在上進行大幅度的飛躍，兩個軸都是軸這是總體平均分配的目標。由於現在我們連續訪問y值（儘管x值正確），因此對於相同輸入集的不良結果是：（（3,1），（1,2），（4,3），（2,4）），。

這是所有需要填充預先計算的表格，這將用於採樣，所以任何最終算法的速度並不重要（當然，只要它不需要2年）。任何幫助讚賞。

謝謝

來源

2011-10-19 Emil Kirichev

我不明白第二個條件。請寫一個好的和一個壞的解決方案來發布示例，並解釋他們爲什麼好/壞。 – Dialecticus

@Dialecticus好的，增加了一個例子。我希望現在很清楚。 –

因此，實際上你正在尋找'[1..n]'中的隨機確定標準*置換*，而不是一個正方形上的隨機點？如果'n'小，計算所有'n！'排列的適合度，並且統一挑選其中一個'足夠好'的排列。 – AakashM

您可以使用分而治之策略來實現這一點。基本上，如果你想要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-07 02:39:19 ElKamina

正方形上的隨機均勻點分佈

回答

相關問題