Talk:Shuffling

Opening comment

Do not delete this page because someone will say "This isn't an encyclopedia article", as it is useful. -- 67.20.29.3 22:03, 2 Apr 2004 (UTC)

---

I discovered (I'm sure I'm not the first) a constant time variation on the so-called Knuth shuffle. It is a specialized use, but I think it worth mentioning. This assumes a pre-existing permutation (which may or may not be sorted). Whatever card (or element or whatever) you are currently on, swap that card with itself or any card remaining. It is not necessary to apply the swaps to cards which have not been drawn. If one is starting a new game, it is NOT necessary to shuffle remaining cards.

---

Somebody who has a copy of Knuth handy should put his references in for who he got the "Knuth Shuffle" from. While it has his name attached, I distinctly recall that he cites other sources for it. I invented it independently :-) well before I knew about Knuth, so I imagine it has been invented a million times previously...

I submit'd the link on the main shuffle page for http://crystalpoker.net/securityreview.php I looked on the net for several hours trying to find a good article on shuffling algorithsm for real world scenarios. all the articles linked in external links didn't even give me any practical good data. so i figured that putting the link would be worth it to help others. so thats' why i put it on the page

I'm going to delete all final periods within each paragraph to increase productivity. Filefire

And That article will probably be in print in dr.doobs and a few other tech magazines in a few weeks too i bet. Just checked the site, they just put the article up a few days ago.

"Also I'm told : Donald E Knuth, The Art of Computer Programming (Chapter 3.4.2), and he also gives the original publishers of this algorithm: L.E.Moses and R.V.Oakford (1963) and R Durstenfeld (1964)" - 82.163.24.100 21:34, 9 July 2007 (UTC)

Riffle and Faro are really the same

The Riffle shuffle and Faro shuffle are the same thing. They both interleave the cards one-by-one from alternating sides, and can be done either as an in shuffle or out shuffle. They may differ by the actual way the hands are held to accomplish the shuffle, but the result is the same. The two sections should be merged. At the very least, the text needs to SAY that they are the same and there should be a link to the Faro Shuffle page from within the Riffle shuffle section. If the two sections are not merged, then at least the Faro Shuffle section should immediately follow the Riffle shuffle section. — Preceding unsigned comment added by Tedtoal (talk • contribs) 22:27, 5 April 2020 (UTC)

Agreed. I had previously believed that the Overhand was called Faro. I specifically came to the Talk half of this page because here the Faro and Riffle are the same thing, and it confused me. Lepome (talk) 17:27, 23 March 2023 (UTC)

Fisher and Yates

The "Knuth shuffle" is something I've previously encountered as the Fisher-Yates shuffle, e.g. see [1], [2], [3]. The first of those links cites "R. A. Fisher and F. Yates, Example 12, Statistical Tables, London, 1938.", which obviously predates any algorithms invented by Knuth. I've added a mention of the name Fisher-Yates shuffle. Graue 01:02, 29 May 2005 (UTC)

imperfect shuffling

"concluding that it did not start to become random until five good riffle shuffles, and was truly random after seven. (You would need more shuffles if your shuffling technique is poor, of course.)"

In particular, I'd like to refer to the quoted sentence in brackets. It's quite untrue. In fact, the number seven in shuffling refers more to "perfect shuffles" than anything else. Imperfect shuffling, that is, when cards from each shuffling pile do not perfectly intertwine, produce more random results, if anything. While perfect, or close to perfect, shuffling produces predictable results, imperfect shuffing does not. So I think the bracket should be simply deleted from the article, since it's mathematically incorrect.

-- anonymous

I think it is true. Let's myopically focus on the card at the very top of the deck (say it's the ace of hearts). If the deck is "truly random", then there should be an equal probability that the AoH is in any location, right?

Let's say I always grab the top of the deck with my left hand, and then grab the bottom of the deck with my right hand. Say I always flip through the half-deck in my right hand faster than the half-deck in my left hand (poor riffle shuffling technique). Then once I've used up all the cards in my right hand, all the remaining cards in my left hand get thrown on top of the stack.

