7

arrayインプレーススワッピングを使用して、O（n）でシャッフルすることは難しくありません。

listO（n）を使ってOCamlでそれを行う方法は？

要件：

  1. アレイなしまたはインプレース使用

  2. これを面接の質問と考えてください

4

2 に答える 2

13

リストは不変であり、不変のデータを処理するために支払う対数の代償がしばしばあります。このコストを支払う意思がある場合は、明らかなn log nアプローチがあります。各リスト要素にランダムな値をタグ付けし、ランダムな値に基づいて並べ替え、ランダムな値を削除します。これは、本番コードでリストをシャッフルする方法です。

これが私が販売しているiOSアプリのシャッフルコードです。

let shuffle d =
    let nd = List.map (fun c -> (Random.bits (), c)) d in
    let sond = List.sort compare nd in
    List.map snd sond
于 2013-02-26T17:42:51.233 に答える
0

カードのリフルシャッフルを模倣することができます。

カードのデッキのリフルシャッフルは、次のことを意味します。

  • デッキを2つに切る
  • 2つの部分をインターリーブします

実際には、逆順列を実行する方が簡単です。

  • 2つの補助リストAとBがあり、元のリストLを繰り返し、各要素をAまたはBの前にランダムに（確率1/2で）プッシュします。
  • L：= List.rev A @ List.rev B（これは、カスタムList.revで末尾再帰にすることができます）。
  • k回繰り返します。

「パーシ・ダイアコニスによるリフルシャッフリングの分析からの数学的発展、2002年」によれば、k = 3/2 log_2（n）+cを選択します。実際、均一性と結果の間の合計変動距離は指数関数的に0に低下します。つまり、cをインクリメントするたびに約半分になります。c=10を選択できます。

スペースO（1）（Lを破壊した場合）、時間O（n log n）。ただし、ランダムジェネレーターへのO（n log n）呼び出しがありますが、Jeffrey ScofieldのソリューションにはO（n）ランダムビットのみが必要ですが、Θ（n）スペースが必要です。

于 2013-02-26T23:10:06.213 に答える