Fun with shuffling algorithms

array-shuffles.js

import { randmax } from './random.js'

// -- Bad array shuffling examples. Here for completeness. DO NOT USE ------- //

/**
 * Sort shuffle, a bad example of shuffling an array using
 * Array.prototype.sort() with a random comparator. This does not produce a
 * uniform shuffle.
 *
 * Time complexity is O(n log n) due to the use of Array.prototype.sort().
 * Space complexity is O(n) due to the use of an additional array.
 *
 * @param {Array} array - An array of elements
 * @returns {Array} A non-uniformly shuffled array
 */
export function sortShuffle(array) {
  const deck = [...array]
  return deck.sort(() => 2 ** 31 - randmax(2 ** 32))
}

// -- Efficient array shuffling algorithms ---------------------------------- //

/**
 * Key shuffle, a better example of shuffling an array using
 * Array.prototype.sort(). This produces a uniform shuffle.
 *
 * Time complexity is O(n log n) due to the use of Array.prototype.sort().
 * Space complexity is O(n) due to the use of an additional array.
 *
 * @param {Array} array - An array of elements
 * @returns {Array} A uniformly shuffled array
 */
export function keyShuffle(array) {
  const deck = [...array]

  return deck
    .map((item) => ({ item, key: randmax(2 ** 32) }))
    .sort((a, b) => a.key - b.key)
    .map(({ item }) => item)
}

/**
 * Original 1938 Fisher-Yates pencil-and-paper scratch method.
 *
 * Time complexity is O(n^2) due to the use of Array.prototype.splice().
 * Space complexity is O(n) due to the use of an additional array.
 *
 * @param {Array} array - An array of elements
 * @returns {Array} A uniformly shuffled array
 */
export function fisherYatesShuffle(array) {
  const deck = [...array]
  const shuffled = []

  while (deck.length > 0) {
    const index = randmax(deck.length)
    shuffled.push(deck[index])
    deck.splice(index, 1)
  }

  return shuffled
}

/**
 * 1964 efficient improvement of Fisher-Yates for computers by Richard
 * Durstenfeld and Donald E. Knuth.
 *
 * Time complexity is O(n) due to the use of a single loop.
 * Space complexity is O(1) as it shuffles the array in place.
 *
 * @param {Array} array - An array of elements
 * @returns {Array} A uniformly shuffled array
 */
export function durstenfeldKnuthShuffle(array) {
  const deck = [...array]
  for (let i = deck.length - 1; i > 0; i--) {
    const j = randmax(i + 1)
    ;[deck[i], deck[j]] = [deck[j], deck[i]]
  }

  return deck
}

/**
 * Sattolo's algorithm for generating uniformly distributed cycles. Differs from
 * Durstenfeld-Knuth in that every element must be shuffled to a new position.
 *
 * Time complexity is O(n) due to the use of a single loop.
 * Space complexity is O(1) as it shuffles the array in place.
 *
 * @param {Array} array - An array of elements
 * @returns {Array} A uniformly shuffled array
 */
export function sattoloShuffle(array) {
  const deck = [...array]
  for (let i = deck.length - 1; i > 0; i--) {
    const j = randmax(i)
    ;[deck[i], deck[j]] = [deck[j], deck[i]]
  }

  return deck
}

/**
 * Rao-Sandelius shuffle, a divide-and-conquer algorithm for large datasets.
 *
 * Time complexity is O(n log n) due to the recursive calls.
 * Space complexity is O(n) due to the use of additional arrays.
 *
 * @param {Array} array - An array of elements
 * @returns {Array} A uniformly shuffled array
 */
export function raoSandeliusShuffle(array) {
  const n = array.length
  if (n <= 1) return array

  const group0 = []
  const group1 = []

  let remaining = n
  let needed = Math.floor(n / 2)

  for (const item of array) {
    if (randmax(remaining) < needed) {
      group0.push(item)
      needed--
    } else {
      group1.push(item)
    }

    remaining--
  }

  return [...raoSandeliusShuffle(group0), ...raoSandeliusShuffle(group1)]
}

card-shuffles.js

import { randmax } from './random.js'

// -- Playing card shuffling techniques -------------------------------------- //

