在O（1）内存中的随机序列迭代？ [英] Random sequence iteration in O(1) memory?

问题描述

假设您要以随机顺序迭代序列[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.

这篇关于在O（1）内存中的随机序列迭代？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！