doubly dual shuffles

https://dotat.at/@/2025-12-25-shuffle.html

Here's a pearlescent xmas 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.)

( Read more... )