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.

Improve this question
$\endgroup$
7
  • $\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, 2015 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, 2015 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, 2015 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, 2015 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, 2015 at 14:43

4 Answers 4

Reset to default
7
$\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.

Improve this answer
$\endgroup$
3
  • $\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, 2015 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, 2015 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, 2015 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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ yes, but it was not the question on how many bits, but on how to do that ? $\endgroup$
    – guillaume girod-vitouchkina
    Dec 27, 2015 at 14:10
  • $\begingroup$ Generate your $k$-bit random number one bit at a time. $\endgroup$
    – David Richerby
    Dec 27, 2015 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.

Improve this answer
$\endgroup$
7
  • $\begingroup$ This doesn't quite work. $\endgroup$
    – Yuval Filmus
    Dec 27, 2015 at 13:49
  • $\begingroup$ @YuvalFilmus could you be more precise ? what doesn't work ? $\endgroup$
    – guillaume girod-vitouchkina
    Dec 27, 2015 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, 2015 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, 2015 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, 2015 at 16:29
0
$\begingroup$

You actually can use true / false to simulate a Riffle Shuffle or Faro Shuffle:

  1. Start with the deck of cards on the middle
  2. Move half of the deck to the left, and half to the right
  3. Get a boolean: if true, then move the top card from the left pile back to the middle, or if false, move that top card from the right pile back to the middle
  4. Repeat step 3 until all cards are back to the middle

There can be a variation of step 3: if another boolean is true, move 1 card, otherwise, move 2 cards.

Another variation:

  1. Start with the deck of cards on the middle
  2. Get a boolean: if true, then move the top card to the left pile, or if false, move that top card to the right pile
  3. Repeat step 2 until all cards in the middle are gone.
  4. Now merge the left and right pile of cards by taking 1 card from each pile alternatively and putting them back into one pile

You can also use boolean to say, move 1 card vs 2 cards in step 2. Also a boolean for step 4: if true, move one card from the left pile card during merging, but if false, moving one card from the right pile card during merging instead.

But you probably have to do it 7, 8 times to get a pretty good shuffle.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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