Coding a derangement-based playlist shuffle algorithm in J
- YT :: https://www.youtube.com/watch?v=SWNqgv7w_cY
- Original title :: Coding Playlist Shuffle Algorithm
Tsoding (Alexey Kutepov) fixes the naive "pick a random index every time" shuffle in his own music player, which sometimes replays the same song twice or thrice in a row. A Discord member (X4204) had shared a fix based on abstract algebra: a linear function f(x) = (a*x + b) mod p, with p prime and greater than the song count, produces a derangement — every song plays exactly once before any repeat, with no need to shuffle the underlying list. Tsoding implements this from scratch in his language J, building a prime-number generator and binary-search lookup, a minimal LCG-like "playlist shuffler" struct, and wiring it into his real application in place of the old random-index picker. He closes with a viewer-submitted proof-by-contradiction showing why the formula never repeats within one period.
The problem: naive shuffle repeats songs
Tsoding's music player picks the next song as a plain random index between 0 and n-1 each time. With real randomness this occasionally repeats the same song twice or even three times in a row, which reads to listeners as "not random enough" — the classic gambler's-fallacy-adjacent observation (also faced by early Spotify) that true randomness doesn't feel random to humans; you have to engineer it, similar to how blue noise is engineered to look uniform. The straightforward fix — shuffle the song list and play it left to right — is awkward for him because songs live in a database, not a convenient in-memory list.
A Discord member's abstract-algebra trick
A Discord user, X4204, had posted a message describing a way to generate a random permutation using finite fields: pick a prime p greater than or equal to the number of songs, pick random a and b in [1, p-1], and define f(x) = (a*x + b) mod p. Iterating x = 0, 1, 2, ... and evaluating f(x) (skipping outputs >= n) walks through all n songs exactly once before repeating, without ever needing to materialize or shuffle a list — this is a derangement/permutation property guaranteed by the field arithmetic. Tsoding, unfamiliar with the underlying theory, decides to implement and test it rather than take the claim on faith.
Generating and looking up primes
He writes an is-prime check (trial division up to sqrt(x), later optimized to only test divisors that are themselves already-found primes), pre-generates primes up to a large bound (testing up to a million, then ten million) at startup, and adds a find-prime function that binary-searches (upper/lower bound) the sorted prime array for the smallest prime >= n. He accepts the tradeoff that this caps the maximum playlist size to whatever range of primes was pre-generated, which mildly bothers him as an artificial limitation, but decides it's fine in practice.
Implementing the shuffler
He builds a small "playlist randomizer" (later renamed playlist shuffler / PS) struct holding n, p, a, b, and the current x, seeded from the current time. Its next() function increments x (wrapping mod p) until f(x) < n, returns that value, and updates state. He verifies correctness by generating N outputs, sorting, and checking they're a duplicate-free set of exactly N elements (running it twice shows exactly 2x duplicates, confirming each value appears once per period). Along the way he fights J's lack of closures (has to pass the primes array explicitly), an integer-only random-range helper that only came as a float, and signed/unsigned casting quirks when allowing negative ranges.
First impressions and viewer skepticism
Early test permutations look suspiciously non-random (e.g. sequences that are just a constant shift), prompting chat to suggest regenerating "bad" seeds or adding higher powers of x. Tsoding is annoyed at introducing a subjective "is this shuffle bad" criterion and initially doubts the algorithm, but decides the occasional weak-looking run is acceptable and moves on without those tweaks.
Wiring it into the real application
He integrates the shuffler into his actual music player, replacing the function that picks the next non-hidden song (songs can be individually hidden from the shuffle without being deleted). He initializes the playlist shuffler with the count of sorted non-hidden song IDs and replaces the naive random pick with next() on the shuffler, indexing into that sorted ID array. After fixing a compile error, he tests it live by playing through songs while chatting, confirming no repeats occur during the session, and takes viewer questions on programming philosophy (enjoying the process over the destination, not being afraid of mistakes) and personal topics.
Footnote: proof the formula never repeats
After the stream, Gaston147 posted a proof by contradiction: assume f(x1) = f(x2) for x1 != x2 within [0, p). Subtracting b and factoring out a mod p gives a*(x1 - x2) ≡ 0 (mod p), meaning p divides a*(x1 - x2). Since p is prime, it must divide (x1 - x2) (as a is coprime to p) — but that's impossible since both x1 and x2 are strictly less than p, so no repetition can occur within one period. Tsoding is impressed by how simple the proof turns out to be despite the abstract-algebra framing making it initially seem intimidating.