-1

このシャッフルアルゴリズムが適切であることを確認するだけです。それとも、改善される可能性がありますか？

public static void shuffleArray(Object[] arr, Random rnd){
    int lastIndex = arr.length - 1;
    for (int i=0; i<=lastIndex; i++){
        int k = rnd.nextInt(lastIndex+1);
        Object a = arr[i];
        Object b = arr[k];
        arr[i] = b;
        arr[k] = a;
    }
}
4

3 に答える 3

4

乱数は、0..lastIndex+1 の範囲ではなく、i..lastIndex+1 の範囲で選択する必要があります。説明については、Google for Fisher-Yates shuffle を参照してください。

x = arr[i]、arr[i] = arr[k]、arr[k] = x.

于 2013-06-13T13:35:31.923 に答える
4

適切で均一に分散されていると言っている場合は、そうではありません。反復ごとに、可能な構成のそれぞれで、N 個の可能な次の構成を同じ確率で生成するという事実を考慮します。最終的に、N ^ N可能性は等しくなりますが、N!順列があるだけで、通常の場合、前者は後者で割り切れないため、均一に分散することはできません。

実際、Jeff Attwood がここで説明していると思います。

コーディングホラー - ナイーブの危険性

于 2013-06-13T13:37:13.483 に答える
1

文字の配列をシャッフルするにはこれが必要です

このようなシャッフル コードをプリミティブに適応させることができます

public static void shuffle(char[] chars, Random rnd) {
    int size = chars.length;
    for (int i = size; i > 1; i--) {
        int idx = rnd.nextInt(i);
        char tmp = chars[idx];
        chars[idx] = chars[i-1];
        chars[i-1] = tmp;
    }
}

あなたはただすることができます

Collections.shuffle(Arrays.asList(array), random);

または、このコードを見ることができます。一時変数を 1 つ使用し、ランダムのサイズを小さくする方が効率的です。これを行う方法については Collections.shuffle を参照してください。

public static void shuffle(List<?> list, Random rnd) {
    int size = list.size();
    if (size < SHUFFLE_THRESHOLD || list instanceof RandomAccess) {
        for (int i=size; i>1; i--)
            swap(list, i-1, rnd.nextInt(i));
    } else {

public static void swap(List<?> list, int i, int j) {
    final List l = list;
    l.set(i, l.set(j, l.get(i)));
}

注：あなたはやっていますが(lastIndex+1)、lastIndexはarr.length - 1本当にこれだけですarr.length

于 2013-06-13T13:30:26.030 に答える