5 ms·

It's always been pretty mind-blowing to me that you can store over 225 bits of information just in an ordering of one deck of cards. A standard way to store dat

It's always been pretty mind-blowing to me that you can store over 225 bits of information just in an ordering of one deck of cards. A standard way to store data in this way is a factoradic encoding like Lehmer coding: https://en.wikipedia.org/wiki/Lehmer_code https://en.wikipedia.org/wiki/Lehmer_code The python library 'permutation' has some functionality around this that's fun to play with: https://permutation.readthedocs.io/en/stable/#permutation.Permutation.lehmer https://permutation.readthedocs.io/en/stable/#permutation.Pe... I found new joy in shuffling a deck of cards, after learning that every (proper) shuffle that every human's ever done has returned a unique deck that nobody's ever held before. edit: I just remembered a guy who made a javascript demo that encodes small strings into a card deck order: https://jerde.net/peter/cards/cards.html https://jerde.net/peter/cards/cards.html (explanation page linked)

randombits0 3y ago
What? No, you can store 52! unique states with a pack of playing cards. Just map each state to a data set. /j
- LoganDark 3y ago
  `52!` is indeed between 225 and 226 bits of information. > 52! = 80,658,175,170,943,878,571,660,636,856,403,766,975,289,505,440,883,277,824,000,000,000,000 > 2^225 = 53,919,893,334,301,279,589,334,030,174,039,261,347,274,288,845,081,144,962,207,220,498,432 > 2^226 = 107,839,786,668,602,559,178,668,060,348,078,522,694,548,577,690,162,289,924,414,440,996,864
  - bscphil 3y ago
    You can show this with a easy one-liner in a lot of languages, e.g. Julia: $ julia -E 'log2(factorial(big(52)))' 225.581003123702761946342444376665612911126819036757601937313805865615023286654 (It's also just math, of course, but it's nice to have a quick way to check these things.)
    - polygamous_bat 3y ago
      Since log(xy) = log(x) + log(y), you can simply calculate sum(log2(i) for i in range(1, 53)) :) might be a nicer formulation for when you don’t have arbitrary precision support.
    - zimpenfish 3y ago
      Or you can use the `bc` that's shipped with macOS. echo 'l(f(52))/l(2)' | bc -l 225.58100312370276194868 (`l(x)` is natural log, hence the `/l(2)` to convert to `log2`) Annoyingly, GNU `bc` doesn't have `f(x)`.
  - plusplusungood 3y ago
    I used this fact in an interview ages ago. The interviewer wanted a function, in Java, that shuffled a deck of cards such that every permutation was equally likely. I pointed out this was not possible using the standard library random functions since the seed is a long (akshually... it's 48 bits). They inexplicably hired my know-it-all ass...
kqr 3y ago
Yeah, combinatorics is neat and frightening. It's crazy things have sensible probabilities at all, but surprisingly often the virtual numerator and denominator are of comparable size, despite the magnitudes involved.

randombits0 3y ago

What? No, you can store 52! unique states with a pack of playing cards. Just map each state to a data set. /j

LoganDark 3y ago
`52!` is indeed between 225 and 226 bits of information. > 52! = 80,658,175,170,943,878,571,660,636,856,403,766,975,289,505,440,883,277,824,000,000,000,000 > 2^225 = 53,919,893,334,301,279,589,334,030,174,039,261,347,274,288,845,081,144,962,207,220,498,432 > 2^226 = 107,839,786,668,602,559,178,668,060,348,078,522,694,548,577,690,162,289,924,414,440,996,864
- bscphil 3y ago
  You can show this with a easy one-liner in a lot of languages, e.g. Julia: $ julia -E 'log2(factorial(big(52)))' 225.581003123702761946342444376665612911126819036757601937313805865615023286654 (It's also just math, of course, but it's nice to have a quick way to check these things.)
  - polygamous_bat 3y ago
    Since log(xy) = log(x) + log(y), you can simply calculate sum(log2(i) for i in range(1, 53)) :) might be a nicer formulation for when you don’t have arbitrary precision support.
  - zimpenfish 3y ago
    Or you can use the `bc` that's shipped with macOS. echo 'l(f(52))/l(2)' | bc -l 225.58100312370276194868 (`l(x)` is natural log, hence the `/l(2)` to convert to `log2`) Annoyingly, GNU `bc` doesn't have `f(x)`.
- plusplusungood 3y ago
  I used this fact in an interview ages ago. The interviewer wanted a function, in Java, that shuffled a deck of cards such that every permutation was equally likely. I pointed out this was not possible using the standard library random functions since the seed is a long (akshually... it's 48 bits). They inexplicably hired my know-it-all ass...

kqr 3y ago

Yeah, combinatorics is neat and frightening. It's crazy things have sensible probabilities at all, but surprisingly often the virtual numerator and denominator are of comparable size, despite the magnitudes involved.