O(1)空间下伪随机生成排列的实现方案及原理咨询

Awesome question—you’re already thinking in the right direction by targeting permutation generators that skip shuffling and memory overhead; this is exactly the kind of high-performance approach used in systems where fairness and speed are critical. Let’s break down your current generator, how it works, how to optimize it, and better alternatives to consider.

Your generator P(x) = ((x ^ mask) ^ (x << z) + y) & mask (where mask = next_pow2(N) - 1) relies on creating a bijection (one-to-one and onto function) over the 2^k elements in the power-of-two space defined by mask. For a function to generate a full permutation of these elements, it must map every input to a unique output, with no duplicates or gaps—this makes it reversible, which is the key property of a permutation.

Let’s unpack the operations:

• x ^ mask: This flips all bits of x within the mask’s bit width (since mask is a sequence of 1s).
• x << z: Left-shifts x by z bits, truncating to the mask width (so high bits are discarded).
• Combining these with XOR and adding y (mod 2^k via the final & mask) creates a function that, if designed correctly, shuffles bits in a way that no two inputs produce the same output.

To ensure your generator produces a valid permutation (no duplicate elements in the sequence), follow these guidelines:

• Choosing z:
  • Pick z such that the combination of x << z and x ^ mask creates a unique bit pattern for every input. A safe bet is to select z as an integer coprime with k (where 2^k is your next power of two). For example, if k=4 (mask=0xf), z=1, 3 work well (since they share no common factors with 4 besides 1). Avoid z values that are multiples of k, as this would lead to redundant bit shifts.
  • Even if z isn’t coprime with k, testing small values (1 to k-1) will often yield valid permutations—you can verify this by checking if every input maps to a unique output for your target k.
• Choosing y:
  • y can be any integer between 0 and mask (inclusive). Adding y mod 2^k acts as a cyclic shift on the permutation, so different y values will produce distinct permutations (even for the same z).
  • To avoid duplicate permutations across runs, pair unique (z, y) pairs with your seed—since your seed comes from an independent PRNG, just generate z and y directly from it (e.g., take bits from the seed to pick z, and remaining bits for y).

While your generator is solid, here are some optimized, battle-tested approaches to consider:

• LCG Permutations: Linear Congruential Generators (LCGs) can be designed as permutations for power-of-two moduli. For mask = 2^k, use an LCG of the form:

  x = (a * x + c) & mask;
  

  where a ≡ 1 mod 4 (e.g., a=5, 9, 13) and c is odd. This is extremely fast (only multiplication and addition) and guarantees a full permutation of the 2^k elements.
• Xorshift Permutations: Xorshift generators are designed to be fast and produce high-quality permutations. A simple 32-bit example is:

  x ^= x << 13;
  x ^= x >> 17;
  x ^= x << 5;
  

  For your use case, truncate to your mask width after each operation. Xorshift permutations are well-researched and avoid the rejection sampling step if you can work with a power-of-two N (or still use rejection for non-power-of-two N).
• Avoiding Rejection Overhead: If N is close to a power of two (e.g., N=15, mask=15), rejection sampling is trivial. For N much smaller than mask, you can adjust your generator to map the 2^k space to N directly using a technique like x = (x * N) >> k (this is a form of range reduction that avoids rejection, though it introduces a tiny bias—often acceptable for fairness).

Your current approach of discarding values > N is valid (rejection sampling). To minimize overhead:

• Calculate mask = next_pow2(N) - 1 once per run.
• When generating each element, if the result is < N, use it; otherwise, skip to the next generated value.
• For most practical cases, the overhead of rejection is negligible—for example, N=10 (mask=15) has a 25% rejection rate, which is manageable in high-performance scenarios.

To dive deeper into permutation generators and pseudorandom number theory:

• The Art of Computer Programming, Volume 2 (Seminumerical Algorithms) by Donald Knuth: The definitive guide to PRNGs, permutations, and all related mathematical foundations.
• Xorshift RNGs by George Marsaglia: The original paper that introduced Xorshift generators, including details on their permutation properties.
• Random Number Generation and Monte Carlo Methods by James E. Gentle: A practical resource covering PRNG design and use cases, including permutation-based sampling.

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