Writing correct code is crucial, especially in JavaScript where subtle bugs can go unnoticed. Let’s explore how to verify and improve code correctness, using a shuffle algorithm as a case study.

The Shuffle Algorithm: A Case Study

Suppose we need to shuffle an array (e.g., a deck of cards). A naive approach might use Array.sort with a random comparator:

function naiveShuffle(arr) {
  return [...arr].sort(() => Math.random() - 0.5);
}

const deck = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
console.log(naiveShuffle(deck)); // Example output: [5, 2, 7, 0, 9, 1, 8, 3, 6, 4]

While this seems to work initially, is it fair (each element has equal probability of being in any position)?

Validating the Algorithm

To check fairness, we run the shuffle 1,000,000 times, summing values at each position. A fair algorithm should have similar sums across positions.

const iterations = 1000000;
const result = new Array(10).fill(0);
const originalDeck = [0, 9, 8, 7, 6, 5, 4, 3, 2, 1]; // Vary input for testing

for (let i = 0; i < iterations; i++) {
  const shuffled = naiveShuffle(originalDeck);
  shuffled.forEach((val, idx) => {
    result[idx] += val;
  });
}

console.log(result); // Example output (unfair): [3864521, 3863478, 4543210, ...] (shows bias)

The output shows a noticeable increase in sums (e.g., first and last positions differ significantly), indicating bias: larger numbers tend to end up later. This algorithm is unfair.

Improving Fairness: Iterative Shuffling

One workaround is to shuffle multiple times:

function multiShuffle(arr, times = 2) {
  let shuffled = [...arr];
  for (let t = 0; t < times; t++) {
    shuffled = naiveShuffle(shuffled);
  }
  return shuffled;
}

// Validation for 2 shuffles:
const result2 = new Array(10).fill(0);
for (let i = 0; i < iterations; i++) {
  const shuffled = multiShuffle(deck, 2);
  shuffled.forEach((v, j) => result2[j] += v);
}
console.log(result2); // More balanced sums

// For 3 shuffles:
const result3 = new Array(10).fill(0);
for (let i = 0; i < iterations; i++) {
  const shuffled = multiShuffle(deck, 3);
  shuffled.forEach((v, j) => result3[j] += v);
}
console.log(result3); // Even more balanced

Repeating shuffles reduces bias, but it’s not a fundamental fix.

Fundamental Fix: Random Sampling (Fisher-Yates Algorithm)

The root issue with sort is its pairwise comparison (not truly random). A better approach is random sampling (Fisher-Yates algorithm):

function fairShuffle(arr) {
  const shuffled = [...arr];
  for (let i = shuffled.length; i > 0; i--) {
    const randIdx = Math.floor(Math.random() * i);
    // Swap elements
    [shuffled[randIdx], shuffled[i - 1]] = [shuffled[i - 1], shuffled[randIdx]];
  }
  return shuffled;
}

This follows the "sampling without replacement" model, ensuring each element has an equal chance (1/n) of being in any position. Validating:

const fairResult = new Array(10).fill(0);
for (let i = 0; i < iterations; i++) {
  const shuffled = fairShuffle(deck);
  shuffled.forEach((v, j) => fairResult[j] += v);
}
console.log(fairResult); // Balanced sums

Applications of Correct Shuffling

Lottery System

To simulate a lottery (e.g., drawing 5 winners from 100), we use a generator to yield shuffled elements:

function* shuffledGenerator(items) {
  const temp = [...items];
  for (let i = temp.length; i > 0; i--) {
    const rand = Math.floor(Math.random() * i);
    [temp[rand], temp[i - 1]] = [temp[i - 1], temp[rand]];
    yield temp[i - 1];
  }
}

// Example: Draw 5 from 100 numbers
const lotteryNumbers = Array.from({ length: 100 }, (_, i) => i + 1);
let drawn = 0;
for (const num of shuffledGenerator(lotteryNumbers)) {
  console.log(num);
  if (++drawn >= 5) break;
}

Red Packet Distribution

In apps, distributing "red packets" (random amounts) without leaving insufficient funds:

Balanced Distribution (Guaranteed Fairness)

function splitEvenly(amount, count) {
  const parts = [amount];
  while (count > 1) {
    const largest = Math.max(...parts);
    const idx = parts.indexOf(largest);
    const split = 1 + Math.floor(Math.random() * (largest / 2));
    const remaining = largest - split;
    parts.splice(idx, 1, split, remaining);
    count--;
  }
  return parts;
}

Fun (Unbalanced) Distribution

To introduce randomness, split the amount by randomly choosing positions (like cutting a line):

function* shuffleGenerator(arr) {
  const temp = [...arr];
  for (let i = temp.length; i > 0; i--) {
    const rand = Math.floor(Math.random() * i);
    [temp[rand], temp[i - 1]] = [temp[i - 1], temp[rand]];
    yield temp[i - 1];
  }
}

function splitRandomly(amount, count) {
  if (count <= 1) return [amount];
  const positions = Array.from({ length: amount - 1 }, (_, i) => i + 1);
  const shuffled = shuffleGenerator(positions);
  const cuts = [];
  for (let i = 0; i < count - 1; i++) {
    cuts.push(shuffled.next().value);
  }
  cuts.sort((a, b) => a - b);
  const result = [cuts[0]];
  for (let i = 1; i < count - 1; i++) {
    result.push(cuts[i] - cuts[i - 1]);
  }
  result.push(amount - cuts[count - 2]);
  return result;
}

This ensures unpredictable (yet valid) red packet amounts.

Key Takeaway

Code correctness (e.g., fairness in algorithms) requires careful validation. The initial sort-based shuffle was flawed, but iterative shuffling or the Fisher-Yates algorithm fixes it. These techniques apply to real-world scenarios like lotteries and red packet distribution.