在O（1）内存中的随机序列迭代？

本文介绍了在O（1）内存中的随机序列迭代？的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

假设您要以随机顺序迭代序列[0到n]，每次访问每个元素一次。有没有办法在 （1）内存，即不使用 std :: iota 创建[1..n]并通过 std :: random_shuffle ？

Say you want to iterate over a sequence [0 to n] in a random order, visiting every element exactly once. Is there any way to do this in O(1) memory, i.e. without creating an [1..n] sequence with std::iota and running it through std::random_shuffle?

运行它。某种迭代器以随机顺序排列序列

Some kind of iterator spitting out the sequence in a random order would be optimal.

要求是可以通过选择另一个种子来获得另一个随机顺序。

A requirement is that it should be possible to get another random order by picking another seed.

推荐答案

在理论上，如果你构建一个随机数生成器，其周期恰好为 n ，并覆盖0..n中的所有值，给你你喜欢什么。

In theory, if you built a random number generator whose period was exactly n, and covered all values in 0..n, then running through this once would give you what you like.

当然，这可能不是一个一般的解决方案，至少如果你正在寻找一些动态，因为你必须预先创建PRNG和你如何做这取决于n。

Of course, this may not be a general solution, at least if you are looking for something dynamic, since you would have to pre-create the PRNG and how you do this depends on n.