No matter how many times I riffle shuffle, that ace of hearts is thrown to the top of the stack. Not very random.

Say I *try* to make it more random by occasionally grabbing the top of the deck with my other hand. After 5 shuffles, the AoH is still likely to be somewhere in the top half of the deck. Better, but still not truly random. But after a few more riffle shuffles (occasionally switching which hand grabs the top of the deck), it gets closer to truly random.

On the other hand, I agree that "perfect" riffle shuffling isn't exactly random either.

--DavidCary 23:34, 11 January 2006 (UTC)

Speed rate for shuffling

Someone should add a section on performance issues associated with different shuffling algorithms ? Maybe have a diagram with real world data, and clock cycles used, approx milliseconds, etc.. Help the real world developers.. I actually might be able to come up with some data and sample code if I come up with some free time

Have you seen http://c2.com/cgi/wiki?LinearShuffle ?

Riffle and Bridge

I disagree that the bridge "technique" after a riffle shuffle is just for showing off. On softer paper playing cards, the cards bend easily from a riffle shuffle, and the bridge bends them back, keeping them straight. 70.111.224.85 19:05, 11 January 2006 (UTC)

I also disagree with this business about the "bridge" being some kind of show-off technique. But it hardly matters whether I disagree or not; the important thing to consider here is that it's nothing but opinion, and therefore non-NPOV, and therefore doesn't belong on the Wikipedia. I've deleted the statement, along with the first sentence of the sub-section dealing with the pile shuffle, since it's not only misleading but also self-contradictory (it starts by saying the pile shuffle isn't a randomization procedure [the portion I've deleted] and then immediately goes on to say that the aim of it is to move formerly-adjacent cards apart--which, since adjacent cards tend to be adjacent because they formed runs or sets and the person holding the hands put them together, would clearly imply that it is a randomization procedure). Buck 01:32, 31 January 2006 (UTC)

I'm going to point out that pile shuffling is NONRANDOM. If the order is known before a pile shuffle, the order will be known afterwards. There's a card game called "magic: the gathering". In it, some people try to gain advantage by putting all 20 cards of one type first, then all 40 cards of another type, then pile shuffling in 3 stacks to get it into 1-2-1-2 order. It's cheating because it's not random.

Pile shuffle

The pile shuffle section contains the statement: "This is the only method of human shuffling approved in bridge when four piles are used (each pile is then assigned to the four players in this game)". This can't possibly be correct; as is correctly pointed out above, the pile "shuffle" is hopelessly non-random and wholly inadequate. Please provide a reference or remove. --LDC 14:38, 1 June 2006 (UTC)

Is it just me, or is the pile shuffle as described for use in bridge ("each pile is then assigned to the four players in this game") just a description of dealing the cards? --VinceBowdren 18:35, 21 November 2006 (UTC)

Speed

Someone changed my "five seconds" claim for the speed of a good casino shuffle to fifteen; I can't imagine any experienced poker dealer that slow being able to keep a job for long. --LDC 22:19, 3 June 2006 (UTC)

    Yeah 5 secs is fine. I can do it in 5 seconds, no problem; 15 secs is stupidly long.

I don't believe 5 seconds is possible. Maybe a video on youtube to prove it, or something?

Proposed move

Per Wikipedia:Naming conventions, shouldn't this article be at Shuffling? If there are no objections filed within a week or so, I'll move it there. howcheng {chat} 23:19, 2 October 2006 (UTC)

Knuth shuffle

"Notice that great care needs to be taken in implementing the Knuth shuffle; even slight deviations from the correct algorithm will produce biased shuffles. For example, working your way through the pack swapping each card in turn with a random card from any part of the pack is an algorithm with nⁿ different possible execution paths, yet there are only n! permutations. A counting argument based on the pigeonhole principle will clearly show that this algorithm cannot produce an unbiased shuffle, unlike the true Knuth shuffle, which has n! execution paths which match up one-to-one with the possible permutations."

Is this at all true? Obviously if there are fewer execution paths than permutations, an unbiased shuffle is impossible per the pigeonhole principle. But "overshuffling" with an algorithm that has more execution paths than permutations surely need not be biased.

