如何在JavaScript中打乱笛卡尔积迭代器的遍历顺序？

Awesome question—dealing with 100 million Cartesian product combinations without blowing up your memory is a super common pain point, and there's a smart way to do random traversal without generating every single item upfront. Here's how to pull it off:

Every combination in a Cartesian product maps to a unique integer index (from 0 to total_combinations - 1). Instead of generating all combinations and shuffling them (which is impossible for 1e8 items), we can:

1. Generate random, non-repeating integer indices (without storing all of them)
2. Convert each index directly to its corresponding Cartesian product combination on-the-fly

This keeps your memory usage minimal—you only need to store the original input arrays, not the entire product.

Let's break this down with JavaScript, since you're using the cartesian-product-generator npm package.

1. Calculate Total Combinations #

First, figure out how many total combinations you're dealing with. For 4 arrays each of length 100, that's 100 * 100 * 100 * 100 = 100,000,000 (totally manageable as a JavaScript Number, since it's well under 2^53).

// Your input arrays (example values)
const inputArrays = [
  Array.from({ length: 100 }, (_, i) => `A${i}`),
  Array.from({ length: 100 }, (_, i) => `B${i}`),
  Array.from({ length: 100 }, (_, i) => `C${i}`),
  Array.from({ length: 100 }, (_, i) => `D${i}`)
];

// Get lengths of each input array
const arrayLengths = inputArrays.map(arr => arr.length);

// Calculate total number of combinations
const totalCombinations = arrayLengths.reduce((acc, len) => acc * len, 1);

2. Generate Non-Repeating Random Indices #

Storing all 1e8 indices is impossible, so we use a pseudo-random number generator (PRNG) with a full cycle (meaning it will produce every index exactly once before repeating). A Linear Congruential Generator (LCG) works great here—just pick parameters that ensure the cycle matches your total combination count.

function* randomIndexGenerator(total) {
  // Start with a random seed (uses crypto for better randomness)
  let currentIndex = crypto.getRandomValues(new Uint32Array(1))[0] % total;
  
  // Track seen indices (only necessary if you need to guarantee no repeats for partial traversal)
  // For full traversal, the LCG will cycle through all indices without repeats, so you can omit this set
  const seenIndices = new Set();

  while (seenIndices.size < total) {
    if (!seenIndices.has(currentIndex)) {
      seenIndices.add(currentIndex);
      yield currentIndex;
    }
    // LCG parameters (tuned for good randomness and full cycle coverage)
    currentIndex = (currentIndex * 1664525 + 1013904223) % total;
  }
}

3. Convert Indices to Cartesian Product Combinations #

Now we need to map each integer index back to the corresponding combination. This works by reversing how Cartesian product indices are calculated: each index can be split into "coordinates" that point to elements in your input arrays.

function indexToCombination(index, arrays, lengths) {
  let remaining = index;
  const combination = [];

  // Iterate from the last array to the first (matches the order of cartesian-product-generator)
  for (let i = arrays.length - 1; i >= 0; i--) {
    const currentLength = lengths[i];
    // Get the index of the element in the current array
    const elementIndex = remaining % currentLength;
    // Add the element to the start of the combination array
    combination.unshift(arrays[i][elementIndex]);
    // Reduce the remaining index for the next array
    remaining = Math.floor(remaining / currentLength);
  }

  return combination;
}

4. Use It! #

Now you can generate random combinations on demand, with zero memory overhead for the full product:

// Initialize the index generator
const indexGenerator = randomIndexGenerator(totalCombinations);

// Grab a single random combination
const randomIdx = indexGenerator.next().value;
const randomCombo = indexToCombination(randomIdx, inputArrays, arrayLengths);
console.log("Random combination:", randomCombo);

// Or iterate through all combinations in random order
for (const idx of indexGenerator) {
  const combo = indexToCombination(idx, inputArrays, arrayLengths);
  // Do whatever you need with the combination here
}

• Partial Traversal: If you don't need to iterate all combinations, skip the seenIndices set—just generate random indices with Math.floor(Math.random() * totalCombinations). The chance of repeats is negligible if you're only sampling a small portion of the total.
• Big Numbers: If your total combinations exceed 2^53 (JavaScript's safe integer limit), switch to BigInt for all index calculations to avoid precision loss.
• Matching Generator Order: The indexToCombination function is tuned to match the order of cartesian-product-generator. If you need to verify, generate the first few combinations with the library and cross-check against the index 0, 1, etc., from your conversion function.

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