Lodash sampleSize Algorithm Explained

Lodash's _.sampleSize function selects a specified number of unique, random elements from a collection using an optimized variant of the Fisher-Yates shuffle algorithm, often called a partial Fisher-Yates or Durstenfeld shuffle. Instead of randomizing the entire collection, the algorithm only shuffles the exact number of elements requested, providing uniform randomness and preventing duplicates while maximizing performance.

The Core Algorithm: Partial Fisher-Yates Shuffle

The standard Fisher-Yates shuffle (modernized by Richard Durstenfeld) runs in \(O(N)\) time by iterating through an entire array of size \(N\) and swapping each element with another randomly chosen element from the unshuffled portion.

Because _.sampleSize only needs \(n\) elements (where \(n \le N\)), running a full shuffle would waste CPU cycles when \(n\) is significantly smaller than \(N\). To solve this, Lodash implements a partial Fisher-Yates shuffle.

How the Algorithm Works Step-by-Step

When _.sampleSize(collection, n) is called, the internal implementation (primarily managed by Lodash's internal baseSampleSize function) follows these steps:

  1. Input Normalization: Lodash first converts the input collection into an array and clamps the requested size \(n\). If \(n\) is greater than the collection's length, \(n\) is set to the collection's length. If \(n \le 0\), an empty array is immediately returned.
  2. Array Copying: To ensure that the function remains pure and does not mutate the original data, Lodash creates a shallow copy of the collection (or an array of its values if an object is passed).
  3. In-Place Partial Swapping: The algorithm loops from index 0 up to n - 1:
    • At each index i, it generates a pseudo-random integer rand between i and the last index of the array (length - 1), inclusive.
    • It swaps the element at index i with the element at index rand.
  4. Result Extraction: After completing \(n\) iterations, the first \(n\) positions of the array contain randomly selected, unique elements. Lodash slices and returns these first \(n\) elements.

Mathematical Fairness

The partial Fisher-Yates algorithm guarantees that every possible subset of size \(n\) has an equal probability of being chosen:

\[\frac{1}{\binom{N}{n}} = \frac{n!(N - n)!}{N!}\]

Because the pool of available choices shrinks by one on each iteration, each remaining element always has an equal \(1 / (N - i)\) chance of being swapped into position \(i\).

Complexity and Performance