On: Scrambling eggs for Spotify with Knuth's Fibonacci hashing

[pncnmnp]

This is fantastic! I still need to carefully study it all, but I implemented the idea you described in the original comment. It seems the error lies somewhere between the algorithm I mentioned and the Fisher-Yates shuffle, based on one million playlists: Mean: 0.13, Median: 0.11, Mode: 0, p25: 0.06, p75: 0.18, p90: 0.26, p95: 0.31.

It's possible I'm missing something here. Regarding your edit about 'picking any new random number as the stepsize,' wouldn't it be affected by a 'bad break,' as mentioned by Knuth? I still need to work out the 'bad break' proof.

Edit: If it helps, here is the code I used to test it out - https://gist.github.com/pncnmnp/8afb7903f61ec69a157287435a63...

[bazzargh → pncnmnp]

I don't have Knuth to hand...but yeah it is possible you can accidentally pick a number that is too close to a rational, so you get short repeats of tracks instead of long ones. What you're after is a number with a high approximation coefficient https://en.wikipedia.org/wiki/Liouville_number#Irrationality... but in practice you just need to know that it is irrational "enough", eg you might want to avoid repeats in the first 1000 plays.

You can get that by rejection sampling on the random number and using the Farey sequence to find nearby low-denominator fractions https://en.wikipedia.org/wiki/Farey_sequence#Applications - if I pick a number between 0 and 1 I can use 0/1, 1/1 as the starting point for the usual iteration. (and then scale to .25,.75 at the end). You pick your approximation bound mu and reject if log(abs(p/q - x)) > - mu log q, repeat the farey iteration until q is large enough. (just making this up as I go on an ipad, I may have a sign wrong in there or whatever)

It is actually much simpler than this ^ to just explicitly check the first 1000 numbers for a loop. It's simpler than tortoise and hare: you know there is no run-in, so the first number is in the loop, and you want that number to not reappear in the first min(N,1000) items.