# Four variants of array-shuffle algorithms

DevFeed: [Four variants of array-shuffle algorithms](<https://devfeed.tech/articles/doubly-dual-shuffles-36225.md>)

Original publisher: [Read original article](<https://dotat.at/@/2025-12-25-shuffle.html>)

Published: 2025-12-25T23:45:02Z

Content type: tutorial

Language: en

Sources: [Tony Finch's blog](<https://devfeed.tech/sources/tony-finch-s-blog.md>)

Topics: [Algorithms](<https://devfeed.tech/topics/algorithms.md>), [Algorithms, Complexity](<https://devfeed.tech/topics/algorithms-complexity.md>)

Tags: [algorithm](<https://devfeed.tech/tags/algorithm.md>), [permutations](<https://devfeed.tech/tags/permutations.md>)

## AI overview

The article examines four symmetric variants of an array-shuffling algorithm. It distinguishes sampling-based and permutation-based approaches, and places the common Durstenfeld shuffle among the variants.

## Source excerpt

Here's a pearlescent winter holiday gift for you! There are four variants of the algorithm for shuffling an array, arising from two independent choices: whether to swap elements in the higher or lower parts of the array whether the boundary between the parts moves upwards or downwards The variants are perfectly symmetrical, but they work in two fundamentally different ways: sampling or permutation. The most common variant is Richard Durstenfeld's shuffle algorithm, which moves the boundary downwards and swaps elements in the lower part of the array. Knuth describes it in TAOCP vol. 2 sect. 3.4.2; TAOCP doesn't discuss the other variants. (Obeying Stigler's law, it is often called a "Fisher-Yates" shuffle, but their pre-computer algorithm is arguably different from the modern algorithm.) the four variants In the pseudocode below, min and max are the inclusive bounds on the array to be shuffled; the arguments to rand() are the inclusive bounds on its return value; and the loop bounds are inclusive too. I chose this style to make the symmetries more obvious. In all variants, it's possible for the indexes this (the boundary between the parts of the array) and that (chosen at random) to be the same, in which case the swap is a no-op. I could have written the loop bounds as min and max instead of min+1 and max-1 to make the variants look as similar as possible, but it's more realistic to omit the loop iterations when this and that are guaranteed to be equal. It should be clear that rand() is invoked for spans of each size between 2 and N (where N = max - min + 1) so the algorithms produce N! possible permutations as expected. boundary moves down, pick from lower shuffle(a, min, max) for this = max to min+1 step -1 that = rand(min, this) swap a[this] and a[that] boundary moves up, pick from higher shuffle(a, min, max) for this = min to max-1 step +1 that = rand(this, max) swap a[this] and a[that] boundary moves down, pick from higher shuffle(a, min, max) for this = max-1 t