伪伪随机遍历 [英] Psuedo-Random Traversal of a Set

问题描述

我一直在阅读《游戏编码完成》(第4版)，但在理解有用的东西的袋子"中的伪随机遍历集合"路径时遇到一些问题第3章中的"部分.

I've been reading Game Coding Complete (4th Edition) and I'm having a few problems understanding the "Pseudo-Random Traversal of a Set" path in the "Grab Bag of Useful Stuff" section in Chapter 3.

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

Have you ever wondered how the "random" button on your CD player works? It will play every song on your CD randomly without playing the same song twice. That's a really useful solution for making sure players in your games see the widest variety of features like objects, effects, or characters before they have the chance of seeing the same ones over again.

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

After this description, it goes on to talk about an implementation in C++ that I've tried to implement in Java, but have been unable to replicate successfully. It also briefly describes how it works, but I don't get it either.

我找到了此 StackOverflow，它回答了类似的问题，但不幸的是，答案中的示例链接已经失效，我也不理解维基百科的文章，尽管对其所做的描述似乎可以描述我在寻找什么.

I found this StackOverflow answer to a similar question, but unfortunately the link to examples in the answer is dead and I don't understand the Wikipedia article either, although the description about what it does seems to describe what I'm looking for.

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

To be clear, I'm not looking for a way to randomly re-order a collection. I am looking for a way to randomly select an element from a collection exactly once before repeating.

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

Can someone explain how this behavior works and provide an example in Java? Thanks!

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

[EDIT] I figured it might be useful to have an excerpt of the implementation in here to help explain what I'm talking about.

这是它的工作方式.跳过值是通过选择三个大于零的随机值来计算的.这些值成为二次方的系数，并且将域值(x)设置为集合的序数值:

Here's how it works. A skip value is calculated by choosing three random values greater than zero. These values become the coefficients of the quadratic, and the domain value (x) is set to the ordinal value of the set:

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

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

Armed with this skip value, you can use this piece of code to traverse the entire set exactly once, in a pseudo-random order:

nextMember += skip;
nextMember %= prime;

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

The value of skip is so much larger than the number of members of your set that the chosen value seems to skip around at random. Of course, this code is inside a while loop to catch the case where the value chosen is larger than your set but still smaller than the prime number.

推荐答案

下面是一个示例，该示例显示了对一组字符进行随机排列的情况:

Here's an example of what this looks like in the case of getting a random permutation of a set of characters:

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:

Most of the conditions of the example from the book are present in the code example above, but with a few exceptions. First of all, if the skip is divisible by the prime number, than this algorithm doesn't work as it will only access index 0 due to this part of the code:

            nextMember += skip;
            nextMember %= prime;

第二，这三个系数在1和素数之间(包括1和2)，在范围之内，但这不是必须的.它可以是任何一个非零的正数，但是我发现如果这样做，我将出现整数溢出并得到一个负的跳跃值，这是行不通的.这种特殊情况可以通过采用跳过值的绝对值来解决.

Secondly, the three coefficients are in between the range of 1 and the prime number, inclusive, but this does not have to be the case. It can be any positive, non-zero number, but I find that if I do that I'll have integer overflow and get a negative skip value, which doesn't work. This particular case can be fixed by taking the absolute value of the skip value.

最后，您需要检查下一个成员是否在1到集合的长度(包括该长度)之间(包括端值在内)，然后在索引处获得比该数字少一个的成员.如果不这样做(如果仅检查数字是否小于集合的长度)，则每次运行程序，这很有趣，但对于随机遍历来说是不可取的.

Lastly, you need to check if the next member a number between 1 and the length of the set, inclusive, and then get the member at the index one less than that. If you don't do this (if you only check to see if the number is less than the length of the set), then you'll end up with the first element in the array at the end of each permutation whenever you run the program, which is interesting but undesirable for a random traversal.

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

The program will select a different index until all indexes are visited, and then it will repeat. When it repeats, the same permutation will be produced (which is how it's supposed to work), so if we wanted a different permutation, you would need to calculate a new skip value. The program works due to the properties of quadratic equations and primes. I can't explain it in detail without being doubtful of what I'm saying, and a more or less similar description is already present in the book.

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

I've run a slightly modified version of this program a couple of times on sets of 3 and 5 characters. For both, each permutation appears evenly, with an average absolute difference of 0.0413% and 0.000000466726%, respectively, from the average number of times expected for an even distribution. Both were run to produce 60 million samples. No permutations where characters are repeated are produced.

这篇关于伪伪随机遍历的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！