5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Could you use bitonic sort and provide your true/false to comparators? This way you avoid "bubbling" effect or giving pivots to quicksort. $\endgroup$ – Evil Dec 27 '15 at 3:08
  • $\begingroup$ @EvilJS Interesting. Since there is no natural order to a random permutation, there can be no UP or DOWN. Can the bitonic sort ever complete therefore, or will it just run ad-infinitum? $\endgroup$ – Paul Uszak Dec 27 '15 at 23:58
  • $\begingroup$ I mean sorting network, it has constant number of operations disregarding the input, therefore your compares on comparators will give you shuffle. Bitonic net, you can run it in serial, and instead of comparing two numbers you provide your own. So it will end sorting in exactly same number of steps as always. Sorting net - this is to be sure we are on the same page. As Yuval Filmus said - this disaster is highly skewed characteristic, because each "bubble" has decreasing probability of moving... $\endgroup$ – Evil Dec 28 '15 at 1:33
  • $\begingroup$ @EvilJS I seem to be falling between the gap created by your sorting network solution and Yuval's comment regarding its' impossibility... $\endgroup$ – Paul Uszak Dec 28 '15 at 13:38
  • $\begingroup$ Sorting network will give you nicer shuffle, bubble sort will give you disasterous shuffle, but providing small number of random boolean - sorting network will consume more bits, will look nicer, but this is handmade solution, to get pure uniform distribution you have to provide much more random bits. $\endgroup$ – Evil Dec 28 '15 at 14:43
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Does your "No" include EvilJS' bitonic sort method? It seems to operate on a bounded number of Booleans and looks promising with a cursory inspection. It might also eliminate the usual modulo n bias from a classical RAND(n) function. $\endgroup$ – Paul Uszak Dec 28 '15 at 1:54
  • $\begingroup$ No algorithm using a bounded number of uniformly random bits can shuffle even an array of length $n = 3$. $\endgroup$ – Yuval Filmus Dec 28 '15 at 6:32
  • $\begingroup$ one has to distinguish between problems with an algorithm itself and problems related solely to finite-length effects, truncation and quality of pseudo-random number generators. In this sense fisher-yates-knuth shuffle is both optimal and unbiased shuffle, any other issues are related solely to finite-length effects and prngs involved and not the algorithm per-se $\endgroup$ – Nikos M. Dec 31 '15 at 20:46
3
$\begingroup$

Referring to a $b$-bit number as $b$ individual bits or vice-versa doesn't change the number of random bits you need. If you need a gazillion bits when you consider them as forming integers, you need a gazillion bits when you consider them as individual tosses of a fair coin.

$\endgroup$
  • $\begingroup$ yes, but it was not the question on how many bits, but on how to do that ? $\endgroup$ – guillaume girod-vitouchkina Dec 27 '15 at 14:10
  • $\begingroup$ Generate your $k$-bit random number one bit at a time. $\endgroup$ – David Richerby Dec 27 '15 at 15:55
0
$\begingroup$

Why not converting booleans to integer, and using Fischer-Yates ?

If you have n elements, you will have n! possible permutations.

Let us use FYK algorithm (supposing it is almost good).

Then you will need:

  • choose among n : say n = 2^k_n
  • then choose among n-1 : says n=2^k_n-1
  • etc.

So you need sum(k_n,k_n-1, ...) = P, where 2^P=n! (approximately, because every n, n-1, ... is not a power of 2.

1 So you need P booleans, where 2^P=n!

2 FYK needs almost minimal time: you have to make n changes (difficult to do less). and cutting/converting bits is minimal. You even can struct your array in some of binary tree.

$\endgroup$
  • $\begingroup$ This doesn't quite work. $\endgroup$ – Yuval Filmus Dec 27 '15 at 13:49
  • $\begingroup$ @YuvalFilmus could you be more precise ? what doesn't work ? $\endgroup$ – guillaume girod-vitouchkina Dec 27 '15 at 13:51
  • $\begingroup$ You can only choose among $m$ options using $\log_2 m$ bits if $m$ is a power of 2. $\endgroup$ – Yuval Filmus Dec 27 '15 at 13:52
  • $\begingroup$ @YuvalFilmus Yes, but what is the problem ? if you have enough bits (and you must have to get every cases), then you can apply the algorithm. $\endgroup$ – guillaume girod-vitouchkina Dec 27 '15 at 14:08
  • 3
    $\begingroup$ You can't choose between 5 using just 3 bits. You won't get a uniform choice. $\endgroup$ – Yuval Filmus Dec 27 '15 at 16:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.