総論
確率を使用するアルゴリズムの正しさに関する私の個人的なアプローチ：それが正しいことを証明する方法を知っているなら、それはおそらく正しいでしょう。そうでなければ、それは確かに間違っています。
別の言い方をすれば、思いついたすべてのアルゴリズムを分析しようとするのは一般的に絶望的です。正しいと証明できるアルゴリズムが見つかるまで、アルゴリズムを探し続ける必要があります。
分布を計算することによるランダムアルゴリズムの分析
単純な「大量のテストをスローして均一性をチェックする」よりも強力なシャッフル（またはより一般的にはランダムを使用するアルゴリズム）を「自動的に」分析する1つの方法を知っています。アルゴリズムの各入力に関連付けられた分布を機械的に計算できます。
一般的な考え方は、ランダムを使用するアルゴリズムが可能性の世界の一部を探索するというものです。アルゴリズムがセット内のランダムな要素を要求するたびに（コインを投げるときは{ true、 }）、アルゴリズムには2つの可能な結果があり、そのうちの1つが選択されます。falseアルゴリズムを変更して、可能な結果の1つを返す代わりに、すべてのソリューションを並行して探索し、関連する分布とともにすべての可能な結果を返すようにすることができます。
一般に、これにはアルゴリズムを徹底的に書き直す必要があります。言語が区切られた継続をサポートしている場合は、サポートする必要はありません。ランダム要素を要求する関数内に「すべての可能な結果の探索」を実装できます（ランダムジェネレーターは、結果を返す代わりに、プログラムに関連付けられた継続をキャプチャし、すべての異なる結果で実行するという考え方です）。このアプローチの例については、olegのHANSEIを参照してください。
中間的で、おそらくそれほど難解ではない解決策は、この「可能な結果の世界」をモナドとして表現し、モナドプログラミングの機能を備えたHaskellなどの言語を使用することです。確率パッケージの確率モナドを使用した、Haskellでのアルゴリズムのバリアント¹の実装例を次に示します。
import Numeric.Probability.Distribution
shuffleM :: (Num prob, Fractional prob) => [a] -> T prob [a]
shuffleM [] = return []
shuffleM [x] = return [x]
shuffleM (pivot:li) = do
(left, right) <- partition li
sleft <- shuffleM left
sright <- shuffleM right
return (sleft ++ [pivot] ++ sright)
where partition [] = return ([], [])
partition (x:xs) = do
(left, right) <- partition xs
uniform [(x:left, right), (left, x:right)]
特定の入力に対して実行し、出力分布を取得できます。
*Main> shuffleM [1,2]
fromFreqs [([1,2],0.5),([2,1],0.5)]
*Main> shuffleM [1,2,3]
fromFreqs
[([2,1,3],0.25),([3,1,2],0.25),([1,2,3],0.125),
([1,3,2],0.125),([2,3,1],0.125),([3,2,1],0.125)]
このアルゴリズムは、サイズ2の入力では均一ですが、サイズ3の入力では不均一であることがわかります。
テストベースのアプローチとの違いは、有限のステップ数で絶対的な確実性を得ることができることです。それは、可能性の世界の徹底的な調査に相当するため、非常に大きくなる可能性があります（ただし、通常は2 ^N未満です。同様の結果の因数分解があります）が、それが不均一な分布を返す場合、アルゴリズムが間違っていることは確かです。もちろん、との一様分布を返す場合は[1..N]、1 <= N <= 100アルゴリズムがサイズ100のリストまで一様であることだけがわかります。それはまだ間違っているかもしれません。
¹：このアルゴリズムは、特定のピボット処理のため、Erlangの実装の変形です。あなたの場合のようにピボットを使用しない場合、入力サイズは各ステップで減少しなくなります。アルゴリズムは、すべての入力が左側のリスト（または右側のリスト）にあり、無限ループで失われる場合も考慮します。 。これは確率モナド実装の弱点であり（アルゴリズムの確率が0である場合、分散計算はまだ発散する可能性があります）、修正方法はまだわかりません。
ソートベースのシャッフル
これが私が正しいと証明できると私が確信している単純なアルゴリズムです：
- コレクション内の要素ごとにランダムなキーを選択します。
- キーがすべて区別できない場合は、手順1から再開します。
- これらのランダムキーでコレクションを並べ替えます。
衝突の確率（選択された2つの乱数が等しい）が十分に低いことがわかっている場合は、手順2を省略できますが、それがないと、シャッフルは完全に均一ではありません。
[1..N]でキーを選択すると、Nはコレクションの長さであり、多くの衝突が発生します（誕生日の問題）。キーを32ビット整数として選択した場合、実際には競合の可能性は低くなりますが、それでも誕生日の問題が発生する可能性があります。
有限長のキーではなく、無限の（遅延評価された）ビット文字列をキーとして使用する場合、衝突の確率は0になり、区別をチェックする必要がなくなります。
怠惰な実数を無限のビット文字列として使用する、OCamlでのシャッフル実装は次のとおりです。
type 'a stream = Cons of 'a * 'a stream lazy_t
let rec real_number () =
Cons (Random.bool (), lazy (real_number ()))
let rec compare_real a b = match a, b with
| Cons (true, _), Cons (false, _) -> 1
| Cons (false, _), Cons (true, _) -> -1
| Cons (_, lazy a'), Cons (_, lazy b') ->
compare_real a' b'
let shuffle list =
List.map snd
(List.sort (fun (ra, _) (rb, _) -> compare_real ra rb)
(List.map (fun x -> real_number (), x) list))
「純粋なシャッフル」には他のアプローチがあります。良いものは、apfelmusのマージソートベースのソリューションです。
アルゴリズムに関する考慮事項：以前のアルゴリズムの複雑さは、すべてのキーが異なる確率に依存します。それらを32ビット整数として選択すると、特定のキーが別のキーと衝突する確率は約40億分の1になります。乱数の選択がO（1）であると仮定すると、これらのキーによる並べ替えはO（n log n）です。
ビットストリングを無限に設定する場合、ピッキングを再開する必要はありませんが、複雑さは「ストリームの平均で評価される要素の数」に関係します。平均してO（log n）だと思いますが（それでも合計でO（n log n））、証明はありません。
...そしてあなたのアルゴリズムはうまくいくと思います
さらに反射した後、私は（douplepのように）あなたの実装は正しいと思います。これが非公式の説明です。
リスト内の各要素は、いくつかのテストによってテストされrandom:uniform() < 0.5ます。要素に、これらのテストの結果のリストをブール値または{ 0、1}のリストとして関連付けることができます。アルゴリズムの開始時には、これらの番号のいずれかに関連付けられているリストはわかりません。最初のpartition呼び出しの後、各リストの最初の要素などがわかります。アルゴリズムが返されると、テストのリストは完全に認識され、要素はそれらのリストに従って並べ替えられます（辞書式順序で並べ替えられるか、実数のバイナリ表現と見なされます）。数字）。
したがって、アルゴリズムは無限ビット文字列キーによるソートと同等です。ピボット要素上でのクイックソートの分割を連想させるリストを分割するアクションは、実際には、ビット文字列内の特定の位置について、評価0のある要素を評価のある要素から分離する方法です1。
ビット文字列がすべて異なるため、並べ替えは均一です。実際、実数が-番目のビットまで等しい2つの要素は、深さnの再帰呼び出し中に発生するパーティションの同じ側にあります。アルゴリズムは、パーティションから生じるすべてのリストが空またはシングルトンの場合にのみ終了します。すべての要素が少なくとも1つのテストによって分離されているため、1つの異なる2進数の小数があります。shufflen
確率的終了
あなたのアルゴリズム（または私の同等のソートベースの方法）についての微妙な点は、終了条件が確率的であるということです。フィッシャー-イェーツは、既知のステップ数（配列内の要素数）の後に常に終了します。アルゴリズムでは、終了は乱数ジェネレーターの出力に依存します。
アルゴリズムを終了させるのではなく、分岐させる可能性のある出力があります。たとえば、乱数ジェネレーターが常に出力する場合0、各partition呼び出しは入力リストを変更せずに返します。このリストで再帰的にシャッフルを呼び出します。無限にループします。
ただし、乱数ジェネレーターが公平であると確信している場合、これは問題ではありません。それは不正行為を行わず、常に独立した均一に分散された結果を返します。その場合、テストrandom:uniform() < 0.5が常に戻るtrue（またはfalse）確率は正確に0です。
- 最初のN回の呼び出しが戻る確率
trueは2^{-N}です。
- すべての呼び出しが戻る
true確率は、すべてのNについて、最初のN個の呼び出しが戻るイベントの無限交差の確率0です。これは、2 ^ {-N}の最小限界¹であり、0です。
¹：数学の詳細については、http：//en.wikipedia.org/wiki/Measure_ （mathematics）#Measures_of_infinite_intersections_of_measurable_setsを参照してください。
より一般的には、一部の要素が同じブールストリームに関連付けられた場合にのみ、アルゴリズムは終了しません。これは、少なくとも2つの要素が同じブールストリームを持っていることを意味します。ただし、2つのランダムなブールストリームが等しい確率は再び0です。位置Kの桁が等しい確率は1/2であるため、最初のN桁が等しい確率は2 ^ {-N}であり、同じです。分析が適用されます。
したがって、アルゴリズムが確率1で終了することがわかります。これは、常に終了するフィッシャー-イェーツアルゴリズムの保証が少し弱いです。特に、乱数ジェネレーターを制御する邪悪な敵の攻撃に対して脆弱です。
より確率論を使用すると、特定の入力長に対するアルゴリズムの実行時間の分布を計算することもできます。これは私の技術的能力を超えていますが、それは良いことだと思います。平均してO（log N）の最初の桁を見るだけで、N個のレイジーストリームがすべて異なること、および実行時間がはるかに長くなる可能性があることを確認できます。指数関数的に減少します。