Coyote on Nostr: I found an algorithm for generating shuffled indexes that doesn’t require any ...

I found an algorithm for generating shuffled indexes that doesn’t require any memory.

I was thinking that there must be a better way of generating a shuffled list (a list of integers in random order appearing only once) than building the entire thing in memory. I did some research and came across the paper Correlated Multi-Jittered Sampling by Andrew Kensler that had this code for a pseudorandom permutation function:

unsigned permute(unsigned i, unsigned l, unsigned p) {
unsigned w = l - 1;
w |= w >> 1;
w |= w >> 2;
w |= w >> 4;
w |= w >> 8;
w |= w >> 16;

do {
i ^= p;
i *= 0xe170893d;
i ^= p >> 16;
i ^= (i & w) >> 4;
i ^= p >> 8;
i *= 0x0929eb3f;
i ^= p >> 23;
i ^= (i & w) >> 1;
i *= 1 | p >> 27;
i *= 0x6935fa69;
i ^= (i & w) >> 11;
i *= 0x74dcb303;
i ^= (i & w) >> 2;
i *= 0x9e501cc3;
i ^= (i & w) >> 2;
i *= 0xc860a3df;
i &= w;
i ^= i >> 5;
} while (i >= l);
return (i + p) % l;
}


I haven’t dug deep enough into crypto math to explain it, but you can pass the function an index, length, and seed and it’ll spit out a new “random” index that only appears once. You could use this to shuffle up to 4,294,967,295 songs without having to use gigabytes of memory to keep the list around and without having to compute the whole thing first.