Sattolo's Algorithm (2017)

Sattolo's algorithm provides a solution to this because it produces a permutation of a list with exactly one cycle, which guarantees that we will reach every element of the list even though we're traversing it in random order.However, the explanations of why the algorithm worked that I could find online either used some kind of mathematical machinery (stirling numbers, assuming familiarity with cycle notation, etc.), or used logic that was hard for me to follow. When I was looking for a simple explanation, I also found a lot of people who were using Sattolo's algorithm in places where it wasn't appropriate and also people who didn't know that Sattolo's algorithm is what they were looking for, so here's an attempt at an explanation of why the algorithm works that doesn't assume an undergraduate combinatorics background.Before we look at Sattolo's algorithm, let's look at Fisher-Yates, which is an in-place algorithm that produces a random permutation of an array/vector, where every possible permutation occurs with uniform probability.We'll look at the code for Fisher-Yates and then how to prove that the algorithm produces the intended result.shuffle takes an array and produces a permutation of the array, i.e., it shuffles the array. Since Fisher-Yates produces each output with uniform probability, it produces all possible permutations with uniform probability.Now, let's look at Sattolo's algorithm, which is almost identical to Fisher-Yates and also produces a shuffled version of the input, but produces something quite different:Instead of picking an element at random to swap with, like we did in Fisher-Yates, we pick an element at random that is not the element being placed, i.e., we do not allow an element to be swapped with itself. We'll then do n-1 iterations, reducing the number of cycles from n to n - (n-1) = 1.Now let's see why it's safe to assume we always swap elements from different cycles. When we swap the initial element with some random element, we'll take one of the swappable elements and render it unswappable, creating a cycle of length 2 with 1 swappable element and leaving us with n-2 other cycles, each with 1 swappable element.The key invariant that's maintained is that each cycle has exactly 1 swappable element. And as long as this is true, every time we merge two cycles of any length, we'll take the swappable element from one cycle and swap it with the swappable element from the other cycle, rendering one of the two elements unswappable and creating a longer cycle that still only has one swappable element, maintaining the invariant.Since we cannot swap two elements from the same cycle, we merge two cycles with every swap, reducing the number of cycles by 1 with each iteration until we've run n-1 iterations and have exactly one cycle remaining.To see that we generate each cycle with equal probability, note that there's only one way to produce each output, i.e., changing any particular random choice results in a different output. permutations with exactly one cycle, then we'll know that we generate every permutation with exactly one cycle with uniform probability.Let's say we have an arbitrary list of length n that has exactly one cycle and we add a single element, there are n ways to extend that to become a cycle of length n+1 because there are n places we could add in the new element and keep the cycle, which means that the number of cycles of length n+1, cycles(n+1), is n * cycles(n).For example, say we have a cycle that produces the path 0 -> 1 -> 2 -> 0 ... While Sattolo's algorithm generates derangements, it only generates derangements with exactly one cycle, and there are derangements with more than one cycle (e.g., 3 2 1 0), so it can't possibly generate random derangements with uniform probability.One way to generate random derangements is to generate random shuffles using Fisher-Yates and then retry until we get a derangement:This algorithm is simple, and is overwhelmingly likely to eventually return a derangement (for n != 1), but it's not immediately obvious how long we should expect this to run before it returns a result. Assume by induction that after the initial iteration of the loop, the remaining iterations permute the first n - 1 elements according to a cycle of length n - 1 (those remaining iterations are just Sattolo's algorithm applied to those first n - 1 elements). Assuming randrange generates integers with uniform probability in the appropriate range, the original a[0] has 1/n probability of being swapped with any element (including itself), so the resultant a[0] has a 1/n chance of being any element from the original a, which is what we want.a[1] is placed on the second iteration of the loop.