/**
 * Faro shuffle, a deterministic shuffle that splits the array exactly in half
 * and interleaves the two halves.
 *
 * The horseshoe option reverses the second half before interleaving, as studied
 * by Steve Butler et al. in American Mathematical Monthly, 2016. It's studied
 * as a generalization of the faro group. The paper works out the group
 * structure and shows how it relates to the ordinary in/out-shuffle group.
 * Unlike a straight faro, the horseshoe shuffles aren't naturally reversible
 * into "in" vs "out" variants in quite the same clean way, since you also have
 * to specify which half gets reversed (top or bottom) in addition to the
 * interleave direction, so there's effectively a small family of these
 * depending on that choice.
 *
 * Time complexity is O(n) due to the use of array slicing and concatenation.
 * Space complexity is O(n) due to the use of additional arrays.
 *
 * @param {Array} array - An array of elements
 * @param {boolean} outShuffle - If true, performs an out-shuffle;
 *     if false, performs an in-shuffle
 * @returns {Array} A shuffled array
 */
export function faroShuffle(array, outShuffle = true, horseshoe = false) {
  const deck = [...array]
  const half = Math.floor(deck.length / 2)
  const a = deck.slice(0, half)
  const b = horseshoe ? deck.slice(half).reverse() : deck.slice(half)
  const result = []

  for (let i = 0; i < half; i++) {
    outShuffle ? result.push(a[i], b[i]) : result.push(b[i], a[i])
  }

  if (deck.length % 2 !== 0) result.push(b[b.length - 1])

  return result
}

/**
 * Gilbert-Shannon-Reeds shuffle, a probabilistic shuffle that simulates the
 * physical card shuffling technique via the Gilbert-Shannon-Reeds model.
 * Simulates a physical shuffle by interleaving the two halves based on the
 * weights of the remaining cards in each half.
 *
 * Time complexity is O(n) due to the use of a single loop.
 * Space complexity is O(n) due to the use of additional arrays.
 *
 * @param {Array} array - An array of elements
 * @returns {Array} A shuffled array
 */
export function gsrShuffle(array) {
  let deck = [...array]
  let rounds = Math.ceil(1.5 * Math.log2(deck.length)) // See Bayer and Diaconis

  while (rounds-- > 0) {
    const result = []

    let cut = 0
    for (let i = 0; i < deck.length; i++) cut += randmax(2)

    let leftIdx = 0
    let rightIdx = 0
    const left = deck.slice(0, cut)
    const right = deck.slice(cut)

    while (leftIdx < left.length && rightIdx < right.length) {
      const remaining = randmax(left.length - leftIdx + right.length - rightIdx)

      if (remaining < left.length - leftIdx) {
        result.push(left[leftIdx++])
      } else {
        result.push(right[rightIdx++])
      }
    }

    deck = result.concat(left.slice(leftIdx), right.slice(rightIdx))
  }

  return deck
}

/**
 * Klondike, a deterministic card shuffle that alternately takes elements from
 * the top and bottom of the array.
 *
 * Earliest known reference to this shuffle written about in the book {@link
 * https://www.conjuringcredits.com/lib/tpl/credits/files/1726-modern-gaming.pdf
 * The Whole Art and Mystery of Modern Gaming Fully Expos'd and Detected} by an
 * anonymous author in 1726. It was also independently discovered by {@link
 * https://web.archive.org/web/20191122010242/https://pthree.org/2018/10/05/the-ouroboros-card-shuffle/
 * Aaron Toponce in 2018} as the Ouroboros shuffle. Noticing that the bottom
 * card of a Klondike shuffle always remains in the same position, this
 * variation implements moving the top card off first, then proceeding with the
 * standard Klondike shuffle, ensuring a different bottom card after each full
 * cycle.
 *
 * Time complexity is O(n) due to the use of a single loop.
 * Space complexity is O(n) due to the use of an additional array.
 *
 * @param {Array} array - An array of elements
 * @param {boolean} ouroboros - If false, uses the standard Klondike shuffle;
 *     if true, uses the Ouroboros shuffle variant
 * @returns {Array} A shuffled array
 */
