2

配列のランダムなシャッフルは簡単に解決できます。シャッフルを行いたいのですが、任意の要素のシフトが範囲内に制限されるという制限が追加されています。そのため、最大許容 shift の場合、シャッフルの結果として、いずれの方向にもステップを= n超えて要素を移動することはできません。n

したがって、この配列と n=​​3 が与えられた場合:

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

これは有効なシャッフルになります。

[2, 3, 4, 0, 1, 6, 5, 8, 9, 7]

これらは無効になりますが：

[2, 3, 4, 7, 1, 6, 5, 8, 9, 0]
[2, 3, 4, 6, 1, 7, 5, 8, 9, 0]

(範囲は回転ではないことに注意してください)

これを達成するためのシンプルで効率的な方法を探しています。インプレースで実行することをお勧めしますが、適切な解決策が得られる場合は、2 番目の配列を使用しても問題ありません。

単純なスターター ソリューションは、2 番目の配列を使用することです。

for element in array1:
  get legal index range
  filter out indexes already filled
  select random index i from filtered range
  array20[i] = element

編集：

これは、アルゴリズムが最初に終端要素を同じ確率で処理する場合に @ruakh によって提起された確率の歪みの問題に関するものです。

一見、配列サイズが大きくなると確率分散が小さくなると思いましたが、そうではないようです。以下にいくつかの簡単なテストを示します (急いで作成したため、エラーが発生する可能性があります)。確率の歪みが大きいので、一般的なケースとしては受け入れられないと思いますが、コメントで述べたように、自分のアプリケーションではそれで問題ありません。

import itertools

n = 2

def test(arlen):
    ar = range(arlen)
    lst = list(itertools.permutations(ar))
    flst = [l for l in lst if not illegal(l)]

    print 'array length', arlen
    print 'total perms: ', len(lst)
    print 'legal perms: ', len(flst)

    frst = [0] * (n+1)
    for l in flst:
        frst[l[0]] +=1

    print 'distribution of first element: ',frst

def illegal(l):
    for i in range(len(l)):
        if abs(l[i]-i)>n: return True

if __name__=="__main__":
    arlen = range(4,10)
    for ln in arlen:
        test(ln)

------------ n=2
array length 4
total perms:  24
legal perms:  14
distribution of first element:  [6, 4, 4]
array length 5
total perms:  120
legal perms:  31
distribution of first element:  [14, 10, 7]
array length 6
total perms:  720
legal perms:  73
distribution of first element:  [31, 24, 18]
array length 7
total perms:  5040
legal perms:  172
distribution of first element:  [73, 55, 44]
array length 8
total perms:  40320
legal perms:  400
distribution of first element:  [172, 128, 100]
array length 9
total perms:  362880
legal perms:  932
distribution of first element:  [400, 300, 232]

------------ n=4
array length 4
total perms:  24
legal perms:  24
distribution of first element:  [6, 6, 6, 6, 0]
array length 5
total perms:  120
legal perms:  120
distribution of first element:  [24, 24, 24, 24, 24]
array length 6
total perms:  720
legal perms:  504
distribution of first element:  [120, 96, 96, 96, 96]
array length 7
total perms:  5040
legal perms:  1902
distribution of first element:  [504, 408, 330, 330, 330]
array length 8
total perms:  40320
legal perms:  6902
distribution of first element:  [1902, 1572, 1296, 1066, 1066]
array length 9
total perms:  362880
legal perms:  25231
distribution of first element:  [6902, 5836, 4916, 4126, 3451]
4

3 に答える 3

2

これを正確なカバーの問題と見なすことが可能であり、おそらく（私はそれをテストしませんでしたが、この主張を正当化します）ZDDを使用して効率的に解決できます。

正確なカバーの問題には、すべての要素を結果に入れることができるすべての方法に対してブール決定変数があります。したがって、の場合n = 0、要素と同じ数の変数がありますn = 1。これは、端を除くすべての要素に3つの変数があるためです。それぞれ2つの変数があります。

が配列のサイズよりも大幅に小さい場合nは、「遠く離れている」決定変数が相互に直接影響を与えないことを意味します。これにより、ZDDのサイズが適切に保たれるはずです。これは、たとえば、小さなタイルのタイルの問題と構造が同等であるためです。

編集：実際、私は今これについて、特にますます疑わしいと思われるタイリングとの比較可能性については確信が持てませんが、それでもZDDは扱いやすいサイズになると思います。

妥当なサイズのZDDでは、バイアスのない（つまり、すべての解の確率が等しい）ランダム解（「n桁を超えて移動しない」ルールの下で有効な順列に対応）を効率的に生成できます。

そして、それはおそらく最善の方法ではありませんが、力ずくでそれを行うことが可能であることを示しています。

