一个针对集合的伪随机遍历算法

Question

我一直在阅读《游戏编码完全手册（第4版）》，但我对第3章的“ Grab Bag of Useful Stuff”部分中“ Pseudo-Random Traversal of a Set”路径有一些困惑。

你是否曾经想过CD播放器上的“随机”按钮如何工作？它会随机播放CD上的每首歌曲，而不重复播放同一首歌曲。这是确保游戏玩家在看到相同元素之前先看到最广泛的对象、效果或角色等各种功能的非常有用的解决方案。

在描述完这一点后，它继续讨论了C++的实现方法。我试着在Java中实现它，但没有成功地复制它。它也简单描述了它的工作原理，但我也不明白。

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

明确一下，我不是在寻找一种重新排列集合的随机方法。我正在寻找一种从集合中随机选择一个元素，只选取一次后再重新开始的方法。

有人能解释一下它的工作原理并在Java中提供一个示例吗？谢谢！

[编辑] 我想把实现的摘录放在这里，以帮助解释我在说什么。以下是其工作原理。通过选择三个大于零的随机值计算跳过值。这些值成为二次方程的系数，域值（x）设置为集合的序数值：

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

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

nextMember += skip;
nextMember %= prime;

skip的值比你的集合成员数量大得多，所以选择的值似乎会随机跳过。当然，此代码位于while循环中，以捕捉选择的值大于你的集合但仍小于质数的情况。

- exodrifter

---

所以您想要以随机顺序显示项目，但不重新排序它们。我可以问一下原因吗？ - Baz

我正在尝试理解书中的示例。此外，如果我正确地理解了正在发生的事情，那么对于包含N个对象的集合进行洗牌将会随着N的增加而变得更加昂贵。 - exodrifter

@dpek 这就是我询问你意图的原因。自从你最后一次编辑以来，我们能够看到你为什么要这样做。 - Baz

有趣的是，nextMember += skip; nextMember %= prime;与nextMember = (nextMember + skip % prime) % prime;是相同的，换句话说，只是使用步长为skip % prime进行简单的步进。唯一让它看起来“随机”的是如果素数的大小显著大于数组的大小。这是非常糟糕的“随机”遍历方式。 - Nuoji

@Nuoji，是的，我相信这就是书的意图。它提到只有当质数显著大时（就像你说的那样），它才会看起来随机。 - exodrifter

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和长度），然后获取该索引减1处的成员。如果不这样做（如果只检查数字是否小于集合的长度），那么每次运行程序时，排列的第一个元素都会出现在数组的末尾，这很有趣，但对于随机遍历来说是不可取的。

程序将选择不同的索引，直到访问所有索引，然后重复执行。当它重复执行时，将生成相同的排列（这是它应该工作的方式），因此如果我们想要不同的排列，就需要计算新的跳过值。该程序由于二次方程和质数的特性而工作。我不能详细解释，否则我会对自己所说的话表示怀疑，而且书中已经有了一个或多个类似的描述。

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

- exodrifter

---

这一行是错误的：while (nextMember <= 0 && nextMember > chars.length)。应该改为 while (nextMember <= 0 || nextMember > chars.length)。 - Nuoji

Answer 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相同）

无论您选择什么数字，您都会看到此模式。

- Nuoji

Answer 3

从集合中随机选择不重复的元素，与对其进行洗牌并从洗牌后的列表中按顺序选择相同。

shuffled = shuffle(my_list);
first = pop(shuffled);
second = pop(shuffled);

- tskuzzy

---

洗牌方法是否是标准API的一部分，它是否会修改原始列表的顺序？ - Bobulous

@user1515834 是的，它是标准API的一部分。它在原地工作，因此原始列表将被更改。请参见：http://docs.oracle.com/javase/6/docs/api/java/util/Collections.html#shuffle(java.util.List) - Baz

@Baz 谢谢你，我之前很少使用过 Collections 类，所以没想到去那里找。 - Bobulous

Answer 4

我只需要通过在随机位置插入原始列表的成员来创建列表的副本，就像这样：

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替换为您的列表类型。）

- Bobulous

Answer 5

这是一个例子：

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副本中，以便我不会完全失去这些元素。最后，我将列表设置为副本，一切都恢复正常，您可以一遍又一遍地重复此过程。

- jrad

---

由于原始列表将不再可用，因此这与Collections.shuffle(list);具有完全相同的结果。 - Baz