Here is a trivial shuffle algorithm that is completely unbiased and only requires an unbiased coin (or random number generator giving bits):
How does this compare to a regular Knuth shuffle where, since you only have a 1-bit generator, when you need (for example) an integer between 0 and 23, you treat the bits you generate as the binary expansion of a real number in [0, 1), and generate them until floor(24*n) is unambiguous?
(Obviously, the random number generation is more conceptually complex, but aside from that.)
You need at least nlog(n) bits for the same reason as regular shuffling. There are n! permutations and it therefore takes log(n!) bits to uniquely describe a shuffle. nlog(n) is the same as log(n^n) which is obviously greater than log(n!) (this is Stirling’s approximation).
OK, but I was kind of hoping for a treatment that involved the workings of one or both algorithms. They are subject to the same theoretical lower bound, yes. Do they have any advantages or disadvantages relative to each other? Does one of them do a much better job reaching the theoretical bound?
It kind of makes me mad that the very simple RS algorithm (divide and conquer) isn't more widely known given that it's so easy to implement and that it's actually parallelizable unlike Fisher-Yates. I think it's also better pedagogically since you can easily do it with a deck of cards and a coin or some dice while Fisher-Yates is pretty unwieldy for anything beyond very small lists.
Comments
How does this compare to a regular Knuth shuffle where, since you only have a 1-bit generator, when you need (for example) an integer between 0 and 23, you treat the bits you generate as the binary expansion of a real number in [0, 1), and generate them until floor(24*n) is unambiguous?
(Obviously, the random number generation is more conceptually complex, but aside from that.)
You need at least nlog(n) bits for the same reason as regular shuffling. There are n! permutations and it therefore takes log(n!) bits to uniquely describe a shuffle. nlog(n) is the same as log(n^n) which is obviously greater than log(n!) (this is Stirling’s approximation).
OK, but I was kind of hoping for a treatment that involved the workings of one or both algorithms. They are subject to the same theoretical lower bound, yes. Do they have any advantages or disadvantages relative to each other? Does one of them do a much better job reaching the theoretical bound?
This paper goes in way more detail than you'd likely ever want on that topic: https://dl.acm.org/doi/10.1145/3009909.
It kind of makes me mad that the very simple RS algorithm (divide and conquer) isn't more widely known given that it's so easy to implement and that it's actually parallelizable unlike Fisher-Yates. I think it's also better pedagogically since you can easily do it with a deck of cards and a coin or some dice while Fisher-Yates is pretty unwieldy for anything beyond very small lists.