求无需额外内存、可即时生成0~n索引的非顺序遍历算法

你需要的是无需修改原数组、O(1)内存开销、能即时生成唯一索引的非顺序遍历方法，以下是几种实用方案：

1. 线性同余全周期置换（适用于多数场景） #

通过线性同余公式生成覆盖所有索引的置换序列，每个索引仅出现一次，无需额外存储。

公式与参数要求 #

每次生成下一个索引的公式：

next_idx = (a * current_idx + c) % n

初始索引设为0，循环执行n次即可遍历所有元素。

要保证序列覆盖所有0到n-1的索引，参数需满足：

• 增量c与数组长度n互质（即两者的最大公约数为1）
• 乘数a-1能被n的所有质因数整除
• 若n是4的倍数，a-1也必须能被4整除

示例（n=8，全周期序列） #

取a=5，c=1，生成的索引序列为：
0 → 1 → 6 → 7 → 4 → 5 → 2 → 3
完全覆盖0-7的所有索引，无重复。

2. 位运算置换（适用于数组长度为2的幂） #

如果你的数组长度是2的幂（如8、16、32），可以用位运算快速生成伪随机置换：

next_idx = (current_idx * 5 + 1) % n

以n=8为例，序列会覆盖所有索引，且计算开销极低。

3. 固定模式非顺序遍历（简单易实现） #

如果不需要伪随机的乱序，仅需非升/降序的遍历，可采用以下固定模式：

• 对称跳跃遍历：先取第一个，再取最后一个，接着第二个，倒数第二个……
  索引生成公式（i从0到n-1）：

  idx = i // 2 if i % 2 == 0 else n - 1 - (i // 2)
  

• 奇偶分组遍历：先遍历所有奇数索引，再遍历偶数索引（或反之）
  索引生成公式（n为偶数时）：

  idx = 2*i + 1 if i < n//2 else 2*(i - n//2)
  

这些方法完全无需额外内存，直接计算即可，每个索引仅出现一次。

4. 通用伪随机置换（任意n） #

对于任意长度的数组，可选择与n互质的整数a和任意整数b，用公式f(x) = (a*x + b) % n生成置换。若该映射分解为多个循环，可依次遍历每个循环（仅需记录当前循环的起始点，内存开销仍为O(1)）。

比如n=10，选a=3，b=1，会得到两个循环：0→1→4→3→0和2→5→8→7→6→9→2，遍历完第一个循环后，切换到未遍历的起始点（如2）继续即可。

内容的提问来源于stack exchange，提问作者Golden appendages