[HN Gopher] 52 Factorial
___________________________________________________________________
52 Factorial
Author : Amorymeltzer
Score : 64 points
Date : 2024-10-02 19:22 UTC (2 days ago)
(HTM) web link (czep.net)
(TXT) w3m dump (czep.net)
| tmtvl wrote:
| So if I want a collection of card decks in every possible
| combination I should start collecting now, got it.
| dsamarin wrote:
| With this, you could invent a very unique magic trick where
| your spectator well-shuffles a deck of cards, then you can
| secretly swap your deck with one of the decks from your
| collection to reveal that yours was shuffled in the exact same
| way.
| vunderba wrote:
| This is a relatively well known technique in card
| manipulations known as a "cold deck". There are _many_
| variations of it involving probabilistic but not entirely
| _deterministic_ forces that lead to a branching path to a
| different cold deck.
| nabla9 wrote:
| mass of Earth is 6x10^27 kg
|
| mass of the Milky Way is 6x10^42 kg
|
| mass of the visible Universe is 1.5x10^53 kg
|
| Quality deck of cards weighs 0.3 kg. All deck combinations
| would weigh 2.4x10^67 kg.
|
| = 10^14 times the mass of the visible Universe.
|
| You need many multiverses to store all those cards.
| pixl97 wrote:
| Or just make each deck 10^14 times smaller
| altruios wrote:
| That would be a serious magic trick, as that's the
| explanation given to the rubes.
|
| Some sort of auto-shuffling machine with some computer vision
| to match the shuffling in real time... still a magic trick, a
| different kind of impressive. But that guy who makes robots
| at home and does videos would love a project like this. I
| seriously doubt it would work.
| SwiftyBug wrote:
| Is it safe to say that it's almost certain that no two people
| have ever shuffled a deck of cards in the exact same order?
| immibis wrote:
| No, due to suboptimal shuffling strategies. If you shuffle
| exactly the wrong way, you can even end up with the cards in
| their original order.
| RyanCavanaugh wrote:
| Yep, this. Matt Parker makes a convincing argument that
| multiple people have accidently performed a perfect Faro
| shuffle when trying to randomize a new deck of cards
|
| https://www.youtube.com/watch?v=s9-b-QJZdVA
| Workaccount2 wrote:
| Given the set of people who can competently shuffle a deck of
| cards. No, there has never been an identical deck, and there
| never will be. This would be true even if every human ever
| dedicated their entire life to randomly shuffling decks looking
| for a repeat.
|
| Even if all compute on earth was focused on shuffling as many
| decks as fast as possible, we still wouldn't ever get two
| identical decks. Even after hundreds of millions of trillions
| of years.
|
| The odds of getting two identical shuffles is somewhere around
| the odds of picking the correct sand grain sized piece of
| matter, out of all matter in the Milky Way.
| RAM-bunctious wrote:
| That would only be safe if you assumed everyone shuffled well.
|
| The likelihood that more than one person used a poor or lazy
| shuffling technique on a brand new deck of cards seems
| significant.
| wduquette wrote:
| In terms of actually playing games with cards, the effective
| number of permutations can be much smaller (though still large
| enough to be going on with). In many card games, the suits are
| distinct but functionally identical; you could swap spades rank-
| for-rank with hearts and get a functionally equivalent deck. In
| Klondike solitaire, the tableau is concerned with red cards and
| black cards, not all four suits.
|
| I imagine somebody has done research on this: for a given card
| game, how many functionally distinct shuffles there are.
| wduquette wrote:
| I remember looking at some early Draw Poker machines in Las
| Vegas back in the late 80's/early 90's, and thinking about
| pseudo-random number generation (as it existed at that time).
| If it was using a standard linear-congruential RNG with a 16
| bit value, there would be only 65536 possible seeds, and hence
| only that many distinct sequences of random numbers, and hence
| only that many possible shuffles. Even a 64-bit RNG would have
| only 1.844674407370955e+19 possible shuffles, far lower than
| 52!.
| zaik wrote:
| ln(52!)/ln(2)[?]226 bits. You don't have to depend on a
| single random 64-bit number:
| https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle
| Straw wrote:
| If the RNG has < 226 bits of state, such as most non
| cryptographic PRNGs, you cannot reach all shuffles even if
| you use multiple numbers.
| IanCal wrote:
| I'm not totally sure that's true. I get where you are
| coming from, an 8 bit rng can only output 256 distinct
| values at most. 256 would be the longest cycle.
|
| However if you combine the outputs of two, but don't step
| them at the same time, you can have more outputs.
|
| Imagine you had one that outputs just 0 and 1 and then
| loops. You could have two of these updating at a
| different frequency and have four distinct outputs.
|
| I think that makes sense.
| wduquette wrote:
| Oh, yeah, there are ways to finesse it. I'm just
| wondering whether anyone involved in those early poker
| machines had made the effort.
| sophacles wrote:
| You're right. There are also game rules that can act as
| multipliers (e.g. who has the blind affects the game state in
| poker - so that means that there are actually multiple "games"
| for each given shuffle).
|
| Something you may find interesting is formal methods - what
| we're talking about here are "equivalence classes". In formal
| methods you want to analyze the totality of a system and
| understand every outcome based on every possible state within
| the rules of the system. Clearly this is a combinatoric
| nightmare in anything interesting (even a simple system like a
| card game and 52 cards, as we can see). Equivalence classes are
| a way of knowing distinct, but not actually different, states,
| and grouping them together so that they can all be considered
| just once.
| montefischer wrote:
| Those interested can read Mark Conger's thesis to learn about
| the mathematics of repeated cards:
| https://websites.umich.edu/~mconger/thesis.pdf
| ozyschmozy wrote:
| Pretty easy to calculate how many distinct shuffles considering
| only the numbers: 52!/(4!^13)=~9.2e49. Still monstrously big
| jrflowers wrote:
| This thought experiment gets even wilder if you like to live
| dangerously and leave two jokers and the rules card in the deck.
| 55 factorial is even _larger_
| RedNifre wrote:
| The jokers are indistinguishable, so it's only 55 factorial
| divided by two.
| kevindamm wrote:
| Sometimes they are distinct, usually one is black & white and
| the other is color.. the solitaire cipher makes use of this
| distinction.
| nabla9 wrote:
| You can use one deck to encode 225 bits of information.
| pesfandiar wrote:
| 277 if we encode information in whether each card is face up or
| down
| RedNifre wrote:
| Not quite, because you won't be able to tell the deck
| orientation any more.
| whartung wrote:
| So, then 275? With the both the top and bottom card face
| down?
|
| That's going in my next spy novel. Spy 1 gets together with
| Spy 2, for cracking game of Cribbage, and at the end, Spy 2
| walks out with a deck of cards, but it's actually a 256 bit
| encryption key.
| praptak wrote:
| Some cards are not symmetrical, (e.g. any seven or a five of
| not-diamonds) so they can encode two bits of information.
| RedNifre wrote:
| Yeah, I actually implemented this some years ago here, for
| UTF-8 text: https://github.com/Michael-Zinn/cardfs
|
| Works for Poker, Skat, Tarot and Quartett decks.
| zzo38computer wrote:
| A tarot deck has more than only trumps. It also has fourteen
| non-trumps in each of four suits (Latin-suited or French-
| suited depending on the deck), so the total number of cards
| (trumps and non-trumps) is 78.
|
| Furthermore, if you can store bytes, then why should it need
| to be UTF-8? Not all data is text, and not all text is
| Unicode (and not all Unicode text is most efficient with
| UTF-8). As far as I can tell, the only part of the program
| that requires it to be UTF-8 is the "decode_array_to_string"
| function (although I think it will have to be a string
| without embedded null characters since that is how argv is
| working, and that could possibly allow you to store a few
| more bytes, if the data is required to not have null
| characters).
| RedNifre wrote:
| Thanks for pointing this out, I did not know that there are
| other tarot decks (I only have this one
| https://steemit.com/software/@michaelzinn/store-text-in-a-
| de... )
|
| I originally had planned to store other data as well
| (that's why it's called "CardFS"): With the bytes, there is
| another multiplier 3 in there, which is unused. My plan was
| to do 0=UTF-8 text, 1=raw bytes, 2=bitmap graphic, but I
| stopped working on it after I got the UTF-8 text working.
|
| Excluding NUL characters would only up the byte count to
| floor(log_255(52!)), which is still 28 bytes (though it
| increases the unused multiplier from 2.99 to 3.1, which
| makes it possible to use all bytes in all three file
| types), but how would you then store texts that use fewer
| than the maximum number of characters? Fill it with spaces?
| nnf wrote:
| I remember reading once that every time you shuffle a deck of
| cards, it's almost certainly the first time any deck of cards has
| ever been in that configuration. Seeing how outrageously large
| 52! is puts this into perspective.
| SideQuark wrote:
| Most likely not true, since many shuffles are from a sorted
| deck (original buy, result of playing out some game, etc...).
| The 52! possibilities are certainly not uniformly spread in
| real life.
|
| With enough shuffles then you'll likely hit never before seen
| territory.
| thfuran wrote:
| And once you get there, it is likely that further shuffles
| will stay there.
| 7373737373 wrote:
| This is a good Numberphile video about it - The Best (and
| Worst) Ways to Shuffle Cards:
| https://youtube.com/watch?v=AxJubaijQbI
| hermitcrab wrote:
| Combinatorial problems are hard. The number of ways to arrange N
| guests in N seats at a seated event (such as a wedding or gala)
| is N!. Even with only 60 guests, there are already more possible
| seating permutations that there are believed to be atoms in the
| observable universe. The solution space for hundreds of guests is
| mind boggling large. I sometimes try to explain this to customers
| of my seating planning software (PerfectTablePlan) when they
| complain that the auto seating algorithm has separated 2 people
| in a 500 seat event, but I don't think many of them understand!
| montefischer wrote:
| And despite the huge size of 52!, it is possible with basic motor
| skills to produce a random deck. For those with the background
| and interest, there is a great book: The Mathematics of Shuffling
| Cards by Diaconis and Fulman, published 2023.
| erehweb wrote:
| Some debate, but it seems that ! was used for factorial to
| replace another symbol that was less easy to print
| https://math.stackexchange.com/questions/802141/history-of-n....
| danbruc wrote:
| Animated version by VSauce [1] starting at about 15 minutes.
|
| [1] https://www.youtube.com/watch?v=ObiqJzfyACM
| kimbernator wrote:
| I sometimes wake up having an anxiety attack because my dream was
| attempting to play something like this out- always something to
| do with permutations of massive numbers. It was a little bit of a
| challenge to keep it together while reading this. No idea why
| that is, either. It's the only thing that has such an effect on
| me.
| thfuran wrote:
| Have you ever dreamt of Graham's number?
| marvinborner wrote:
| I have something similar but for lambda terms with huge normal
| forms, I always wake up exhausted when this happens
| SideQuark wrote:
| > This number is beyond astronomically large.
|
| 52! ~ 10^67 is far many orders of magnitude than the number of
| particles in the universe, which is exactly an astronomical
| number.
| lostmsu wrote:
| A word got lost, but current estimates for Universe particles
| are around 10^80, so 52! is 13 magnitudes smaller.
| szvsw wrote:
| I would guess the author is a fan of Joyce:
|
| > What must it be, then, to bear the manifold tortures of hell
| forever? Forever! For all eternity! Not for a year or an age but
| forever. Try to imagine the awful meaning of this. You have often
| seen the sand on the seashore. How fine are its tiny grains! And
| how many of those tiny grains go to make up the small handful
| which a child grasps in its play. Now imagine a mountain of that
| sand, a million miles high, reaching from the earth to the
| farthest heavens, and a million miles broad, extending to
| remotest space, and a million miles in thickness, and imagine
| such an enormous mass of countless particles of sand multiplied
| as often as there are leaves in the forest, drops of water in the
| mighty ocean, feathers on birds, scales on fish, hairs on
| animals, atoms in the vast expanse of air. And imagine that at
| the end of every million years a little bird came to that
| mountain and carried away in its beak a tiny grain of that sand.
| How many millions upon millions of centuries would pass before
| that bird had carried away even a square foot of that mountain,
| how many eons upon eons of ages before it had carried away all.
| Yet at the end of that immense stretch time not even one instant
| of eternity could be said to have ended. At the end of all those
| billions and trillions of years eternity would have scarcely
| begun. And if that mountain rose again after it had been carried
| all away again grain by grain, and if it so rose and sank as many
| times as there are stars in the sky, atoms in the air, drops of
| water in the sea, leaves on the trees, feathers upon birds,
| scales upon fish, hairs upon animals - at the end of all those
| innumerable risings and sinkings of that immeasurably vast
| mountain not even one single instant of eternity could be said to
| have ended; even then, at the end of such a period, after that
| eon of time, the mere thought of which makes our very brain reel
| dizzily, eternity would have scarcely begun.
|
| (From Portrait of the Artist)
| interroboink wrote:
| And maybe Joyce was a fan of the Brothers Grimm! [1]
| "The third question is, how many seconds of time are there in
| eternity?" Then said the shepherd boy: "In Lower Pomerania is
| the Diamond Mountain, which is two miles and a half high,
| two miles and a half wide, and two miles and a half in
| depth; every hundred years a little bird comes and
| sharpens its beak on it, and when the whole mountain is worn
| away by this, then the first second of eternity will be over."
|
| [1] https://www.grimmstories.com/en/grimm_fairy-
| tales/the_shephe...
| szvsw wrote:
| Love it!
|
| I think it is a _somewhat_ common analogy in catechistic
| texts but I'm not positive. I don't think anyone could write
| it quite like Joyce though!
| lcnPylGDnU4H9OF wrote:
| The number has 12 zeroes at the end, which confused me for a bit,
| so I'm leaving this comment in case anyone else is similarly
| confused and would like to know why.
|
| There are 10 total numbers between 1 and 52 which include 5 as a
| factor (5 which also include 2 as a factor to make a factor of 10
| and 5 more to be multiplied with a bunch of other 2-factor
| numbers) so intuitively I was thinking there should be 10 zeroes.
| The two I missed are additional factors of 5, one each in 25 and
| 50.
| gjm11 wrote:
| The cute general theorem is: if p is a prime number then the
| number of times p divides n factorial is floor(n/p) +
| floor(n/p^2) + floor(n/p^3) + ...
|
| And from this (or by other arguably more elegant means) one can
| get the related cute theorem: the number of times p divides the
| binomial coefficient (n choose r) is the number of _carries_
| that occur when adding r to n-r in base p.
|
| In particular, if n = p^k then unless r=0 or r=n there is
| always at least one carry because n is "longer" than r and n-r,
| so all the binomial coefficients (p^k choose r) are multiples
| of p apart from (p^k choose 0) and (p^k choose p^k).
|
| (You can use this sort of idea to understand why, if you write
| out many many rows of Pascal's triangle mod 2, you get a sort
| of Sierpinski gasket thing.)
| jll29 wrote:
| 52! is not small. Yet factorials grow slowly compared to the
| Ackerman function or "busy beavers":
|
| https://www.quora.com/What-is-the-fastest-growing-mathematic...
| OldGuyInTheClub wrote:
| Youtuber "But Why" marvels at the size of 52! in
| https://www.youtube.com/watch?v=hoeIllSxpEU and then tries to
| relate it to something graspable by humans
| https://www.youtube.com/watch?v=RdnVhjYFr7w
___________________________________________________________________
(page generated 2024-10-04 23:01 UTC)