我有一个数组，希望以随机顺序进行迭代。也就是说，我希望迭代只访问每个元素一次，并且以看起来随机的顺序进行。
是否可能实现一个迭代器，可以像这样迭代元素而不事先在查找表中存储顺序或其他数据？
是否可能对N维数组（其中N>1）执行此操作？
更新：一些答案提到了如何通过存储索引来完成此操作。该问题的主要重点是如何在不存储索引或其他数据的情况下完成它。
在伪随机顺序中迭代 N 维数组的算法
5
- Lennart Rolland
5
你的问题就是你的问题！“迭代”的定义：重复一组指令指定次数或直到达到特定结果的过程。-> 你最初的问题清楚地说：“我想以随机方式迭代”。所以，我们是随机迭代了若干次。然而，由于这是随机的，你需要记住已经访问过的地方，否则你的迭代就不再是迭代，而只是随机访问。是的，随机访问任意数量的地方没有问题。但如果你要迭代，你需要记住你访问过哪些地方。这类似于访问国家。 - T.S.
1我不得不提出异议，因为我知道有一种纯数学的解决方法，不需要存储超过几个种子数字。我只是不记得它的名字或实现的细节。由于我希望这对他人有用，所以决定在S.O上询问。 - Mr. Developerdude
请查看我的更新答案。再次强调，如果您进行真正的迭代或随机访问 - 您不需要保存已访问的位置。但如果您是随机迭代 - 那么您需要保存已访问的位置！ - T.S.
我知道有解决方案。好的，给我们解决方案。我们会等待的。:o) 嗯，我知道如何编程。数学...这是为爱因斯坦准备的。顺便说一句，如果你看看我的解决方案，你实际上并没有写入任何表格。你所做的只是从控制列表中删除已经访问过的项目。 - T.S.
@T.S. 我终于想起来了 :-D 请看下面的答案。 - Mr. Developerdude
4个回答
4
我决定解决这个问题，因为我非常烦恼自己记不起之前听过的解决方案的名字。最后我终于记起来了，更多详情请见本帖底部。
我的解决方案依赖于一些经过巧妙计算的数字的数学属性。
通过这种设置，我们可以重复计算以下内容，并以一种看似随机的顺序迭代数组的所有元素，之后它会循环以完全相同的顺序遍历数组。
我用Java实现并测试了这个，所以我决定将我的代码贴在这里，方便日后参考。
如上所述，在我花费了大部分晚上的时间得出结果后约10分钟，我确实记起了原始方法在哪里读到。它是在一个小型C实现的2D图形“溶解”效果中提到的，如《图形宝典》第1卷所述，这又是对称为“LFSR”的机制进行的2D适应，并进行了一些优化（维基百科文章在这里，原dissolve.c源代码在这里）。
我的解决方案依赖于一些经过巧妙计算的数字的数学属性。
range = array size
prime = closestPrimeAfter(range)
root = closestPrimitiveRootTo(range/2)
state = root
通过这种设置，我们可以重复计算以下内容，并以一种看似随机的顺序迭代数组的所有元素，之后它会循环以完全相同的顺序遍历数组。
state = (state * root) % prime
我用Java实现并测试了这个，所以我决定将我的代码贴在这里，方便日后参考。
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Random;
public class PseudoRandomSequence {
private long state;
private final long range;
private final long root;
private final long prime;
//Debugging counter
private int dropped = 0;
public PseudoRandomSequence(int r) {
range = r;
prime = closestPrimeAfter(range);
root = modPow(generator(prime), closestPrimeTo(prime / 2), prime);
reset();
System.out.println("-- r:" + range);
System.out.println(" p:" + prime);
System.out.println(" k:" + root);
System.out.println(" s:" + state);
}
// https://en.wikipedia.org/wiki/Primitive_root_modulo_n
private static long modPow(long base, long exp, long mod) {
return BigInteger.valueOf(base).modPow(BigInteger.valueOf(exp), BigInteger.valueOf(mod)).intValue();
}
//http://e-maxx-eng.github.io/algebra/primitive-root.html
private static long generator(long p) {
ArrayList<Long> fact = new ArrayList<Long>();
long phi = p - 1, n = phi;
for (long i = 2; i * i <= n; ++i) {
if (n % i == 0) {
fact.add(i);
while (n % i == 0) {
n /= i;
}
}
}
if (n > 1) fact.add(n);
for (long res = 2; res <= p; ++res) {
boolean ok = true;
for (long i = 0; i < fact.size() && ok; ++i) {
ok &= modPow(res, phi / fact.get((int) i), p) != 1;
}
if (ok) {
return res;
}
}
return -1;
}
public long get() {
return state - 1;
}
public void advance() {
//This loop simply skips all results that overshoot the range, which should never happen if range is a prime number.
dropped--;
do {
state = (state * root) % prime;
dropped++;
} while (state > range);
}
public void reset() {
state = root;
dropped = 0;
}
private static boolean isPrime(long num) {
if (num == 2) return true;
if (num % 2 == 0) return false;
for (int i = 3; i * i <= num; i += 2) {
if (num % i == 0) return false;
}
return true;
}
private static long closestPrimeAfter(long n) {
long up;
for (up = n + 1; !isPrime(up); ++up)
;
return up;
}
private static long closestPrimeBefore(long n) {
long dn;
for (dn = n - 1; !isPrime(dn); --dn)
;
return dn;
}
private static long closestPrimeTo(long n) {
final long dn = closestPrimeBefore(n);
final long up = closestPrimeAfter(n);
return (n - dn) > (up - n) ? up : dn;
}
private static boolean test(int r, int loops) {
final int array[] = new int[r];
Arrays.fill(array, 0);
System.out.println("TESTING: array size: " + r + ", loops: " + loops + "\n");
PseudoRandomSequence prs = new PseudoRandomSequence(r);
final long ct = loops * r;
//Iterate the array 'loops' times, incrementing the value for each cell for every visit.
for (int i = 0; i < ct; ++i) {
prs.advance();
final long index = prs.get();
array[(int) index]++;
}
//Verify that each cell was visited exactly 'loops' times, confirming the validity of the sequence
for (int i = 0; i < r; ++i) {
final int c = array[i];
if (loops != c) {
System.err.println("ERROR: array element @" + i + " was " + c + " instead of " + loops + " as expected\n");
return false;
}
}
//TODO: Verify the "randomness" of the sequence
System.out.println("OK: Sequence checked out with " + prs.dropped + " drops (" + prs.dropped / loops + " per loop vs. diff " + (prs.prime - r) + ") \n");
return true;
}
//Run lots of random tests
public static void main(String[] args) {
Random r = new Random();
r.setSeed(1337);
for (int i = 0; i < 100; ++i) {
PseudoRandomSequence.test(r.nextInt(1000000) + 1, r.nextInt(9) + 1);
}
}
}
如上所述，在我花费了大部分晚上的时间得出结果后约10分钟，我确实记起了原始方法在哪里读到。它是在一个小型C实现的2D图形“溶解”效果中提到的，如《图形宝典》第1卷所述，这又是对称为“LFSR”的机制进行的2D适应，并进行了一些优化（维基百科文章在这里，原dissolve.c源代码在这里）。
- Lennart Rolland
1
需要我几天时间来消化。希望我会有时间处理它。但我会检查。 - T.S.
0
你可以将所有可能的索引收集到一个列表中，然后删除一个随机索引以进行访问。我知道这有点像查找表，但我没有看到其他选择。
这是一个一维数组的示例（适应多个维度应该很容易）：
这是一个一维数组的示例（适应多个维度应该很容易）：
class RandomIterator<T> {
T[] array;
List<Integer> remainingIndeces;
public RandomIterator(T[] array) {
this.array = array;
this.remainingIndeces = new ArrayList<>();
for(int i = 0;i<array.length;++i)
remainingIndeces.add(i);
}
public T next() {
return array[remainingIndeces.remove((int)(Math.random()*remainingIndeces.size()))];
}
public boolean hasNext() {
return !remainingIndeces.isEmpty();
}
}
另外提一句：如果这段代码与性能有关，那么这种方法的性能将远不如意。因为如果你使用由数组支持的列表（链表也没用，因为索引访问是 O(n) 的），从列表中随机删除触发了复制。我建议使用查找结构（例如 Java 中的 HashSet），它存储所有访问过的索引以避免这个问题（尽管这正是你不想使用的）
编辑：另一种方法是复制该数组，并使用库函数对其进行洗牌，然后按线性顺序遍历它。如果你的数组不是很大，这似乎是最可读和最有效的选择。
- roookeee
1
嗨！我的问题有点含糊不清。我现在已经更新了它。我真的不想存储任何数据来完成这个任务。 - Mr. Developerdude
0
是的，这是可能的。想象一个三维数组（你不太可能使用更多）。这就像一个立方体，所有三条线连接的地方都是一个单元格。您可以使用字典将单元格枚举为1到N，您可以在循环中进行此初始化，并创建一个单元格列表以供随机抽取使用。
初始化
totalCells = ... (xMax * yMax * zMax)
index = 0
For (x = 0; x < xMax ; x++)
{
For (y = 0; y < yMax ; y++)
{
For (z = 0; z < zMax ; z++)
{
dict.Add(i, new Cell(x, y, z))
lst.Add(i)
i++
}
}
}
现在，你所要做的就是随机迭代。
Do While (lst.Count > 0)
{
indexToVisit = rand.Next(0, lst.Count - 1)
currentCell = dict[lst[indexToVisit]]
lst.Remove(indexToVisit)
// Do something with current cell here
. . . . . .
}
这是伪代码，因为您没有提到您使用的编程语言。
另一种方法是随机化3个（或任何您拥有的维度数量）列表，然后嵌套循环遍历它们 - 这最终将是随机的。
- T.S.
0
您需要创建一个伪随机数生成器，它可以生成从0到X-1的值，并在重复周期之前进行X次迭代，其中X是所有维度大小的乘积。我不知道是否有通用的解决方案来完成这个任务。以下是一种类型的随机数生成器的维基百科文章：
- rcgldr
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接