export function klondikeShuffle(array, ouroboros = false) {
  const deck = [...array]
  const result = []
  let lo = 0,
    hi = deck.length - 1,
    top = ouroboros

  for (let i = deck.length - 1; i >= 0; i--) {
    result[i] = top ? deck[lo++] : deck[hi--]
    top = !top
  }

  return result
}

/**
 * Mongean shuffle, a deterministic shuffle that places the first card down,
 * then alternates placing each subsequent card on top of or underneath the
 * growing pile.
 *
 * Time complexity is O(n) due to a single loop with O(1) position math.
 * Space complexity is O(n) due to the use of an additional array.
 *
 * @param {Array} array - An array of elements
 * @returns {Array} A shuffled array
 */
export function mongeanShuffle(array) {
  const deck = [...array]
  const n = deck.length
  const result = new Array(n)
  const half = Math.ceil(n / 2)

  deck.forEach((card, i) => {
    const k = Math.floor(i / 2)
    const pos = (i & 1) === 0 ? half - 1 - k : half + k
    result[pos] = card
  })

  return result
}

/**
 * Spiral shuffle, a deterministic elimination-style shuffle. The top
 * card is discarded to the table, then the new top card is moved to the
 * bottom of the hand, repeating until the hand is exhausted.
 *
 * Time complexity is O(n) due to the use of a circular buffer.
 * Space complexity is O(n) due to the use of an additional array.
 *
 * @param {Array} array - An array of elements
 * @returns {Array} A shuffled array
 */
export function spiralShuffle(array) {
  const deck = [...array]
  const n = deck.length
  if (n <= 1) return deck

  const result = []
  let top = 0,
    bottom = n - 1,
    count = n

  while (count > 0) {
    result.push(deck[top])
    top = (top + 1) % n
    count--

    if (count > 0) {
      const val = deck[top]
      top = (top + 1) % n
      bottom = (bottom + 1) % n
      deck[bottom] = val
    }
  }

  return result.reverse()
}

/**
 * Pile shuffle, a deterministic shuffle that deals cards round-robin into a
 * fixed number of piles, then reassembles the piles by stacking each
 * subsequent pile on top of the previous one.
 *
 * Time complexity is O(n) due to a single deal and a single reassembly.
 * Space complexity is O(n) due to the use of additional arrays for the piles.
 *
 * @param {Array} array - An array of elements
 * @param {number} numPiles - The number of piles to deal into (typically 4-8)
 * @returns {Array} A shuffled array
 */
export function pileShuffle(array, numPiles = 4) {
  const deck = [...array]
  const result = Array.from({ length: numPiles }, () => [])

  for (let i = 0; i < deck.length; i++) {
    result[i % numPiles].push(deck[i])
  }

  return result.reduceRight((stack, pile) => [...pile.reverse(), ...stack], [])
}

crypto-shuffles.js

import { randmax } from './random.js'

// -- Cryptographic mixing-network shuffles --------------------------------- //

/**
 * Thorp shuffle, a probabilistic shuffle that simulates a physical riffle
 * shuffle introduced by E. Thorp in 1973.
 *
 * The deck is divided into two equal piles of n/2 cards. Cards are dropped from
 * the bottom of the piles to form a new deck. For each pair of positions in the
 * new deck, a fair coin is flipped to determine which pile's card is dropped
 * first, the other pile's card dropped second. The process continues until both
 * piles are empty. This constitutes one round. To maximize the Shannon entropy
 * in the deck, optimal mixing rounds are calculated automatically based on array
 * size.
 *
 * Time complexity is O(n log n) due to r = O(log n) rounds of O(n) work each.
 * Space complexity is O(n) due to the use of additional arrays.
 *
 * @param {Array} array - The original array to shuffle.
 * @returns {Array} A new, maximally mixed array.
 */
