OCamlでO（n）のリストをシャッフルするには？

Question

O（N）で、OCamlの中でlistのためにそれを行うにはどのように、代わりに交換して、O（n）の中arrayをシャッフルする

ハードではないでしょうか？

---

要件：

1. ない配列や場所での使用

Answer 1

リストは不変であり、ログがしばしばあります面接の質問としてこれを考えてみましょうn不変の作業のために支払う価格データ。このコストを払うつもりならば、明白な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 

Answer 2

あなたはカードのリフルシャッフルを模倣できます。

カードのデッキのリフルシャッフルをする意味：

• は、実際に逆順列を行うことが容易である二つの部分

をインターリーブ二つの部分

でデッキをカット：

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

「2002年のPersi Diaconisによるリッフルシャッフル解析の数学的展開」によれば、k = 3/2 log_2（n）+ cを選択する。確かに、均一性と結果の間の総変動距離は0に指数関数的に速く低下します。これは、cをインクリメントするたびにほぼ半分になります。あなたはc = 10を選ぶことができます。

スペースO（1）（Lを破壊する場合）、時間O（n log n）。しかし、ジェフリースコフィールドの解はO（n）個のランダムビットしか必要としないが、Θ（n）個の空間しか必要としないが、ランダムジェネレータへのO（n log n）コールがある。