5 ms·

The correct Fisher-Yates shuffle is this (from Wikipedia): -- To shuffle an array a of n elements (indices 0..n-1): for i from 0 to n−2 do j ← random

The correct Fisher-Yates shuffle is this (from Wikipedia): -- To shuffle an array a of n elements (indices 0..n-1): for i from 0 to n−2 do j ← random integer such that i ≤ j < n exchange a[i] and a[j]

seanhunter 4y ago
Right. The subtle difference being that because you only sample from position i to n you only ever exchange each card exactly once. In my algo you sample from 0 to n-1 so a card exchanged in a previous round can be exchanged again. This generalises into cards early in the shuffle being exchanged more than later cards, which changes the distribution of possible outcomes. Nerd sidenote: Because generating random numbers tends to be expensive, I had an idea once where you generate the full permutation with only a single random sample. Basically you could use something which fully enumerates a space like Gray codes[1] (you want one with a closed form solution which can arbitrarily you the nth code) then you generate one random number, multiply by the number of combinations, look up that code and decode that into the sequence of cards. I never actually got around to implementing it, but I suspect if your code lookup was fast it would be much faster than Fisher-Yates. The use case was if you wanted to make a Monte Carlo algorithm to evaluate strategies in a card game for instance. [1] https://en.wikipedia.org/wiki/Gray_code https://en.wikipedia.org/wiki/Gray_code
- 6keZbCECT2uB 4y ago
  I've wondered about the same thing of generating a permutation with a minimum number of samples. I'm not sure how Gray codes helps you here, and the multiplication sounds wrong since many outputs aren't reachable from any input.
  - seanhunter 4y ago
    The idea is just a closed form solution that gets you from a number in 1...nPermutations to a single specific permutation. I was using Gray codes as an example of a sequence that exhausts all permutations with a closed form that gets you to a specific point in the sequence. Might not work - as I say I never actually got around to implementing it.
    - erikstrand 4y ago
      I think you're looking for a factorial number system [1] and/or Lehmer code [2]. [1] https://en.wikipedia.org/wiki/Factorial_number_system https://en.wikipedia.org/wiki/Factorial_number_system [2] https://en.wikipedia.org/wiki/Lehmer_code https://en.wikipedia.org/wiki/Lehmer_code
      - seanhunter 4y ago
        Thanks!
