This article is rated Start-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | ||||||||||||||||
|
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.
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)
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)
"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)
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
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.
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)
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?
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. howch e ng { chat} 23:19, 2 October 2006 (UTC)
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 removed [4] this sentence from the " False shuffles" section because it seemed meaningless:
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)
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)
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)
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)
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.
This article is rated Start-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | ||||||||||||||||
|
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.
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)
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)
"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)
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
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.
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)
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?
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. howch e ng { chat} 23:19, 2 October 2006 (UTC)
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 removed [4] this sentence from the " False shuffles" section because it seemed meaningless:
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)
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)
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)
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)
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.