25

線形 (n log n) 時間と対数 (log n) 余分なスペースでリンク リストをランダムにシャッフルする分割統治アルゴリズムを使用して、リンク リストをシャッフルしようとしています。

値の単純な配列で使用できるのと同様のクヌース シャッフルを実行できることは認識していますが、分割統治法でこれを行う方法がわかりません。私が言いたいのは、実際に何を分割しているのかということです。リスト内の個々のノードに分割してから、ランダムな値を使用してリストをランダムに組み立て直しますか?

または、各ノードに乱数を与えてから、乱数に基づいてノードでマージソートを実行しますか?

4

7 に答える 7

36

以下はどうですか？マージソートと同様の操作を行います。マージするときは、2 つのリストから要素を 1 つずつ選択する代わりに、コインを投げます。コイン投げの結果に基づいて、最初のリストから要素を選択するか、2 番目のリストから要素を選択するかを選択します。

編集 (2022-01-12): GA1 が下の回答で指摘しているように、このアルゴリズムは順列をランダムに一様に生成しません。

アルゴリズム。

shuffle(list):
    if list contains a single element
        return list

    list1,list2 = [],[]
    while list not empty:
        move front element from list to list1
        if list not empty: move front element from list to list2

    shuffle(list1)
    shuffle(list2)

    if length(list2) < length(list1):
        i = pick a number uniformly at random in [0..length(list2)]             
        insert a dummy node into list2 at location i 

    # merge
    while list1 and list2 are not empty:
        if coin flip is Heads:
            move front element from list1 to list
        else:
            move front element from list2 to list

    if list1 not empty: append list1 to list
    if list2 not empty: append list2 to list

    remove the dummy node from list

スペースの重要な点は、リストを 2 つに分割しても余分なスペースが必要ないことです。必要な唯一の余分なスペースは、再帰中にスタックに log n 個の要素を維持することです。

ダミー ノードのポイントは、ダミー要素の挿入と削除によって要素の分布が均一に保たれることを認識することです。

編集 (2022-01-12): Riley がコメントで指摘しているように、以下の分析には欠陥があります。

分析。 なぜ分布は均一なのですか？最終マージ後、P_i(n)特定の数字がその位置に収まる確率は次のiとおりです。次のいずれかでした。

  • 独自のリストのi- 番目の場所にあり、そのリストが最初にコイントスに勝ったi場合、この確率は1/2^iです。
  • i-1独自のリストの第 1 位で、リストが最後のコイン トスを含めてコイン トスに 1 回勝って1回i-1負けた場合、この確率は回です。(i-1) choose 11/2^i
  • i-2独自のリストの 2 番目の場所にあり、リストが最後のコイン トスを含めてコイン トスで 2 回勝ち、2回i-2負けた場合、この確率は回です。(i-1) choose 21/2^i
  • 等々。

だから確率

P_i(n) = \sum_{j=0}^{i-1} (i-1 choose j) * 1/2^i * P_j(n/2).

帰納的に、それを示すことができますP_i(n) = 1/n。基本ケースを確認して、P_j(n/2) = 2/n. この項\sum_{j=0}^{i-1} (i-1 choose j)は、正確にi-1- ビットの 2 進数の数、つまり2^{i-1}です。だから私たちは得る

P_i(n) = \sum_{j=0}^{i-1} (i-1 choose j) * 1/2^i * 2/n
       = 2/n * 1/2^i * \sum_{j=0}^{i-1} (i-1 choose j)
       = 1/n * 1/2^{i-1} * 2^{i-1}
       = 1/n

これが理にかなっていることを願っています。必要な唯一の仮定は、それnが偶数であり、2 つのリストが均一にシャッフルされていることです。これは、ダミー ノードを追加 (および削除) することによって実現されます。

PS私の最初の直感は厳密にはほど遠いものでしたが、念のためリストに挙げておきます。リストの要素に 1 から n までの数字をランダムに割り当てるとします。そして、これらの数値に関してマージソートを実行します。マージの任意のステップで、2 つのリストのどちらのヘッドが小さいかを判断する必要があります。しかし、一方が他方よりも大きい確率はちょうど 1/2 であるべきなので、コインを投げることでこれをシミュレートできます。

PPS ここに LaTeX を埋め込む方法はありますか?

于 2012-08-28T22:03:43.433 に答える
7

コード

アップシャッフルアプローチ

この (lua) バージョンは、foxcub の回答から改善され、ダミー ノードの必要性がなくなりました。

