集的伪随机遍历

Question

我一直在阅读《 游戏编码完成》（第4版） ，但在理解第3章“有用的东西的袋子”一节中的“一组伪随机遍历”路径时遇到一些问题。

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

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

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

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

[ 编辑 ]我认为在这里摘录一个实现可能会有用，以帮助解释我在说什么。

运作方式如下。跳过值是通过选择三个大于零的随机值来计算的。这些值成为二次方的系数，并且域值（x）设置为集合的序数值：

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

有了此跳过值，您可以使用以下代码以伪随机顺序将整个集合精确遍历一次：

nextMember += skip;
nextMember %= prime;

skip的值比集合中成员的数量大得多，以至于所选的值似乎随机地跳来跳去。当然，此代码在while循环内，以捕获所选值大于您的设置但仍小于质数的情况。

Answer 1

这是获得一组字符的随机排列的情况下的示例：

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和2），但不是必须这样。它可以是任何一个非零的正数，但是我发现如果这样做，我将出现整数溢出并得到一个负的跳跃值，这是行不通的。这种特殊情况可以通过采用跳过值的绝对值来解决。

最后，您需要检查下一个成员是否在1到集合的长度（包括端值）之间（包括1和2），然后使该成员的索引比其小1。如果您不这样做（如果您仅检查数字是否小于集合的长度），那么每次运行程序，这很有趣，但是对于随机遍历是不希望的。

程序将选择一个不同的索引，直到访问了所有索引，然后重复执行。当它重复时，将产生相同的排列（这应该是这样工作的），因此，如果我们想要不同的排列，则需要计算一个新的跳过值。该程序的工作归因于二次方程和素数的性质。在不怀疑我在说什么的情况下，我无法详细解释它，并且本书中已经存在或多或少的类似描述。

我已经在3个和5个字符的集合上运行了该程序的稍微修改的版本。对于这两种情况，每个排列均匀出现，与平均分布预期的平均次数相比，平均绝对差分别为0.0413％和0.000000466726％。两家公司都生产了六千万个样品。没有产生重复字符的排列。