patternMinor
Is there a random shuffle algorithm using only true /false?
Viewed 0 times
randomtruealgorithmfalseusingshufflethereonly
Problem
Is there a way to randomly shuffle an array using only a source of random boolean values? SO to clarify, shuffle using true /false only, and not integers or decimals.
For this question, I'm specifically excluding an approach whereby the booleans are just arranged into an integer and then it's used in a Fisher-Yates shuffle. I'd be repeatedly shuffling approximately 30,000 items and have a ready source of random booleans. I'd need to build up a very large integer for Fischer-Yates to avoid any form of bias in the shuffle. Can this step be avoided and true /false used directly somehow? I have the sense that some soft of bubble sort might do it, with the comparison determined randomly, but I can't quite flesh it out.
I'd be interested in any algorithm than wasn't ridiculous i.e. with a stupid time complexity of something like 2^O(n). This question builds upon some of the concepts of Best random permutation employing only one random number but isn't identical.
For this question, I'm specifically excluding an approach whereby the booleans are just arranged into an integer and then it's used in a Fisher-Yates shuffle. I'd be repeatedly shuffling approximately 30,000 items and have a ready source of random booleans. I'd need to build up a very large integer for Fischer-Yates to avoid any form of bias in the shuffle. Can this step be avoided and true /false used directly somehow? I have the sense that some soft of bubble sort might do it, with the comparison determined randomly, but I can't quite flesh it out.
I'd be interested in any algorithm than wasn't ridiculous i.e. with a stupid time complexity of something like 2^O(n). This question builds upon some of the concepts of Best random permutation employing only one random number but isn't identical.
Solution
No, there is no algorithm that shuffles an array of length $n > 2$ using a bounded number of random Booleans. This is because given an algorithm that uses $m$ random bits (at most), each outcome has a probability of the form $A/2^m$, whereas we need each possible permutation to have probability $1/n!$.
When you're using Fisher–Yates shuffle in the form you describe you aren't getting a uniformly random permutation, though you are getting something very close. If you want to get a truly uniform random permutation then you need to use some form of rejection sampling.
Using bubble sort in the way you describe would likely be a disaster – it would likely result in a random permutation which is easy to distinguish from uniform. Don't do that. There are no tricks and shortcuts. If you want your random permutations to be faster at the cost of being slightly less uniform, you can reduce the precision involved in approximating random integers inside the Fisher–Yates shuffle. This will probably be much better than inventing your own algorithm.
When you're using Fisher–Yates shuffle in the form you describe you aren't getting a uniformly random permutation, though you are getting something very close. If you want to get a truly uniform random permutation then you need to use some form of rejection sampling.
Using bubble sort in the way you describe would likely be a disaster – it would likely result in a random permutation which is easy to distinguish from uniform. Don't do that. There are no tricks and shortcuts. If you want your random permutations to be faster at the cost of being slightly less uniform, you can reduce the precision involved in approximating random integers inside the Fisher–Yates shuffle. This will probably be much better than inventing your own algorithm.
Context
StackExchange Computer Science Q#51166, answer score: 7
Revisions (0)
No revisions yet.