In fact, I contend that this supposedly defective algorithm is in fact unbiased and equivalent to the Knuth shuffle. After operating on each card position, that position is equally likely to be any of the n cards from the deck. Subsequent operations are independent and cannot affect this. So after the algorithm is complete, every card position is totally randomized, just as in the vanilla Knuth algorithm. The only difference is that no "excess entropy" is wasted in the Knuth algorithm, which may be theoretically elegant but irrelevant in implementation.

So unless anyone can show otherwise, I propose that this entire section be removed, because it is misguided and incorrect. NTK 03:03, 26 October 2006 (UTC)

I can show otherwise. First off, the pigeonhole argument is correct; but it doesn't show how biased the results are. If every possibility had the same number, plus-or-minus one, of paths to reach it, then there really is no signifcant bias. But that is not the case.

The algorithm is to start with cards 1 through N in positions 1 through N, respectively. Then you move through each position and swap the card that is there out of the position, and a randomly selected card (which can be the same one) into it. The proof of bias is to follow the probabilities for where card N can be in this process; and it can be done descriptively rather than calculating the exact formula. The calcualtion isn't than difficult, but is not necessary for this demonstration and hard put into a text format.

Before I start, note that the probability of any specific card being chosen for any specific swap is always 1/N. Even if that card's position could be biased throughout the deck, the fact that the selection is random guarantees that every card has an equal chance of being selected.

We know that card N doesn't start position 1; so the first swap can only leave it in position N or move it out of position N and into position 1. If P(J) represents the probability of it being in position J, then P(1)=1/N, P(2) thru P(N-1)=0, and P(N)=(N-1)/N.

For the second swap, we know that card N does not start in position 2. The second swap can only leave it wherever it was (position 1 or N), or move it into position 2. The probability of it moving into position 2 is 1/N (see note above), and the probability of it remaining in position 1 now has to be less than 1/N because it could have been swapped out. So P(1)<P(2)=1/N, P(3) thru P(N-1)=0, and P(N) is immaterial.

This argument can be repeated for every swap, up until the last one. Card N cannot ever start in the position being swapped out, or in a higher position except the last one. So just before the last swap, P(1)<P(2)<P(3)...<P(N-1)=1/N, and P(N) is immaterial. In other words, a bias exists. When the last swap is performed, it has the same probability of moving card N into each of positions 1 through N-1, which will continue to be biased. The actual formula for position J, where 1<=J<=N-1, is ((N-1)^(N-J)*N^(J-1) + (N-1)^(N-1))/N^N. For a 52 card deck, card 52 has a 1.4% chance of ending up first, a 2.6% chance of ending up fifty-first, and varies monotonically in between. JeffJor 19:21, 1 May 2007 (UTC)

The pigeonhole argument is useful precisely because it's hard to reason about shuffling, because it does an end-run around all possible arguments involving tracking the state of the pack as it travels through its configuration space, and considers only apportioning outcomes to execution paths at the end of the shuffle.

For an example of how the pigeonhole argument works on the n^n shuffle, first try the simpler case of shuffling three cards, so that n=3. Then there are n^n = 27 different possible execution paths (these are the 27 things to put in the pigeonholes). But there are only 6 ways to permute three cards (these are the 6 pigeonholes to put the things in). 27 is odd, and 6 is even, so 27 things cannot be divided evenly into 6 pigeonholes. Therefore, if we assume that the execution paths are equiprobable, then the outcomes cannot be, since at least two of the different outcomes must have different probabilities. Therefore the n^n shuffle cannot be unbiased for n=3.

Now consider the full pack of playing cards. For n=52, there are 170676555274132171974277914691501574771358362295975962674353045737940041855191232907575296 possible execution paths, but only 80658175170943878571660636856403766975289505440883277824000000000000 ways to permute 52 cards. Now consider prime factors: just looking at the last digit tells you that the former number is not divisible by 5, but that the second is. Therefore the larger number cannot be divided evenly by the smaller, and so the shuffle must be biased, by the same reasoning as in the n=3 case. QED.

