▶ YouTube Summaries

• YT :: https://www.youtube.com/watch?v=SWNqgv7w_cY
• Original title :: Coding Playlist Shuffle Algorithm

Tsoding replaces the naive "pick a random index" shuffle in his stream music player with a formula-based permutation suggested by a Discord member: =f(x) = (a*x + b) mod p= with p prime and greater than the song count. It walks every index exactly once before repeating, so no song plays twice in a cycle, and it needs no shuffled array — only four integers of state. He implements it in Jai, pre-generates a table of primes at build time, integrates it into the player, and closes with a chat-supplied proof by contradiction that the sequence cannot repeat.

The problem

The player picks the next track as a uniform random index in [0, n). True randomness does not feel random: songs repeat twice or three times in a row. This is the same reason game developers engineer "random" rather than using an RNG directly, and the problem Spotify hit early on. The obvious fix — shuffle the list and walk it — is awkward because the songs live in a database, and he does not want to shuffle a table.

The algorithm

From Discord user X4204:

• Find prime p >= number of songs.
• Pick a, b randomly in [1, p-1].
• Iterate x from 0 upward, emitting =f(x) = (a*x + b) mod p=, skipping any value >= n (that is why the loop has the guard: p can exceed the song count, so out-of-range values are discarded).

Field properties guarantee a full permutation of 0..p-1, so no repeat until the whole list is exhausted. Chat later identifies this as a linear congruential generator; X4204 apparently rediscovered it independently.

Prime generation

Trial division, with two standard cuts: only test divisors up to sqrt(x) (divisors come in pairs), and only test previously found primes, using the growing primes array to index into itself. He starts the array with 2 and steps by 2 thereafter.

Since he will never have more than a million songs, he pre-generates all primes below a million and emits them as a formatted Jai source file — padded to six digits, twenty per row — rather than computing them at startup or at compile time (compile-time execution slowed the build). Lookup is a binary search upper_bound over the sorted table, which behaves as a lower bound for the "smallest prime >= n" query he wants. Out-of-range lookups go out of bounds; he adds an assert with a message about not enough pre-generated primes. Note that in Jai an uncalled generic function is never instantiated, so a broken format string in that assert compiles silently until the function is used.

His main complaint about the whole approach: it introduces a limit he now has to think about, where before there was none. Even if the limit is never hit, its existence is irritating.

Implementation

A Playlist_Shuffler struct holding songs_count, p, a, b and the current x; init finds the prime and draws a and b; next loops, incrementing x modulo p until the mapped value falls below the count, then returns it and advances. Jai's random_get_within_range only returns floats, so he writes an integer version — min + random_get() % (max - min + 1) — with an assert that min < max=, casting through u64 and back to s64 so negative ranges work.

First impressions were bad by accident: a random draw of =a = 10, p = 11= produced a plain descending shift, and a couple of other draws looked nearly sequential. Chat's suggestion to add higher powers of x breaks the no-repeat property, which was the entire point. He verifies correctness instead by piping the output through sort -n | uniq | wc -l and confirming it is always exactly n distinct values, and that running it over 2n produces exactly pairs.

Integration into the player replaces the random index in next_random_non_hidden_song: the shuffler is initialized with the count of sorted non-hidden song ids (songs can be marked hidden — they stay in the database and are searchable, but never played), and its next supplies the index. He listens through several tracks on stream with no repeats.

Footnote: the proof

Posted after the stream by Gaston147, proof by contradiction. Assume =f(x1) = f(x2)= for distinct x1, x2 in range. Subtract: =(a*(x1 - x2)) mod p = 0=, so a*(x1 - x2) is a multiple of p. Since p is prime, either a or (x1 - x2) must be a multiple of p — impossible, as both are strictly less than p. Hence no repetition. Tsoding's point: the original message claimed nontrivial field theory was required, and the whole thing collapses to a few lines.

Asides

• On his own skill level: he calls himself an average programmer by 2000s/2010s standards and says the bar for the industry has fallen. His goal is enjoying programming, not being good at it — being worse can be more fun, and the fear of looking stupid is what stops people enjoying the process.
• Riffs on generating the primes table as "automated code" replacing the programmers whose job was typing numbers into a file, and on people who apparently thought programming was a data-entry problem all along.
• Jai remains closed-beta; he says he would not be badly hurt if he lost access to the compiler tomorrow.
• Accepts a chat suggestion to fade out the waveform stems with a gradient instead of a solid border color.