以伪随机顺序迭代 N 维数组的算法

Question

我有一个数组，我想以随机顺序迭代。也就是说，我希望我的迭代以看似随机的顺序仅访问每个元素一次。

是否可以实现一个迭代器来迭代这样的元素，而无需先将顺序或其他数据存储在查找表中？

是否可以对 N>1 的 N 维数组执行此操作？

更新：一些答案提到了如何通过存储索引来做到这一点。这个问题的一个要点是如何在不存储索引或其他数据的情况下做到这一点。

Answer 1

我决定解决这个问题，因为不记得我以前听过的解决方案的名称，这让我很恼火。不过，我最终还是记得了，更多内容在这篇文章的底部。

我的解决方案取决于一些巧妙计算的数字的数学特性

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 分钟，我确实记得我在哪里读到过关于这样做的原始方法。它是在 2D 图形“溶解”效果的小型 C 实现中实现的，如 Graphics Gems vol.1 中所述。1 反过来又是对 2D 的适应，并对称为“LFSR”的机制进行了一些优化（此处为维基百科文章，此处为原始溶解.c 源代码）。