export function thorpShuffle(array) {
  let deck = [...array]
  let rounds = Math.ceil(4 * Math.log2(deck.length)) // See Hoang, Morris, and Rogaway

  while (rounds-- > 0) {
    const mid = Math.ceil(deck.length / 2)
    const discard = []
    const leftPile = deck.slice(0, mid)
    const rightPile = deck.slice(mid)

    let leftIndex = 0
    let rightIndex = 0

    while (leftIndex < leftPile.length && rightIndex < rightPile.length) {
      if (randmax(2) === 0) {
        discard.push(leftPile[leftIndex++], rightPile[rightIndex++])
      } else {
        discard.push(rightPile[rightIndex++], leftPile[leftIndex++])
      }
    }

    // For odd-numbered decks, one pile will have one extra card. Add it to the discard pile.
    if (leftIndex < leftPile.length) discard.push(leftPile[leftIndex++])
    if (rightIndex < rightPile.length) discard.push(rightPile[rightIndex++])

    deck = discard
  }

  return deck
}

/**
 * Swap-or-Not shuffle, a round-based mixing shuffle introduced by Hoang,
 * Morris, and Rogaway (CRYPTO 2012) as a card-shuffle-based construction for
 * small-domain block ciphers.
 *
 * Each round picks a random round value k, then pairs every position x with
 * its "partner" position (k - x) mod n. A fair coin flip decides whether to
 * swap each pair. The true Swap-or-Not construction pairs positions via XOR
 * with a round key, which requires the domain size to be a power of two;
 * this implementation instead pairs positions via modular subtraction
 * ((k - x + n) % n), which is a valid involution for ANY n, so it works on
 * arrays of arbitrary length without padding or cycle-walking.
 *
 * NOTE: this is a randomized MIXING demonstration, not a real cipher. The
 * actual swap-or-not construction derives its swap decision from a keyed
 * PRF; here the swap decision is a plain coin flip via randmax(2), matching how
 * thorpShuffle treats mixing rounds. This preserves the mixing structure and
 * round-count guidance from the literature, but produces an unkeyed,
 * non-invertible shuffle, not a small-domain encryption scheme.
 *
 * Time complexity is O(rounds * n) due to a single pass over all positions
 * each round.
 * Space complexity is O(n) due to the use of an additional array (swaps
 * themselves are in place).
 *
 * @param {Array} array - An array of elements
 * @param {number} rounds - The number of mixing rounds to perform
 * @returns {Array} A shuffled array
 */
export function swapOrNotShuffle(array) {
  const deck = [...array]
  const n = deck.length
  let rounds = Math.ceil(4 * Math.log2(array.length)) // See Dai, Hoang, and Tessaro (2017)

  while (rounds-- > 0) {
    const k = randmax(n)

    for (let x = 0; x < n; x++) {
      const partner = (k - x + n) % n

      if (partner > x && randmax(2) === 1) [deck[x], deck[partner]] = [deck[partner], deck[x]]
    }
  }

  return deck
}

/**
 * Sometimes-Recurse shuffle, introduced by Morris and Rogaway (EUROCRYPT
 * 2014) as an efficiency improvement over the Mix-and-Cut shuffle. The core
 * idea: lightly shuffle the whole deck, cut it in half, then recurse on only
 * ONE half rather than both — the un-recursed half is left alone since a
 * single light shuffle already leaves it looking close to uniform relative
 * to the other half.
 *
 * NOTE: this is a randomized MIXING demonstration, not a real cipher. The
 * actual Sometimes-Recurse construction builds its light shuffle from a
 * keyed random function and is proven secure even when an adversary queries
 * the entire domain; here the light shuffle is a single unkeyed
 * swap-or-not-style mixing pass via randmax(), matching how thorpShuffle and
 * swapOrNotShuffle above treat mixing rounds. This preserves the shuffle's
 * structural idea (light-mix, cut, recurse-on-one-half) but produces an
 * unkeyed, non-invertible shuffle, not a small-domain encryption scheme. The
 * real construction also has a known timing side-channel (its running time
 * leaks information about the output), addressed by a follow-up "Janus
 * Sometimes-Recurse" variant not implemented here.
 *
 * Time complexity is O(n) overall: each recursive level does one O(size)
 * light-shuffle pass, and sizes halve each level, so the work sums to O(n)
 * across O(log n) levels of recursion.
 * Space complexity is O(n) due to the use of additional arrays.
 *
 * @param {Array} array - An array of elements
 * @returns {Array} A shuffled array
 */
