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) は上記の 2 つの規則に従います。

要約すると: 私は 1 つの軸 (どの軸に関係なく) 上の分布を持っており、アクセスされたときに連続するポイントが互いに遠く離れているが全体的には全体的に均一な分布を形成するように、もう一方の軸上の分布を見つける必要があります。四角。

事例

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

境界条件等のチェックは省いておりますが、その部分の処理方法がわからない場合はお気軽にお尋ねください。

上記の方法で 2 つのランダム シーケンスを取得したら、そのうちの 1 つを逆にしてペアにすると、必要なペア シーケンスが得られます。

于 2012-01-07T02:39:19.843 に答える