41–50 of 53 posts
Reminds me of a really cool coding trick to get a "random" permutation of an array in O(1) time/memory. https://lemire.me/blog/2017/09/18/visiting-all-values-in-an-...
The trick is to do 88 columns, punch them out on a roll, and run it through a player piano.
Reminds me of a really cool coding trick to get a "random" permutation of an array in O(1) time/memory. https://lemire.me/blog/2017/09/18/visiting-all-values-in-an-...
That's neither random nor O(1). I think everybody reading the link immediately understands what you mean, but I whished this community would use its technical terminology more carefully.
The blog post uses "random" in quotations as well in its title.
I call it O(1) because the ordering is fully determined just by choosing an arbitrary prime number. It's constant time to "reorder" the elements and also constant time to get the i'th element in the permutation. This is in contrast to something like the the Fisher-Yates shuffle which permutes the elements in O(n) time.
Reminds me of a really cool coding trick to get a "random" permutation of an array in O(1) time/memory. https://lemire.me/blog/2017/09/18/visiting-all-values-in-an-...
The trick is to do 88 columns, punch them out on a roll, and run it through a player piano.
this deserves more upvotes
It will sound horrible. IIRC if you know music and choose only 4 notes correctly, even random notes may not sound too bad. So perhaps the version with 88/12*4 columns may be better.
Reminds me of a really cool coding trick to get a "random" permutation of an array in O(1) time/memory. https://lemire.me/blog/2017/09/18/visiting-all-values-in-an-...
Feistel networks are another way to map your index from linear sequence to a pseudorandom permutation.
It has better avalanching compared to indexing by `(i * prime) % n`, but at the tradeoff of `n` being restricted to powers of 2.