Hacker News Reader

Comment by cypherpunks01 | Hacker News Reader

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

The python library 'permutation' has some functionality around this that's fun to play with:

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 (explanation page linked)

View on HN

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.

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

`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

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...

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.)

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.

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)`.

Reply on news.ycombinator.com