Re:I analyzed shuffling in a million games of MtG Arena
by Adverblessly on Sunday January 15, 2023 @12:43PM
(#34391265)
I wrote that code for fun 15-20 years ago (code definitely lost in the mists of time).
You can think of it as rolling one random number up to n!, then use x%n to pick the first element and then x/n to pick the next (n-1) elements (so the next step is then to pick the second element with (x/n)%(n-1) and use (x/n)/(n-1) for the remaining (n-2) elements).
Though as a sibling comment points out, since you need a random number up to n!, even 64 bits of randomness only get you so far (I think up to 20, but didn't check my math).
You can think of it as rolling one random number up to n!, then use x%n to pick the first element and then x/n to pick the next (n-1) elements (so the next step is then to pick the second element with (x/n)%(n-1) and use (x/n)/(n-1) for the remaining (n-2) elements).
Though as a sibling comment points out, since you need a random number up to n!, even 64 bits of randomness only get you so far (I think up to 20, but didn't check my math).