4

Game Coding Complete（4th Edition）を読んでいて、第3章の「GrabBagofUsefulStuff」セクションの「Pseudo-RandomTraversalofaSet」パスを理解するのにいくつか問題があります。

CDプレーヤーの「ランダム」ボタンがどのように機能するのか疑問に思ったことはありませんか。同じ曲を2回再生することなく、CDのすべての曲をランダムに再生します。これは、ゲーム内のプレーヤーが同じ機能を何度も見る前に、オブジェクト、エフェクト、キャラクターなどのさまざまな機能を確認するための非常に便利なソリューションです。

この説明の後、Javaで実装しようとしたが、正常に複製できなかったC++での実装について説明します。また、それがどのように機能するかについても簡単に説明していますが、私もわかりません。

私は同様の質問に対するこのStackOverflowの回答を見つけましたが、残念ながら回答の例へのリンクは無効であり、ウィキペディアの記事も理解していません。

明確にするために、私はコレクションをランダムに並べ替える方法を探していません。繰り返す前に、コレクションから要素を1回だけランダムに選択する方法を探しています。

誰かがこの動作がどのように機能するかを説明し、Javaで例を提供できますか？ありがとう！

[編集]私が話していることを説明するのに役立つように、ここに実装の抜粋があると便利かもしれないと思いました。

仕組みは次のとおりです。スキップ値は、ゼロより大きい3つのランダムな値を選択することによって計算されます。これらの値は2次の係数になり、定義域の値（x）はセットの序数に設定されます。

Skip = RandomA * (members * members) + (RandomB * members) + RandomC

このスキップ値を使用すると、このコードを使用して、疑似ランダムな順序でセット全体を1回だけトラバースできます。

nextMember += skip;
nextMember %= prime;

スキップの値は、セットのメンバーの数よりもはるかに大きいため、選択した値はランダムにスキップしているように見えます。もちろん、このコードはwhileループ内にあり、選択した値がセットよりも大きいが素数よりも小さい場合をキャッチします。

4

5 に答える 5

7

文字のセットのランダム順列を取得した場合のこれがどのように見えるかの例を次に示します。

public static void main(String[] args) {
    // Setup
    char[] chars = { 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j' };
    int prime = 11; // MUST be greater than the length of the set
    int skip = 0;
    int nextMember = 0;

    // If the skip value is divisible by the prime number, we will only access
    // index 0, and this is not what we want.
    while (skip % prime == 0) {
        // Generate three random positive, non-zero numbers
        int ra = new Random().nextInt(prime) + 1;
        int rb = new Random().nextInt(prime) + 1;
        int rc = new Random().nextInt(prime) + 1;
        skip = ra * chars.length * chars.length + rb * chars.length + rc;
    }

    String result = "";
    for (int x = 0; x < chars.length; x++) {
        do {
            nextMember += skip;
            nextMember %= prime;
        } while (nextMember <= 0 || nextMember > chars.length);
        result += chars[nextMember - 1];
    }

    // Print result
    System.out.println(result);
}

この本の例の条件のほとんどは、上記のコード例に含まれていますが、いくつかの例外があります。まず、スキップが素数で割り切れる場合、コードのこの部分のためにインデックス0にのみアクセスするため、このアルゴリズムは機能しません。

            nextMember += skip;
            nextMember %= prime;

次に、3つの係数は、1から素数までの範囲内にありますが、そうである必要はありません。ゼロ以外の正の数値でもかまいませんが、そうすると整数のオーバーフローが発生し、負のスキップ値が得られますが、これは機能しません。この特定のケースは、スキップ値の絶対値を取得することで修正できます。

最後に、次のメンバーが1からセットの長さまでの数であるかどうかを確認してから、インデックスのメンバーをそれより1つ少なくする必要があります。これを行わない場合（数がセットの長さよりも短いかどうかを確認するだけの場合）、実行するたびに、各順列の最後に配列の最初の要素が表示されます。プログラム。これは興味深いですが、ランダムなトラバーサルには望ましくありません。

プログラムは、すべてのインデックスにアクセスするまで別のインデックスを選択し、その後繰り返します。それが繰り返されると、同じ順列が生成されます（これが機能するはずです）。したがって、別の順列が必要な場合は、新しいスキップ値を計算する必要があります。このプログラムは、二次方程式と素数の特性により機能します。私が言っていることを疑わずにそれを詳細に説明することはできません、そして多かれ少なかれ同様の説明がすでに本に存在しています。

このプログラムのわずかに変更されたバージョンを、3文字と5文字のセットで数回実行しました。どちらの場合も、各順列は均等に表示され、均等な分布で予想される平均回数との平均絶対差は、それぞれ0.0413％と0.000000466726％です。両方とも実行され、6000万のサンプルが生成されました。文字が繰り返される順列は生成されません。

于 2012-08-03T15:55:36.467 に答える
2

このアルゴリズムは、実際にはランダムまたはランダムに見えるものとはかけ離れています。

このメソッドは単純に、skip % prime の期間でステップ実行し、array.length の外側にあるすべての値を削除します。

小さな素数を使用すると、パターンを簡単に作成できます。

配列に入力し[0, 1, 2, 3..., 9]、係数 3、5、7 - 素数 11 を選択すると、753 のスキップが得られます。ただし、753 % 11は 5 であるため、実際のステップは 5 です。

結果（実装を使用）は

[4, 9, 3, 8, 2, 7, 1, 6, 0, 5]

ここで手順を確認できます。

+5、-6、+5、-6、+5、-6、+5、-6、+5

(-6 は (x + 5) % 11 に由来し、6 <= x <= 10 の場合は x - 6 と同じです)

どの番号を選択しても、このパターンが表示されます。

于 2013-03-22T09:17:14.730 に答える
1

コレクションから繰り返しのない要素をランダムに選択することは、それをシャッフルして、シャッフルされたリストから順番に選択することと同じです。

shuffled = shuffle(my_list);
first = pop(shuffled);
second = pop(shuffled);
于 2012-08-01T19:04:37.677 に答える
1

次のように、元のリストのメンバーをランダムな位置に挿入して、リストのコピーを作成します。

List<T> randomOrder = new ArrayList<T>(original.size());
Random rand = new Random();
int currentSize = 0;
for (T member : original) {
    randomOrder.add(rand.nextInt(++currentSize), member);
}

したがって、 randomOrder は元のリストのコピーになるはずですが、異なるランダムな順序になります。元のリストは影響を受けません。(明らかに、T をリストのタイプに置き換えます。)

于 2012-08-01T19:08:39.047 に答える
0

次に例を示します。

import java.util.*;

public class Randy {

    public static void main(String[] args) {
        ArrayList<String> list = new ArrayList<String>();
        ArrayList<String> copy = new ArrayList<String>();
        list.add("Jack");
        list.add("Tess");
        list.add("Alex");
        list.add("Jeff");
        list.add("Kelli");
        Random randy = new Random();
        int size = list.size();
        for(int i = 0; i < size; i++) {
            int r = randy.nextInt(list.size());
            System.out.println(list.get(r));
            copy.add(list.get(r));
            list.remove(r);
        }
        list = copy;
        copy.clear();
    }

}

ここに、文字列オブジェクトで構成される ArrayList リストがあります。次に for ループで、これらの文字列をランダムな順序で出力し、ランダムに選択された要素をリストから削除して、出力が繰り返されないようにします。ただし、要素を削除する前に、それを別の ArrayList に追加してコピーするので、要素が完全に失われることはありません。最後に list を copy に設定すると、すべてが復元され、このプロセスを何度も繰り返すことができます。

于 2012-08-01T19:09:44.393 に答える