How Lodash _.shuffle Randomizes Elements

The _.shuffle method in the Lodash JavaScript library creates an array of shuffled values from any collection using a version of the Fisher-Yates shuffle algorithm. This article breaks down the internal mechanics of _.shuffle, explaining how it processes input collections non-destructively, generates unbiased random permutations, and achieves optimal time and space complexity.

1. Non-Destructive Array Conversion

Before any shuffling begins, _.shuffle standardizes the input collection:

• Immutability: To avoid mutating the original input, Lodash clones the input elements into a new array.
• Collection Handling: If passed an object, string, or arguments object, Lodash converts the values into a standard array using its internal copyArray or values helpers.

Because the shuffle operation is performed on this freshly allocated array, the source data remains unmodified.

2. The Core Algorithm: Fisher-Yates (Durstenfeld Implementation)

Lodash relies on the modern Fisher-Yates shuffle (frequently credited to Richard Durstenfeld). Unlike naive sorting approaches—such as using array.sort(() => Math.random() - 0.5)—Fisher-Yates guarantees an unbiased, uniform distribution where every possible permutation of the array has an equal probability (\(1/n!\)) of occurring.

The algorithm runs through the following sequence:

1. Initialization: A target array of length \(n\) is prepared.
2. Iteration: A loop runs through the array indices. Lodash typically iterates from index 0 up to length - 1.
3. Random Index Selection: For the current index i, Lodash selects a random index rand within the range from 0 to i (or from i to length - 1 in reverse implementations) using JavaScript's native pseudo-random number generator, Math.random().
4. Element Swap: The element at index rand is swapped with the element at index i.

3. Step-by-Step Execution Model

Conceptually, Lodash executes the shuffle logic as follows:

function shuffle(collection) {
  const array = Array.isArray(collection) ? [...collection] : Object.values(collection);
  const length = array.length;
  let index = -1;
  const lastIndex = length - 1;
  const result = [...array];

  while (++index < length) {
    // Generate a random integer between index and lastIndex inclusive
    const rand = index + Math.floor(Math.random() * (lastIndex - index + 1));
    
    // Swap the current value with the randomly selected value
    const value = result[rand];
    result[rand] = result[index];
    result[index] = value;
  }

  return result;
}

4. Complexity and Randomness Guarantees

• Time Complexity: \(O(n)\), where \(n\) is the number of elements in the collection. Each element is visited and swapped exactly once.
• Space Complexity: \(O(n)\), required to store the new shuffled array while preserving the original input.
• Uniformity: Because each element has an equal chance of landing in any position at every step of the iteration, no bias is introduced. The quality of the randomness is bounded only by the underlying pseudo-random number generator provided by the JavaScript runtime (Math.random).