2

私は現在、入力された文字列をスクランブルする単純な関数に取り組んでおり、考えられるすべての順列が同じ可能性があります。私のコードは以下です。

function scramble(s) {
    result = s.split("");
    for(var i = 0; i < s.length; i++) {
        var j = Math.floor(Math.random() * (i + 1));
        var scrambler = result[i];
        result[i] = result[j];
        result[j] = scrambler;
    }
    return result.join("");
}

これまでのところ、コードは正常に機能しているように見えます...しかし、すべての可能な順列は同じように起こりますか? (私は Math.random と Math.floor を信じていますが、実行時に i と j を見ると奇妙な出力が得られます。)

4

2 に答える 2

3

ここでひどい間違いを犯さない限り (意味があることを確認してください)、このコードは均一に分散された順列を作成しないと思います。

たとえば、最初の文字が所定の位置にとどまる可能性を確認します。i が 0 の場合、誰とも置き換えることができません。i が 1 の場合、要素 0 と 1 は 50% の確率で交換されます。したがって、合計で、結果[0]は確率でその場所に残ります1/2 * 2/3 * 3/4 ... n-1/n = 1/n

ただし、最後の要素が所定の位置に留まる確率は単純に (n-1)/n です。これは、入れ替える機会が 1 回しかなく、配列全体から選択するためです。

(i+1)を に置き換えると、より良いディストリビューションになる可能性がありますs.lengthが、最善の策は、動作することが知られているものを使用することです。ここから開始できます - http://en.wikipedia.org/wiki/Random_permutation

于 2013-09-23T00:15:08.587 に答える