- Someone 4y ago
  You’ll find that the number of ways to shuffle a card pack (52!) is about 8 × 10⁶⁷, so even if your RNG returns 64 bits, you can’t use a single call. Also, you’ll have to make sure you pick each permutation is picked with equal probability. random() % factorial(52) likely won’t work because your RNG won’t return integers in a range k × 52! for some k > 1 (https://stackoverflow.com/questions/10984974/why-do-people-say-there-is-modulo-bias-when-using-a-random-number-generator https://stackoverflow.com/questions/10984974/why-do-people-s...)
- Adverblessly 4y ago
  I wrote that code for fun 15-20 years ago (code definitely lost in the mists of time). You can think of it as rolling one random number up to n!, then use x%n to pick the first element and then x/n to pick the next (n-1) elements (so the next step is then to pick the second element with (x/n)%(n-1) and use (x/n)/(n-1) for the remaining (n-2) elements). Though as a sibling comment points out, since you need a random number up to n!, even 64 bits of randomness only get you so far (I think up to 20, but didn't check my math).
andromeduck 4y ago
The n-2 bit is unnecessary and misleading because we've already established that an index can be swapped with itself. for i in [0..n-1] swap(a[i], a[rand in [i..n-1]) where rand in [I..n-1] coud be implemented as i + (rand() % (n-i)) essentially start with your finger at 0, pick a card from the unpicked set which is everything on and after your finger, swap that card with your finger, move your finger up one card
abetusk 4y ago
For those interested, I wrote a small article on the various was of writing incorrect Fisher-Yates [0]. The post also covers generating single cycle permutations. Fisher-Yates is pretty obvious but weirdly subtle in some ways. For someone not paying attention, it would be easy to get wrong, as the grandparent response points out. [0] https://mechaelephant.com/dev/Fisher-Yates-Shuffle.html https://mechaelephant.com/dev/Fisher-Yates-Shuffle.html
- vmilner 4y ago
  Interestingly the method used to deal bridge hands for top tournaments doesn’t shuffle at all, it generates a random number between 1 and 52!/(13!^4) and maps that number to a corresponding deal of the cards.
  - LudwigNagasena 4y ago
    Are you sure they do bijective mapping instead of simply running a RNG with the given seed?
    - vmilner 4y ago
      Yes - see the “Making bridge deals” section of: https://sater.home.xs4all.nl/doc.html https://sater.home.xs4all.nl/doc.html

seanhunter 4y ago

Right. The subtle difference being that because you only sample from position i to n you only ever exchange each card exactly once. In my algo you sample from 0 to n-1 so a card exchanged in a previous round can be exchanged again. This generalises into cards early in the shuffle being exchanged more than later cards, which changes the distribution of possible outcomes. Nerd sidenote: Because generating random numbers tends to be expensive, I had an idea once where you generate the full permutation with only a single random sample. Basically you could use something which fully enumerates a space like Gray codes[1] (you want one with a closed form solution which can arbitrarily you the nth code) then you generate one random number, multiply by the number of combinations, look up that code and decode that into the sequence of cards. I never actually got around to implementing it, but I suspect if your code lookup was fast it would be much faster than Fisher-Yates. The use case was if you wanted to make a Monte Carlo algorithm to evaluate strategies in a card game for instance. [1] https://en.wikipedia.org/wiki/Gray_code https://en.wikipedia.org/wiki/Gray_code

6keZbCECT2uB 4y ago
I've wondered about the same thing of generating a permutation with a minimum number of samples. I'm not sure how Gray codes helps you here, and the multiplication sounds wrong since many outputs aren't reachable from any input.
- seanhunter 4y ago
  The idea is just a closed form solution that gets you from a number in 1...nPermutations to a single specific permutation. I was using Gray codes as an example of a sequence that exhausts all permutations with a closed form that gets you to a specific point in the sequence. Might not work - as I say I never actually got around to implementing it.
  - erikstrand 4y ago
    I think you're looking for a factorial number system [1] and/or Lehmer code [2]. [1] https://en.wikipedia.org/wiki/Factorial_number_system https://en.wikipedia.org/wiki/Factorial_number_system [2] https://en.wikipedia.org/wiki/Lehmer_code https://en.wikipedia.org/wiki/Lehmer_code
    - seanhunter 4y ago
      Thanks!
Someone 4y ago
You’ll find that the number of ways to shuffle a card pack (52!) is about 8 × 10⁶⁷, so even if your RNG returns 64 bits, you can’t use a single call. Also, you’ll have to make sure you pick each permutation is picked with equal probability. random() % factorial(52) likely won’t work because your RNG won’t return integers in a range k × 52! for some k > 1 (https://stackoverflow.com/questions/10984974/why-do-people-say-there-is-modulo-bias-when-using-a-random-number-generator https://stackoverflow.com/questions/10984974/why-do-people-s...)
Adverblessly 4y ago
I wrote that code for fun 15-20 years ago (code definitely lost in the mists of time). You can think of it as rolling one random number up to n!, then use x%n to pick the first element and then x/n to pick the next (n-1) elements (so the next step is then to pick the second element with (x/n)%(n-1) and use (x/n)/(n-1) for the remaining (n-2) elements). Though as a sibling comment points out, since you need a random number up to n!, even 64 bits of randomness only get you so far (I think up to 20, but didn't check my math).

andromeduck 4y ago

The n-2 bit is unnecessary and misleading because we've already established that an index can be swapped with itself. for i in [0..n-1] swap(a[i], a[rand in [i..n-1]) where rand in [I..n-1] coud be implemented as i + (rand() % (n-i)) essentially start with your finger at 0, pick a card from the unpicked set which is everything on and after your finger, swap that card with your finger, move your finger up one card

abetusk 4y ago

For those interested, I wrote a small article on the various was of writing incorrect Fisher-Yates [0]. The post also covers generating single cycle permutations. Fisher-Yates is pretty obvious but weirdly subtle in some ways. For someone not paying attention, it would be easy to get wrong, as the grandparent response points out. [0] https://mechaelephant.com/dev/Fisher-Yates-Shuffle.html https://mechaelephant.com/dev/Fisher-Yates-Shuffle.html

vmilner 4y ago
Interestingly the method used to deal bridge hands for top tournaments doesn’t shuffle at all, it generates a random number between 1 and 52!/(13!^4) and maps that number to a corresponding deal of the cards.
- LudwigNagasena 4y ago
  Are you sure they do bijective mapping instead of simply running a RNG with the given seed?
  - vmilner 4y ago
    Yes - see the “Making bridge deals” section of: https://sater.home.xs4all.nl/doc.html https://sater.home.xs4all.nl/doc.html