export function sometimesRecurseShuffle(array) {
  const deck = [...array]
  const n = deck.length
  if (n <= 1) return deck

  // Light shuffle: a single swap-or-not-style mixing pass over the whole deck.
  const k = randmax(n)
  for (let x = 0; x < n; x++) {
    const partner = (k - x + n) % n
    if (partner > x && randmax(2) === 1) [deck[x], deck[partner]] = [deck[partner], deck[x]]
  }

  // Cut the deck, then recurse on only the bottom half.
  const mid = Math.floor(n / 2)
  const top = deck.slice(0, mid)
  const bottom = deck.slice(mid)

  return [...top, ...sometimesRecurseShuffle(bottom)]
}

demo.js

import {
  sortShuffle,
  keyShuffle,
  fisherYatesShuffle,
  durstenfeldKnuthShuffle,
  sattoloShuffle,
  raoSandeliusShuffle,
  thorpShuffle,
  swapOrNotShuffle,
  sometimesRecurseShuffle,
  faroShuffle,
  gsrShuffle,
  klondikeShuffle,
  mongeanShuffle,
  spiralShuffle,
  pileShuffle,
} from './index.js'

const array = Array.from({ length: 52 }, (_, index) => index)

console.log("Array shuffles:")
console.log(JSON.stringify(sortShuffle(array)) + " Sort")
console.log(JSON.stringify(keyShuffle(array)) + " Key")
console.log(JSON.stringify(fisherYatesShuffle(array)) + " Fisher-Yates")
console.log(JSON.stringify(durstenfeldKnuthShuffle(array)) + " Durstenfeld-Knuth")
console.log(JSON.stringify(sattoloShuffle(array)) + " Sattolo")
console.log(JSON.stringify(raoSandeliusShuffle(array)) + " Rao-Sandelius")
console.log()
console.log("Cryptographic shuffles:")
console.log(JSON.stringify(thorpShuffle(array)) + " Thorp")
console.log(JSON.stringify(swapOrNotShuffle(array)) + " Swap-or-Not")
console.log(JSON.stringify(sometimesRecurseShuffle(array)) + " Sometimes Recurse")
console.log()
console.log("Playing card shuffles:")
console.log(JSON.stringify(faroShuffle(array, false, false)) + " Faro in")
console.log(JSON.stringify(faroShuffle(array, false, true)) + " Faro out")
console.log(JSON.stringify(faroShuffle(array, true, false)) + " Faro in, horseshoe")
console.log(JSON.stringify(faroShuffle(array, true, true)) + " Faro out, horseshoe")
console.log(JSON.stringify(gsrShuffle(array)) + " Gilbert-Shannon-Reeds riffle")
console.log(JSON.stringify(klondikeShuffle(array, false)) + " Klondike")
console.log(JSON.stringify(klondikeShuffle(array, true)) + " Ouroboros (Klondike variant)")
console.log(JSON.stringify(mongeanShuffle(array)) + " Mongean")
console.log(JSON.stringify(spiralShuffle(array)) + " Spiral")
console.log(JSON.stringify(pileShuffle(array)) + " Pile (4)")

index.js

export { randmax } from './random.js'
export {
  sortShuffle,
  keyShuffle,
  fisherYatesShuffle,
  durstenfeldKnuthShuffle,
  sattoloShuffle,
  raoSandeliusShuffle,
} from './array-shuffles.js'
export { thorpShuffle, swapOrNotShuffle, sometimesRecurseShuffle } from './crypto-shuffles.js'
export {
  faroShuffle,
  gsrShuffle,
  klondikeShuffle,
  mongeanShuffle,
  spiralShuffle,
  pileShuffle,
} from './card-shuffles.js'

package.json

{
    "type": "module"
}

random.js

// -- Helpers --------------------------------------------------------------- //

/**
 * Generate a uniform random number between 0 and n-1 using modulo with
 * rejection. Used in most shuffling algorithms in this file. The CSPRNG is
 * provided just in case security is a concern.
 *
 * @param {number} n
 * @returns {number}
 */
export function randmax(n) {
  const min = 2 ** 32 % n
  const rand = new Uint32Array(1)
  do {
    crypto.getRandomValues(rand)
  } while (rand[0] < min)
  return rand[0] % n
}