By the way, the argument above only provides a non-zero lowerbound to the bias of the n^n shuffle algorithm, not an estimate of the level actual level of bias in that algorithm.

-- The Anome 09:52, 26 October 2006 (UTC)

Just as a postscript to the above: if I had to implement a shuffling system, I'd use the attach-random-numbers-then-sort method, with retries if two of my random numbers collided, since it is far easier to understand, (almost) a one-liner in most decent programming languages [*], and avoids both the above issue and the modulo bias issue. While the Knuth shuffle method is cleaner and better if implemented correctly, unless computational cost was at a premium, I'd prefer to use an algorithm that is harder to get wrong, at a computational cost ratio of O(log n), than risk coding the Knuth algorithm wrongly. -- The Anome 13:03, 26 October 2006 (UTC)

[*] For example, in Python: [x[1] for x in sorted([(random(), y) for y in seq])], if you ignore the check for duplicate random numbers, and random() yields true random numbers.

Wonderful explanation! Somewhere in the mathematical portion of my brain a Rigor Alarm was going off as I typed "Subsequent operations are independent and cannot affect this." Clearly a year of law school has induced this Monty Hallesque blunder. NTK 03:24, 28 October 2006 (UTC)

Wonderful explanation indeed. I would be interested to learn whether this applies to all decks of n cards, or if there exist n for which "poor knuth shuffles" work. That reduces, I guess, to the question of whether n exists such that n^n % n! = 0. Does anyone know the answer to that? Solemnavalanche

Trivially, n = 2. Beyond that, n would have to be a number whose largest prime factor is also the largest prime less than n, which my mathematical intuition tells me isn't possible, but I can't think of a simple proof off the top of my head. --LDC 18:37, 24 February 2007 (UTC)

For n > 2, n^n is never divisible by n!, because n-1 is a factor of n! but is coprime to n^n. And btw, the true Knuth shuffle is also a one-liner in some languages. Joule36e5 (talk) 05:20, 17 April 2009 (UTC)

"riffle stacking"?

I removed [4] this sentence from the "False shuffles" section because it seemed meaningless:

It is most commonly to "stack the deck" (place cards into a desirable order) by means of one or more riffle shuffles; this is called "riffle stacking".

If I'm wrong, feel free to put it back. (But maybe explain it better: I don't know of a way to put a deck in order using anything that looks like a riffle shuffle, though I do know of ways of performing false riffle shuffles which don't disturb decks stacked previously by some other technique. And at any rate, whatever this "riffle stacking" thing is, it certainly isn't "most common"!) —Steve Summit (talk) 03:56, 11 November 2007 (UTC)

Aha. The sentence made more sense before this edit a year ago. Restoring. —Steve Summit (talk) 04:09, 11 November 2007 (UTC)

Merger proposal

I propose that Overhand shuffle be merged into shuffling as it contains no information that this one doesn't have, nor does it even define what an overhand shuffle is. further, I doubt wetter there is enough relevant information that could be added to overhand shuffle that would justify it's existence as a seperate article.131.155.215.91 (talk) 14:35, 1 December 2011 (UTC)

Or simply remove the Overhand shuffle article as it isn't really shuffling, but what people do that can't shuffle or magicians do to false shuffle.Objective3000 (talk) 15:11, 1 December 2011 (UTC)

Overhand Shuffle

Surely the overhand shuffle is not correctly described. As it stands at the moment the description is of the repetition of a simple cut. If we take the order of cards as a circular sequence that can start at any point then the sequence is not changed at all by repeated cuts - only the starting point of the sequence changes. If anyone agrees I will write description of a proper overhand shuffle. Mike Spathaky (talk) 11:44, 30 November 2014 (UTC)

No-one agreed but no-one disagreed. I have now done this as I proposed. Mike Spathaky (talk) 15:22, 12 October 2017 (UTC)

No, this is not simply repeated cuts as the grabs are smaller than half the deck. And, they are not equal in size. What is described is a tops only strip. It is a not uncommon part of a shuffle in casinos. Of course, it is only one step as it doesn't shuffle nearly well enough. O3000 (talk) 18:21, 12 October 2017 (UTC)