于 2013-01-26T13:45:41.953 に答える
1

可能な出力ごとに等しい確率を持つことについて、あまりうるさくないようです。単純な解決策の 1 つは、バブル ソートのパスと同等の処理を行うことですがn、要素を並べ替えるのではなく、各ステップで 2 つの要素を交換するかどうかをランダムに選択するだけです。このアプローチでは、ランダム化もその場で行うことができます。次のようなことができます。

import random
def shuffle_list(list, n):
    for ipass in xrange(n):
        for ielt in xrange(len(list) - 1):
            if random.randrange(2):
                temp = list[ielt]
                list[ielt] = list[ielt + 1]
                list[ielt + 1] = temp

編集：申し訳ありませんが、これについてもっと考えるべきでした。私が説明したアプローチは機能しません。つまり、最初のパスで、最初の要素がリストの最後までバブリングする可能性はゼロではありません。どういうわけか私はそれを逃した。

今は本当に答えがないと思いますが、少なくともここにアイデアがあります: 元のリストの各要素に に等しいプロキシ値を割り当てます。ここで、 は元ii + random.uniform(-n/2., n/2.)のiiリストの要素のインデックスです。次に、このプロキシ値に基づいて元のリストを並べ替えます。次に、その要素iiが最終リストに表示される最も早い位置は位置です。これは、要素がプロキシ値を受け取り、要素で始まる各要素が少なくとも のプロキシ値を受け取ったii-n場合にのみ発生します。上限についても同じ引数。ii-n/2.ii-nii-n/2.

実際には、おそらくrandom.uniform(-n/2. - 0.49, n/2. + 0.5). この計算はまだ慎重に行っていませんが、これで距離の制約が維持されると思います。また、可能なリストの最終的な分布がどうなるかは完全にはわかりません。@Basel、元の提案についてはあなたが正しいと思います。各要素を大きく動かすよりも小さく動かす可能性が高いようです。この解決策の方が良いと思いますが、それを誓うことはできません。:-)

于 2013-01-26T19:06:11.953 に答える
1
  • 入力InputArray: 整数の配列
  • 入力NumberCount: InputArray 内の整数の数

  • 入力ShuffleRange: 数値がジャンプできる有効範囲

  • ShuffleWindowSize: スワッピングが発生する処理ウィンドウ。その値はShuffleRange +1

  • ShuffleIndexArray: シャッフリング ウィンドウの入力数値のインデックス、無効なインデックスはINT_MINになります

初期化ShuffleIndexArray

for (idx =0; idx < ShuffleWindowSize; idx++) {
  ShuffleIndexArray[idx] = idx;
}

プロセスInputArray

for (idx = 0; idx < NumberCount; idx++) {

    shuffleIdx = idx % ShuffleWindowSize;

    /* 1. Check if the Element has been moved from it's Original Position
     * 1.1 IF it was swapped already then move to next element
     * 1.2 ELSE perform shuffling within available window
     */
    if (idx != ShuffleIndexArray[shuffleIdx]) { /* was swapped already */
        goto LOOP_CONTINUE;
    }
    /* Get a random Index in the range [0, shuffleWinSize) */
    randomSwapIdx = rand() % shuffleWinSize; /* OffSet */

    /* Skip Invalid Indexes */
    if (INT_MIN == shuffleIndexArray[randomSwapIdx]) {
        for (jdx = randomSwapIdx + shuffleWinSize - 1; jdx > randomSwapIdx; jdx--) {
            if (INT_MIN != shuffleIndexArray[jdx % shuffleWinSize]) {
                randomSwapIdx = jdx % shuffleWinSize;
                break;
            }
        }
    }

    /* Get the actual index into InputArray */
    randomSwapIdx = ShuffleIndexArray[randomSwapIdx]; /*Actual Index*/

    /* Check if number gets to stay in original position */
    if (idx == randomSwapIdx) { /* Lucky Bugger */
        goto LOOP_CONTINUE;
    }

    /* Swapping of two numbers in InputArray */
    swapInt = inputArr[idx];
    inputArr[idx] = inputArr[randomSwapIdx];
    inputArr[randomSwapIdx] = swapInt;

    /* Update indexes in Shuffle-Window Array */
    ShuffleIndexArray[randomSwapIdx % ShuffleWindowSize] = idx;

    LOOP_CONTINUE:
    /* InputArray[idx] was processed.
     * Update ShuffleIndexArray */
    ShuffleIndexArray[shuffleIdx] =
            ((idx + ShuffleWindowSize) < NumberCount) ?
                    (idx + ShuffleWindowSize) : INT_MIN;
}

ShuffleWindowSizeインデックスを追跡するために別のサイズの配列が必要であることを除いて、これはインプレース シャッフルです。

于 2013-01-26T13:30:40.813 に答える