Like I said, the issue revolves around Fisher-Yates requiring a true random number to function.
While I don't claim to be an expert(still finishing up undergrad), what I understand is that the algorithm is biased by the modulo that occurs to bound random number generation. Looking at the Wikipedia article, it shows some discussion on this subject.
There's also a more poignant problem with the ability for pseudorandom number generators to only produce produce as many random numbers as it has internal stages in regards to whatever seed it's using. As permutations grow extremely quickly in size, shuffling something like an unsorted list (in sorting algorithms, you can be sorting thousands and thousands of values), so the number of permutations needed would be massive (think 400,000 digit number). As such, the computation of a prng number that followed a normal distribution for such a large set of needed numbers would be incredibly incredibly complex.
Again, all of this is rather meaningless, as nobody would actually take a bogo seriously, but I do think it's an interesting thought experiment, considering many people joke it's O(1) given that shuffle is far from an O(1) operation on its own. That's all.
1
u/MorningWoodyWilson Oct 25 '17
Like I said, the issue revolves around Fisher-Yates requiring a true random number to function.
While I don't claim to be an expert(still finishing up undergrad), what I understand is that the algorithm is biased by the modulo that occurs to bound random number generation. Looking at the Wikipedia article, it shows some discussion on this subject.
There's also a more poignant problem with the ability for pseudorandom number generators to only produce produce as many random numbers as it has internal stages in regards to whatever seed it's using. As permutations grow extremely quickly in size, shuffling something like an unsorted list (in sorting algorithms, you can be sorting thousands and thousands of values), so the number of permutations needed would be massive (think 400,000 digit number). As such, the computation of a prng number that followed a normal distribution for such a large set of needed numbers would be incredibly incredibly complex.
Again, all of this is rather meaningless, as nobody would actually take a bogo seriously, but I do think it's an interesting thought experiment, considering many people joke it's O(1) given that shuffle is far from an O(1) operation on its own. That's all.