Fisher–Yates shuffle

function pickVariant(random = Math.random) {
  return random() < 0.5 ? "A" : "B"; // which version of a page a visitor sees
}
 
pickVariant();           // "A" or "B", by chance
pickVariant(() => 0.2);  // "A", every time
pickVariant(() => 0.7);  // "B", every time
 
// Is it fair? Run it many times with a seeded generator and count.
const random = seeded(42);
const counts = { A: 0, B: 0 };
for (let i = 0; i < 10_000; i++) counts[pickVariant(random)]++;
counts; // { A: 5022, B: 4978 }: about half each, and the same counts on every run

Write shuffle(array, random). It returns a new array with the same items as array, in a random order. array itself never changes.

random is optional and defaults to Math.random. It takes no arguments and returns a number from 0 up to, but not including, 1. Get every random number from random, never from Math.random directly, so a test can pass in a predictable one.

Every order must be equally likely, as long as random is fair: shuffling 3 items, each of their 6 orders should come up about once in 6 shuffles, and each item should land in each position about as often as any other. The tests shuffle thousands of times with a seeded random and count.

shuffle([1, 2, 3, 4, 5]);          // for example [3, 5, 1, 2, 4]
shuffle(["a", "b", "c"], () => 0); // the same order every time, since random always returns 0

What the tests check

1. 1returns a new array with the same items

   const input = [1, 2, 3, 4, 5];
   const result = shuffle(input, () => 0.5);
   expect(result).not.toBe(input);
   expect(result).toHaveLength(5);
   expect([...result].sort((x, y) => x - y)).toEqual([1, 2, 3, 4, 5]);
   

2. 2leaves the original array alone

   const input = ["a", "b", "c", "d"];
   shuffle(input, () => 0);
   shuffle(input);
   expect(input).toEqual(["a", "b", "c", "d"]);
   

3. 3keeps duplicates and objects as they are

   const item = { id: 1 };
   const result = shuffle([item, "x", "x", item], () => 0.3);
   expect(result.filter((value) => value === item)).toHaveLength(2);
   expect(result.filter((value) => value === "x")).toHaveLength(2);
   

4. 4handles empty and one-item arrays

   expect(shuffle([])).toEqual([]);
   expect(shuffle([7], () => 0.9)).toEqual([7]);
   

5. 5uses Math.random when random isn't given

   const realRandom = Math.random;
   const fake = spy(() => realRandom());
   Math.random = fake;
   let result;
   try {
     result = shuffle([1, 2, 3, 4, 5]);
   } finally {
     Math.random = realRandom;
   }
   expect(fake).toHaveBeenCalled();
   expect([...result].sort((x, y) => x - y)).toEqual([1, 2, 3, 4, 5]);
   

6. 6gets every random number from random, not Math.random

   const realRandom = Math.random;
   Math.random = () => {
     throw new Error("shuffle called Math.random instead of random");
   };
   let result;
   try {
     result = shuffle([1, 2, 3, 4, 5, 6], () => 0.42);
   } finally {
     Math.random = realRandom;
   }
   expect([...result].sort((x, y) => x - y)).toEqual([1, 2, 3, 4, 5, 6]);
   

7. 7works when random returns its smallest or largest values

   for (const value of [0, 0.9999999999]) {
     const result = shuffle([1, 2, 3, 4, 5], () => value);
     expect([...result].sort((x, y) => x - y)).toEqual([1, 2, 3, 4, 5]);
   }
   

8. 8makes every order of 3 items equally likely

   // A seeded random number generator (mulberry32): the same seed always gives the same numbers.
   function seeded(seed) {
     return () => {
       seed = (seed + 0x6d2b79f5) | 0;
       let t = Math.imul(seed ^ (seed >>> 15), seed | 1);
       t ^= t + Math.imul(t ^ (t >>> 7), t | 61);
       return ((t ^ (t >>> 14)) >>> 0) / 4294967296;
     };
   }
   const random = seeded(42);
   const counts = new Map();
   for (let run = 0; run < 6000; run++) {
     const order = shuffle(["a", "b", "c"], random).join("");
     counts.set(order, (counts.get(order) ?? 0) + 1);
   }
   expect([...counts.keys()].sort()).toEqual(["abc", "acb", "bac", "bca", "cab", "cba"]);
   for (const count of counts.values()) {
     // 6,000 shuffles over 6 orders: about 1,000 each.
     expect(count).toBeGreaterThan(850);
     expect(count).toBeLessThan(1150);
   }
   

9. 9puts each item in each position equally often

   // A seeded random number generator (mulberry32): the same seed always gives the same numbers.
   function seeded(seed) {
     return () => {
       seed = (seed + 0x6d2b79f5) | 0;
       let t = Math.imul(seed ^ (seed >>> 15), seed | 1);
       t ^= t + Math.imul(t ^ (t >>> 7), t | 61);
       return ((t ^ (t >>> 14)) >>> 0) / 4294967296;
     };
   }
   const random = seeded(7);
   const items = [0, 1, 2, 3, 4];
   const counts = items.map(() => items.map(() => 0));
   for (let run = 0; run < 5000; run++) {
     shuffle(items, random).forEach((item, position) => counts[item][position]++);
   }
   for (const row of counts) {
     for (const count of row) {
       // 5,000 shuffles over 5 positions: about 1,000 each.
       expect(count).toBeGreaterThan(850);
       expect(count).toBeLessThan(1150);
     }
   }
   

Learn more

• Numbers & mathLesson
• DestructuringLesson