4 ms·
Kinda interesting. There are N! permutations in a shuffle (no duplicates) and there's an algorithm where you pick one random number between 1->N! and then brin
by zug_zug 2y ago
Kinda interesting.
There are N! permutations in a shuffle (no duplicates) and there's an algorithm where you pick one random number between 1->N! and then bring up that permutation (though I don't know how to do it better than N log N with an order-statistic tree). I like this because it requires exactly one random number.
A trivial solution in functional programming (for those of us who find this swap stuff really unreadable and error-prone) would be something like:
[1,2,3,4,5,6].map(x => {return {value: x, order: Math.random()}}).sort((a,b) => (a.order - b.order)).map(x => x.value)
Of course this is N-Log-N, but personally I think it's easy to forget how small logN grows. Like log10(number of atoms in universe) = 82, so if your dataset is smaller than the number of atoms in the universe you could think of it as less than the constant 82.
- vlovich123 2y agoThe number of permissions of a deck of cards is 2^225 according to the article. Permissions grow quite quick
- zug_zug 2y agoYeah. So something like a 50-digit number. I guess your point is this would require a BigInt? From a performance perspective it's negligible. Like when doing RSA for example the primes are usually 2^512 in length.
- vlovich123 2y agoYour algorithm will never shuffle a deck of cards because randomly selecting a 64 digit means your N(logN) algorithm will need to generate on average the 2^63th or larger permutation. It’ll be several millennia for every deck shuffle. If you don’t believe me try to write it. Also, I’m not really sure your nlog(n) algorithm claim is accurate - python’s itertools says that the time complexity to generate the Nth permutation is still N!. So for a 52 deck card on average you’re going to have to generate 2^88 permutations. By comparison, shuffling is O(n) where your n is the number of items.
- zug_zug 2y agoI don't know what you're talking about, and that makes two of us. Writing the Nth-permutation is something I've done before as a leetcode challenge, here's example code [1] Maybe python implements it poorly, but it can definitely be done in n-log(n), and also try researching a little more before you pick a disagreement. I'm sure a simple google search could have saved you the trouble. ---- 1 - https://stackoverflow.com/questions/7918806/finding-n-th-permutation-without-computing-others https://stackoverflow.com/questions/7918806/finding-n-th-per...
- pvillano 2y agoA real pendant would handle collisions If Math.random() is truly uniform, it has about 53 bits of entropy. We can find the likelyhood of a collision with the birthday paradox ... the post ends here because WolframAlpha keeps choking on computations with numbers very, very close to one. I'm not doing derivatives. Fun fact: Math.random(a,b) always has about 53 bits of randomness, unless b/a is close to 1
- whyever 2y agoYou can calculate the probabilities and expected number of collisions analytically, but evaluating the expressions numerically is tricky for large numbers. I can recommend https://herbie.uwplse.org/ https://herbie.uwplse.org/ to rewrite the expressions into a form that can be evaluated.