この回答のコードを少し単純化するために、このバージョンでは、リストがサイズを知っていると想定しています。そうでない場合は、いつO(n)でも時間内に見つけることができますが、さらに良いことに、事前に計算する必要がないように、コードでいくつかの簡単な適応を行うことができます (前半と後半の代わりに 1 を 2 で分割するなど)。 .

function listUpShuffle (l)
    local lsz = #l
    if lsz <= 1 then return l end

    local lsz2 = math.floor(lsz/2)
    local l1, l2 = {}, {}
    for k = 1, lsz2     do l1[#l1+1] = l[k] end
    for k = lsz2+1, lsz do l2[#l2+1] = l[k] end

    l1 = listUpShuffle(l1)
    l2 = listUpShuffle(l2)

    local res = {}
    local i, j = 1, 1
    while i <= #l1 or j <= #l2 do
        local rem1, rem2 = #l1-i+1, #l2-j+1
        if math.random() < rem1/(rem1+rem2) then
            res[#res+1] = l1[i]
            i = i+1
        else
            res[#res+1] = l2[j]
            j = j+1
        end
    end
    return res
end

ダミー ノードの使用を避けるには、各リストで選択する確率を変えることで、2 つの中間リストの長さが異なる可能性があるという事実を補う必要があります。これは、(2 つのリストで) ポップされたノードの総数に対する最初のリストからポップされたノードの比率に対して [0,1] 一様乱数をテストすることによって行われます。

ダウンシャッフルアプローチ

再帰的に再分割しながらシャッフルすることもできます。私の控えめなテストでは、わずかに (しかし一貫して) パフォーマンスが向上しました。命令が少ないために発生した可能性もあれば、luajit のキャッシュ ウォームアップが原因で発生した可能性もあるため、ユース ケースのプロファイルを作成する必要があります。

function listDownShuffle (l)
    local lsz = #l
    if lsz <= 1 then return l end

    local lsz2 = math.floor(lsz/2)
    local l1, l2 = {}, {}
    for i = 1, lsz do
        local rem1, rem2 = lsz2-#l1, lsz-lsz2-#l2
        if math.random() < rem1/(rem1+rem2) then
            l1[#l1+1] = l[i]
        else
            l2[#l2+1] = l[i]
        end
    end

    l1 = listDownShuffle(l1)
    l2 = listDownShuffle(l2)

    local res = {}
    for i = 1, #l1 do res[#res+1] = l1[i] end
    for i = 1, #l2 do res[#res+1] = l2[i] end
    return res
end

テスト

完全なソースはlistShuffle.lua Gistにあります。

これには、実行時に、入力リストの各要素について、指定された回数の実行後に出力リストの各位置に出現する回数を表す行列を出力するコードが含まれています。かなり均一なマトリックスは、文字の分布の均一性を「示し」、したがってシャッフルの均一性を示します。

以下は、(2 の累乗ではない) 3 要素リストを使用して 1000000 回の反復で実行される例です。

>> luajit listShuffle.lua 1000000 3
Up shuffle bias matrix:
333331 332782 333887
333377 333655 332968
333292 333563 333145
Down shuffle bias matrix:
333120 333521 333359
333435 333088 333477
333445 333391 333164
于 2014-03-05T18:56:30.057 に答える
7

キツネの答えは間違っていると思います。完全にシャッフルされたリストの便利な定義を紹介することを証明するために (配列またはシーケンスなど、任意の名前を付けてください)。

L定義:要素a1, a2 ... anとインデックスを含むListがあるとします1, 2, 3..... n。Lをシャッフル操作 (アクセスできない内部) に公開すると、いくつかの k ( ) 要素のインデックスを知ることによって残りの要素のインデックスを推測できないL場合にのみ、完全にシャッフルされます。つまり、残りの要素は、残りのインデックスのいずれかで明らかになる可能性が等しくなります。k< nn-kn-kn-k

例: 4 つの要素のリストがあり、それをシャッフルした後、その最初の要素が( ) で[a, b, c, d]あることがわかります。要素のいずれかが発生する確率は、たとえば、3 番目のセルが に等しいとします。a[a, .., .., ..]b, c, d1/3


ここで、アルゴリズムが定義を満たさない最小のリストには 3 つの要素があります。しかし、アルゴリズムはとにかくそれを 4 要素リストに変換するので、4 要素リストの誤りを示そうとします。

入力を考えるL = [a, b, c, d]アルゴリズムの最初の実行に続いて、L は と に分割されl1 = [a, c]ますl2 = [b, d]。これらの 2 つのサブリストをシャッフルした後 (ただし、4 つの要素の結果にマージする前)、4 つの同じ確率の 2 つの要素のリストを取得できます。

l1shuffled = [a , c]     l2shuffled = [b , d]
l1shuffled = [a , c]     l2shuffled = [d , b]
l1shuffled = [c , a]     l2shuffled = [b , d]
l1shuffled = [c , a]     l2shuffled = [d , b]


ここで、2 つの質問に答えてみてください。 1.最終結果にマージした後、リストの最初の要素になる
確率はいくらですか。a
簡単に言えば、上記の 4 つのペアのうちの 2 つだけ (これも同様に可能性が高い) がそのような結果をもたらすことがわかります ( p1 = 1/2)。これらの各ペアheadsは、マージ ルーチンの最初の反転時に描画する必要があります ( p2 = 1/2)。aしたがって、の最初の要素としてを持つ確率は でLshuffledありp = p1*p2 = 1/4、これは正しいです。


2.aが の 1 番目の位置にあるLshuffledcbdLshuffled
ことを知っている場合、完全にシャッフルされたリストの上記の定義に従って、Nowの 2 番目の位置にある確率(一般性を失うことなく選択することもできます) はどのくらいです1/3か?リストの残りの 3 つのセルに入力する数字が 3 つあるため、 答えは になるはず
です。アルゴリズムがそれを保証するかどうか見てみましょう。 の最初の要素として
選択すると、次のいずれかになります: または: どちらの場合も選択する確率は、反転する確率( ) に等しいため、の 2 番目の要素として持つ確率は1Lshuffled
l1shuffled = [c] l2shuffled = [b, d]

l1shuffled = [c] l2shuffled = [d, b]
3headsp3 = 1/23Lshuffledの最初の要素要素Lshuffledが1等しいことを知っている場合1/2。これで、アルゴリズムの誤りの1/2 != 1/3証明が終了します。

興味深いのは、アルゴリズムが完全なシャッフルに必要な (しかし十分ではない) 条件を満たしていることです。

nすべてのインデックスk( <n) について、すべての要素について、要素のリストが与えられた場合: リスト回akをシャッフルした後、インデックスで発生した回数をカウントした場合、このカウントは確率的に傾向があり、無限大になる傾向があります。makkm/nm

于 2015-02-27T12:31:09.830 に答える
1

考えられる解決策の 1 つを次に示します。

#include <stdlib.h>

typedef struct node_s {
   struct node_s * next;
   int data;
} node_s, *node_p;

void shuffle_helper( node_p first, node_p last ) {
   static const int half = RAND_MAX / 2;
   while( (first != last) && (first->next != last) ) {
      node_p firsts[2] = {0, 0};
      node_p *lasts[2] = {0, 0};
      int counts[2] = {0, 0}, lesser;
      while( first != last ) {
         int choice = (rand() <= half);
         node_p next = first->next;
         first->next = firsts[choice];
         if( !lasts[choice] ) lasts[choice] = &(first->next);
         ++counts[choice];
         first = next;
      }

      lesser = (counts[0] < counts[1]);

      if( !counts[lesser] ) {
         first = firsts[!lesser];
         *(lasts[!lesser]) = last;
         continue;
      }

      *(lasts[0]) = firsts[1];
      *(lasts[1]) = last;

      shuffle_helper( firsts[lesser], firsts[!lesser] );

      first = firsts[!lesser];
      last = *(lasts[!lesser]);
   }
}

void shuffle_list( node_p thelist ) { shuffle_helper( thelist, NULL ); }

これは基本的にクイックソートですが、ピボットがなく、ランダムなパーティション分割があります。

外側のwhileループは、再帰呼び出しを置き換えます。

内側のwhileループは、各要素を 2 つのサブリストのいずれかにランダムに移動します。

内側のwhileループの後、サブリストを互いに接続します。

次に、小さい方のサブリストを再帰し、大きい方をループします。

より小さいサブリストが最初のリストのサイズの半分を超えることは決してないため、最悪の場合の再帰の深さは要素数の対数底 2 です。必要なメモリ量は、再帰の深さの O(1) 倍です。

平均実行時間と呼び出し回数rand()は O(N log N) です。

より正確なランタイム分析には、「ほぼ確実に」というフレーズを理解する必要があります。

于 2016-10-26T01:26:10.800 に答える
0

比較なしのボトムアップ マージ ソート。マージ中は比較を行わず、要素を交換するだけです。

于 2016-09-07T05:13:40.523 に答える
0

リストをトラバースして、各ノードでランダムに 0 または 1 を生成できます。

1 の場合、ノードを削除し、リストの最初のノードとして配置します。0 の場合は何もしません。

リストの最後に到達するまでこれをループします。

于 2020-05-25T04:05:59.977 に答える