如果您可以获得最大周期可控的随机生成器来模拟洗牌，那么这个想法是不错的。
线性同余生成器使用以下公式计算随机数：
x[i + 1] = (a * x[i] + c) % m;
我的初稿涉及将m设为数组长度之后的下一个4的倍数，并找到合适的a和c值。这既费时又明显得不出什么结果。
我重新考虑了这个方案。我们可以将m设为数组长度刚好能够容纳的最小2的幂。那么只有2是m的质因数，这将使得所有奇数和m互质。除了1和2外，m将是4的倍数，这意味着我们必须让a-1是4的倍数。
将m设置为大于数组长度的值会导致我们需要放弃所有非法的数组索引值。这种情况最多会每隔一次出现一次，并且应该可以忽略不计。
以下代码生成的伪随机数的周期为m。我避免使用了简单的a和c值，并在我的（不太多的）现场检查中，结果看起来还不错。至少没有明显的循环模式。
所以：
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;
}
while (p*p < m) 这个条件就足够了吗？如果有一个更大的质数能整除m怎么办？例如，956 = 4 * 239，而你的算法（如果我检查正确）得出a=5，这是错误的。 - Michal这个算法怎么样？
为了伪随机遍历大小为n的数组，可以采用以下步骤：
k越高，获得的随机性就越大。这种方法将使您延迟使用质数方法生成数字。
类似的方法也可用于提前生成序列中的数字，只需创建另一个名为“跳表”的数组即可。随机选择序列后面的项目，使用它们来遍历下一个位置，然后将它们添加到跳表中。当它们自然到达时，会在跳表中搜索并禁止它们，然后从跳表中移除，此时您可以随机添加另一个项目到跳表中。
这里有一个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;
}
}
正如其他人指出的那样，您可以通过打乱数组索引的方式创建一种“飞行计划”，然后按照它进行操作。这违反了“最好能够用几个整数存储当前状态”的约束，但这真的很重要吗？有严格的性能限制吗？毕竟，我认为如果您不接受重复，那么您需要在某个地方或以某种方式存储已经访问过的项目。
或者，您可以选择一种侵入式解决方案，并在数组的每个元素中存储一个bool，告诉您该元素是否已被选择。可以通过继承（根据需要多次）以几乎干净的方式完成此操作。
这种解决方案带来了许多问题，例如线程安全性，当然也违反了“保持数组完整”的约束。
显而易见的解决方案（取模）不起作用，因为它几乎保证会产生大量重复。
使用位掩码将范围限制在下一个更大的二次幂上应该可以避免引入偏差，并且丢弃超出边界的索引（生成新索引）也应该可以工作。请注意，这需要非确定性时间--但是这两个组合应该在平均情况下工作得相当好（最多尝试几次）。
否则，“真正有效”的解决方案就是像Kamil Kilolajczyk指出的那样对索引数组进行洗牌（尽管您不想要那样做）。