4

我一直在阅读Game Coding Complete（第 4 版），但在第 3 章的“Grab Bag of Useful Stuff”部分中理解“Pseudo-Random Traversal of a Set”路径时遇到了一些问题。

您有没有想过 CD 播放器上的“随机”按钮是如何工作的？它会随机播放您 CD 上的每首歌曲，而不会将同一首歌曲播放两次。这是一个非常有用的解决方案，可以确保游戏中的玩家在有机会再次看到相同的特征之前看到最广泛的特征，例如对象、效果或角色。

在此描述之后，它继续讨论我尝试在 Java 中实现但无法成功复制的 C++ 实现。它还简要描述了它的工作原理，但我也不明白。

我发现这个StackOverflow 回答了一个类似的问题，但不幸的是，答案中的示例链接已经失效，我也不理解 Wikipedia 文章，尽管关于它所做的描述似乎描述了我正在寻找的内容。

需要明确的是，我不是在寻找一种随机重新排序集合的方法。我正在寻找一种在重复之前从集合中随机选择一个元素的方法。

有人可以解释这种行为是如何工作的并提供一个 Java 示例吗？谢谢！

[编辑] 我认为在此处摘录实现可能很有用，以帮助解释我在说什么。

这是它的工作原理。通过选择三个大于零的随机值来计算跳过值。这些值成为二次的系数，域值 (x) 设置为集合的序数值：

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

有了这个跳过值，您可以使用这段代码以伪随机顺序遍历整个集合一次：

nextMember += skip;
nextMember %= prime;

skip 的值远大于集合中的成员数，以至于所选值似乎随机跳过。当然，这段代码在一个 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;

其次，三个系数介于 1 和素数之间，包括 1 和素数，但不一定如此。它可以是任何正的、非零的数字，但我发现如果我这样做，我将有整数溢出并得到一个负的跳过值，这是行不通的。这种特殊情况可以通过获取跳跃值的绝对值来解决。

最后，您需要检查下一个成员是否是介于 1 和集合长度（含）之间的数字，然后获取索引处的成员比该数字小一。如果您不这样做（如果您只检查数字是否小于集合的长度），那么无论何时运行程序，这很有趣，但对于随机遍历是不可取的。

该程序将选择一个不同的索引，直到所有索引都被访问，然后它会重复。当它重复时，将产生相同的排列（这是它应该如何工作的），所以如果我们想要一个不同的排列，你需要计算一个新的跳过值。该程序由于二次方程和素数的特性而起作用。我无法详细解释它而不怀疑我在说什么，并且或多或少类似的描述已经出现在书中。

我已经在 3 个和 5 个字符的集合上运行了这个程序的一个稍微修改过的版本。对于这两种情况，每个排列都是均匀分布的，与平均分布的预期平均次数相比，平均绝对差分别为 0.0413% 和 0.000000466726%。两者都运行以产生 6000 万个样本。不会产生重复字符的排列。

于 2012-08-03T15:55:36.467 回答
2

该算法实际上与随机或随机外观相去甚远。

这种方法只是简单地使用一段跳过 % 素数的周期，然后删除位于 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，复制，所以我不会完全丢失元素。最后，我将列表设置为复制，一切都恢复了，你可以一遍又一遍地重复这个过程。

于 2012-08-01T19:09:44.393 回答