-
-
Save Uradamus/10323382 to your computer and use it in GitHub Desktop.
| function shuffle(tbl) | |
| for i = #tbl, 2, -1 do | |
| local j = math.random(i) | |
| tbl[i], tbl[j] = tbl[j], tbl[i] | |
| end | |
| return tbl | |
| end |
The math is not complicated. It's a truly random shuffle, so the odds of getting the same deck again (or any specific deck) is 1/N! since N! is the full number of possible decks.
To demonstrate, if you have 52 cards, and you pick the first one randomly, there are 52 possibilities. Then you pick the next card from 51 possibilities. Then pick a card from 50.. So 52x51x50x... is 52!. And that is pretty much exactly what Fisher-Yates is doing. It looks complicated, but it's not, it's doing a random selection of a new card from all cards that are still available.
Correct. But for my method, the math is much more complicated because passed cards can be changed by future swaps. So I wrote some code to brute force it, and the odds of getting exactly the same deck are slightly lower with my method.
[edit] Now, average difference is a bit different, and if you have a quick way to calculate it, I'd love to hear it.
[edit2] I did a four card deck by hand and it got 76.042% vs 76.368% change: My method is slightly more random. I'll have to write code for the original F-Y method if I want to go beyond that, because no way am I doing a 5+ card deck by hand...
[edit3] I redacted my 3-card findings because I made an error. The real figures were 66.6…% vs 67.9% between original Fisher-Yates and my variation.
So, to summarize, my variation does introduce greater changes, but it does not matter much—the difference is very slight.
I don't know what you mean by 'greater changes' but your variation is less random.
For either method, there is a finite number of outcomes. My script tallied up every outcome of a deck size up to 7 and compared each to the original deck to get a count of indexes with different values. I took the average of those and divided by the deck size to get a percentage of change. Those are the figures being compared a few posts ago that are very slightly higher than the percentage of average change using the original method. I also proved that the chance of ending up with an unchanged deck is smaller. So if you want to claim that it's less random, you'll have to come up with another metric to judge it by, but those are the two that make sense to me.
You've done a lot of rambling about how the original FY method operates, which was obvious from the start, but you haven't said one word, let alone, say, some math? to prove that is more random by limiting its swaps as it goes.
First we can define randomness. If you look at the outcome of a shuffle given an specific initial deck, what are the odds of getting every possible deck? If the odds are the same for every possible deck (say 1/N for N possible decks) and this is regardless of the starting deck, they we know we have a fully random shuffle. You can't get "more" random than that. Anything that doesn't accomplish that is a less random shuffle.
In the simplest case, a coin flip is fully random if the outcome of the flip (two possible states) have equal probability (50%), and it's regardless of it's initial state. Anything that differs from that is less random.
If you want to have a different definition of random, then that's up to you, but you're going to be disagreeing with the rest of the world, and we probably don't need to bother with this conversation further.
F-Y is fully random. I believe I proved that above, but if you need me to clarify how, I'd be happy to try.
The reason it works is by limiting the two swaps, and I believe I clarified that above as well.
There are other possible ways to shuffle a deck, that's for sure. But if you take the F-Y method and simply remove the limiting of the swap candidate to include the last cards as well, then it cannot possibly "introduce greater changes" in terms of randomness, since F-Y is already as random as a shuffle can be.
The reason your suggestion is problematic requires fully appreciating what FY is doing.
FY is essentially taking a deck of cards and then picking a random card, and putting it in a new pile. Then pick another random card and add it to the top of that pile, and continue until you've gone through all the cards.
Your suggestion is to take a deck of cards, and then pick a random card, and put it in a new pile. Then you pick another random card, either from the old pile, or the new pile, and put it in the new pile. And you do this the same number of times as F-Y, which is once for the number of cards you have.
You'll find that a couple of things happen. In F-Y, every card is "touched" - in the sense that every card has a chance of being moved to every possible location with equal probability. Just what we want from a "shuffle". In your version, you are more likely to leave a card in it's original location.
To see that with math, considering the cards you are picking as candidates for the swap, looking at a 52 card deck.
In FY, we pick a random card for the first swap. Then we pick one of the remaining 51. Then one of the remaining 50. And so on. Every single card is guaranteed to be selected for one of the 52 swaps. And each of those swaps has an equal chance of going to one of the 52 final locations. Genius.
In your version, when you select a card to swap, you are randomly selecting from the original deck as well as the new deck.
But you want math, so I'll give you math. And it turns out, I don't even have to write it out myself, because all it took was a quick search. Here's a fantastic article on the topic:
And here's a great article explaining why FY is brilliant and has some animation to show it:
Oh, nice! They explained it way better than you did! Shoulda posted that first. Thanks!
I would say that truly shuffled decks can and do have similarities to unshuffled decks, and that the true Fisher Yates method also leaves the possibility of cards remaining where they were. To determine whether the chances are lesser or greater would require a lot of statistical math, though, so I'll just have to assume Fisher and Yates did that math.
For example, with a two-object array, the odds of it staying the same are 50% for either method—for the original method because there's only one iteration, and for my method because there are four outcomes (swap-swap, swap-noswap...) that are split in results. For a three-object array, the original method has a 1/6 chance to leave the whole thing untouched, but my method has a 4/27 chance—slightly lower.