Sattolo's algorithm

1 · Dan Luu · Aug. 9, 2017, midnight
I recently had a problem where part of the solution was to do a series of pointer accesses that would walk around a chunk of memory in pseudo-random order. 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 ...