Well the article as you have reverted it says it's repeated cuts ("essentially a series of cuts") and what it describes is repeated cuts. A cut doesn't have to be exactly (or even nearly) into halves. I stand by what I have said, that a cut does not shuffle the pack at all, and so multiple cuts don't either. I would like others' opinions on this before I restore my edit. Mike Spathaky (talk) 21:30, 13 October 2017 (UTC)

Of course it shuffles it if the cuts are of different sizes. Just not very well. (And one of the reasons home Poker games are easy to beat. Home players don't shuffle well.) Which is why a casino also riffles (among other steps). Try it. O3000 (talk) 21:40, 13 October 2017 (UTC)

"Of course" doesn't affect the logic of my explanation above ("Surely..."). Perhaps I am misunderstanding the description in the article, but as it stands it is a description of a series of cuts -- it says as much. A cut does not move a single card from its neighbours apart from the the top and bottom cards which come together and the two cards either side of the cut point which become the new top and bottom. At the next cut the latter two come back together. This is true wherever in the pack the cut point lies. Try it with a new pack (orderd by suits and numbers). Mike Spathaky (talk) 07:51, 14 October 2017 (UTC)

Unless you keep cutting in exactly the same spot, what you are saying is not true. Try it with a deck of cards. O3000 (talk) 12:12, 14 October 2017 (UTC)

I have indeed tried it with a pack of cards. After sorting the pack into suits -- spades, diamonds, clubs, hearts -- with each suit sorted into order, Ace to King, I then cut the pack by splitting it into two parts and placed the bottom part on top of the other. That is what the procedure you have reverted to describes. I repeated the cut many times, cutting in different places each time. At the end , the pack was in this order: 7-K diamonds, A-K clubs, A-K hearts, A-K spades, A-6 Diamonds. In order words the order of the cards treated as a circular series was unchanged. Each card had the same neighbours as at the start, except the top and bottom cards, 7 and 6 of diamonds. A further cut would have brought these two back together. I believe the issue between us lies in the description of the overhand shuffle in the article, which is what I tried to alter on 12 October, after suggesting the change on 30 November 2014. As a way out of this disagreement I propose to change the first paragraph of the Overhand shuffle section of the article and give the definition of an overhand shuffle given in Johan Jonasson's paper that is referenced in the section, namely: "The overhand shuffle... is the shuffling technique where you gradually transfer the deck from, say, your right hand to you left hand by sliding off small packets from the top of the deck." I hope you agree to this. Mike Spathaky (talk) 13:41, 14 October 2017 (UTC)

You aren’t following the instructions. You must make numerous grabs of different sizes. If you wish to replace with what you just proposed, go ahead as it says the same thing. O3000 (talk) 13:48, 14 October 2017 (UTC)

Thank you, O3000. I have now made the instruction clearer, based on those in the Jonasson reference, with a little amplification. As for not following the instructions, I see no mention of "numerous grabs" in the original article. What was lacking was the mention of the release of the cards in a number of small packets. You yourself said (1 Dec 2011) that an overhand shuffle "isn't really shuffling" and that was true with the description given. But overhand shuffling is used the world over, is a valid way of shuffling and now we have have an accurate description of it. Best Wishes O3000, Mike Spathaky (talk) 19:50, 14 October 2017 (UTC)

Yep, it’s used the world over and is a valid method of shuffling by definition. Which is why good card players can easily beat home games, particularly in Poker games where the cards are often set, like Draw Poker. It simply doesn’t shuffle adequately. More popular is just repeatedly jamming the cards together, which is actually better than overhand shuffling. O3000 (talk) 20:08, 14 October 2017 (UTC)

False shuffle

I added back a section yesterday that had been deleted with no reason given back in 2009, and now user:Objective3000 has reverted my edit just because it contained a link to a YouTube that is apparently an ad! Why could he not simply remove the link, if it's such a bad thing?? But there are probably people who would like to see the video.

Wikipedia is an encyclopedia, not an advertising medium. If you can find a reliable source, you are welcome to add it. Objective3000 (talk) 01:09, 28 December 2014 (UTC)