我有一个给定大小的数组。我想以伪随机顺序遍历它，保持数组完整并访问每个元素一次。如果当前状态可以存储在几个整数中，那将是最好的。
我知道you can't have full randomness without storing full array，但我不需要命令是非常随意的。我需要它被用户视为随机的。解决方案应该使用子线性空间。
一个可能的建议 - 使用大素数 - 是given here。该解决方案的问题在于存在明显的固定步骤（采用模块阵列大小）。我更喜欢一种不是非随机的解决方案。有更好的解决方案吗？
这个算法怎么样？
伪伪随机遍历大小为n的数组。
k越高，你获得的随机性就越高。此方法将允许您延迟从素数方法生成数字。
通过创建另一个数组“skip-list”，可以采用类似的方法在序列中生成比预期更早的数字。在序列中稍后随机选择项目，使用它们遍历下一个位置，然后将它们添加到跳过列表中。当它们自然到达时，它们在跳过列表中被搜索并被抑制，然后从跳过列表中删除，此时您可以将另一个项目随机添加到跳过列表中。
如果你可以得到一个你可以控制的最大周期的随机生成器，那么模拟一个随机播放的想法很好。
Linear Congruential Generator使用以下公式计算随机数：
x[i + 1] = (a * x[i] + c) % m;
最大周期为m，并且在以下属性成立时实现：
我的第一稿涉及在数组长度之后将m作为4的下一个倍数，然后找到合适的a和c值。这是（a）很多工作和（b）有时产生非常明显的结果。
我重新考虑过这种方法。我们可以使m成为数组长度适合的2的最小幂.m的唯一主要因子是2，这将使每个奇数对应于它。除了1和2之外，m将被4整除，这意味着我们必须使-1为4的倍数。
m大于数组长度意味着我们必须丢弃所有非法数组索引的值。这种情况最多每隔一个转折就会发生，应该可以忽略不计。
以下代码生成伪随机数，其周期为exaclty m。我已经避免了a和c以及我的（不是太多）现场cheks的微不足道的值，结果看起来没问题。至少没有明显的骑车模式。
所以：
class RandomIndexer
{
public:
RandomIndexer(size_t length) : len(length)
{
m = 8;
while (m < length) m <<= 1;
c = m / 6 + uniform(5 * m / 6);
c |= 1;
a = m / 12 * uniform(m / 6);
a = 4*a + 1;
x = uniform(m);
}
size_t next()
{
do { x = (a*x + c) % m; } while (x >= len);
return x;
}
private:
static size_t uniform(size_t m)
{
double p = std::rand() / (1.0 + RAND_MAX);
return static_cast<int>(m * p);
}
size_t len;
size_t x;
size_t a;
size_t c;
size_t m;
};
然后你可以像这样使用生成器：
std::vector<int> list;
for (size_t i = 0; i < 3; i++) list.push_back(i);
RandomIndexer ix(list.size());
for (size_t i = 0; i < list.size(); i++) {
std::cout << list[ix.next()]<< std::endl;
}
我知道这仍然不是一个伟大的随机数生成器，但它相当快，不需要数组的副本，似乎工作正常。
如果选择a和c的方法随机产生不良结果，那么将发生器限制为2的幂并且硬编码已被证明是好的文献值可能是个好主意。
正如其他人所指出的，你可以通过改组一系列数组索引然后跟随它来创建一种“飞行计划”。这违反了“如果当前状态可以存储在几个整数中将是最好的”约束，但它真的重要吗？是否有严格的性能限制？毕竟，我相信如果你不接受重复，那么你需要存储你已经访问过的地方或某种方式。
或者，您可以选择侵入式解决方案并在阵列的每个元素中存储bool，告诉您元素是否已被选中。这可以通过使用继承（根据需要多个）以几乎干净的方式完成。
该解决方案存在许多问题，例如线程安全，当然它违反了“保持数组完整”的约束。
您提到的二次残差（“使用大素数”）是众所周知的，可以正常工作，并保证每个元素只迭代一次（如果需要，但似乎并非严格的情况？）。不幸的是，他们不是“非常随机的”，除了成为它的主要工作之外，模数还有一些其他要求。 Jeff Preshing的网站上有一个页面详细描述了该技术并向feed the output of the residue generator into the generator again with a fixed offset建议。
但是，由于您说您只需要“被用户视为随机”，因此您似乎可以使用连续整数来提供哈希函数（例如，cityhash或siphash）。输出将是一个“随机”整数，并且至少到目前为止将存在严格的1：1映射（因为存在比输入更多可能的散列值）。
现在的问题是你的数组很可能不那么大，所以你需要以某种方式减少这些生成的索引的范围而不产生重复（这很难）。
显而易见的解决方案（采用模数）将无法工作，因为它几乎可以保证您获得大量重复。
使用位掩码将范围限制为下一个更大的2的幂应该在不引入偏差的情况下工作，并且丢弃超出范围的索引（生成新索引）也应该起作用。请注意，这需要非确定性时间 - 但这两者的组合平均应该可以很好地工作（最多尝试几次）。
否则，“真正有效”的唯一解决方案是改变Kamil Kilolajczyk指出的一系列指数（虽然你不想这样）。
这是一个java解决方案，可以很容易地转换为C ++，类似于上面的M Oehm解决方案，尽管选择LCG参数的方式不同。
import java.util.Enumeration;
import java.util.Random;
public class RandomPermuteIterator implements Enumeration<Long> {
int c = 1013904223, a = 1664525;
long seed, N, m, next;
boolean hasNext = true;
public RandomPermuteIterator(long N) throws Exception {
if (N <= 0 || N > Math.pow(2, 62)) throw new Exception("Unsupported size: " + N);
this.N = N;
m = (long) Math.pow(2, Math.ceil(Math.log(N) / Math.log(2)));
next = seed = new Random().nextInt((int) Math.min(N, Integer.MAX_VALUE));
}
public static void main(String[] args) throws Exception {
RandomPermuteIterator r = new RandomPermuteIterator(100);
while (r.hasMoreElements()) System.out.print(r.nextElement() + " ");
//output:50 52 3 6 45 40 26 49 92 11 80 2 4 19 86 61 65 44 27 62 5 32 82 9 84 35 38 77 72 7 ...
}
@Override
public boolean hasMoreElements() {
return hasNext;
}
@Override
public Long nextElement() {
next = (a * next + c) % m;
while (next >= N) next = (a * next + c) % m;
if (next == seed) hasNext = false;
return next;
}
}