Psuedo-Random Traversal of a Set

Question

我一直在阅读游戏编码完成(第4版),我在第3章的"Grab Bag of Useful Stuff"部分中理解"Set的伪随机遍历"路径时遇到了一些问题.

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

在此描述之后,它继续讨论我尝试在Java中实现的C++实现,但是无法成功复制.它还简要描述了它是如何工作的,但我也没有得到它.

我发现这个 StackOverflow回答了一个类似的问题,但不幸的是,答案中的示例链接已经死了,我也不理解维基百科的文章,尽管关于它的内容的描述似乎描述了我正在寻找的内容.

要清楚,我不是在寻找一种随机重新订购集合的方法.我正在寻找一种方法,在重复之前从集合中选择一个元素.

有人可以解释这种行为是如何工作的并在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之间的数字和集合的长度(包括1),然后使索引处的成员少于该成员.如果你不这样做(如果你只检查数字是否小于集合的长度),那么无论何时运行,你都会在每个排列结束时得到数组中的第一个元素.程序,这是有趣的,但随机遍历是不可取的.

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

我在3和5个字符的集合上运行了几次这个程序的略微修改版本.对于两者,每个排列均匀地出现,平均绝对差异分别为0.0413%和0.000000466726%,与均匀分布的平均预期次数相比.两者都用于生产6000万个样品.不产生重复字符的排列.