My Math Forum  

Go Back   My Math Forum > Science Forums > Art

Art Art and Architecture Forum - Math in our world, culture, buildings, natural wonders, nature, movies, music


Reply
 
LinkBack Thread Tools Display Modes
December 23rd, 2010, 05:50 AM   #1
Newbie
 
Joined: Dec 2010

Posts: 7
Thanks: 0

Lightly or heavily shuffling a deck of cards

Hi,
I am just wondering about ideas for doing this - I imagine none would be perfect. I have a convention for base36 deal codes. The algorithm is simple - 3 steps
1) sequence deck (ordered by protocol)
2) shuffle deck (using input deal code, method by protocol)
3) Deal cards (ordered by protocol)
So that anyone could recreate the same deal of a game of cards by sticking to the stated protocol.

What I want to have is a less shuffled deck with a smaller deal code, and a more shuffled deck with a bigger one. I want it so that a single-digit deal code shuffles the whole deck a tiny bit, and a 70-digit deal code produces one particular arrangement of the deck. For the latter, I want there to be a size of deal code where there is one code value per (possible) arrangement of the cards.

What I do not have is a fair way to turn a small (or short) deal code into a deck that is lightly shuffled (and a long deal code into one that is completely shuffled). Is there a math for that? (Probably not!) Any ideas are appreciated - I would like to have a standard for deal codes for shuffling decks.

TIA, and cheers -
Mark
Markgm is offline  
 
December 25th, 2010, 08:08 AM   #2
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Re: Lightly or heavily shuffling a deck of cards

Is there a reason you want to allow imperfect shuffles? I might be able to help if you can define precisely what you want.

For perfect shuffles, I recommend Knuth-Yates which is easy and fast.
CRGreathouse is offline  
December 27th, 2010, 03:59 PM   #3
Newbie
 
Joined: Dec 2010

Posts: 7
Thanks: 0

Re: Lightly or heavily shuffling a deck of cards

Hi,
I want the perfect shuffle to be what you get with a sufficient amount of randomization. I want less-than-perfect when a smaller (randomizing) number is used. I want the shuffling to come from the number. I want the degree of shuffling to correspond to the length of the number.
Thanks - Mark
Markgm is offline  
December 27th, 2010, 04:56 PM   #4
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Re: Lightly or heavily shuffling a deck of cards

You'll have to explain what is meant by the degree of shuffling, then. Perhaps you want to shuffle for a short amount of time, or perhaps using only a small amount of entropy?
CRGreathouse is offline  
December 28th, 2010, 06:05 AM   #5
Newbie
 
Joined: Dec 2010

Posts: 7
Thanks: 0

Re: Lightly or heavily shuffling a deck of cards

Quote:
Originally Posted by CRGreathouse
You'll have to explain what is meant by the degree of shuffling, then. Perhaps you want to shuffle for a short amount of time, or perhaps using only a small amount of entropy?
I'm not that picky. Using a standard shuffling algorithm, we'll generate random numbers one for each card, right? And each card will be given a new place in a new order. For a 52-card deck, that's 52 random numbers being used, or it could be thought of as a base-so-and-so 52-digit number. At that point, we say the deck is very well shuffled.

OK, so you figure this out. Is there a way to make the entire deck shuffled with half as much randomizing information? Can you think of any way at all to try to shuffle 52 cards with 26 numbers, or with 4? If you had nothing but a 4-digit number to shuffle a 52-card deck, what would you do to get it as shuffled as you could, and would it be just as random? Can we just use a 4-digit number and skip the 52 numbers above? Not likely. So the problem I am thinking of is how a few small random numbers can be evenly distributed in their randomness across 52 cards. In effect, the deck will not be as shuffled. But for the same shuffling numbers, it always has to produce the same exact result.

The next problem I run into, is that I tried a simple method which I would like to improve upon. Presently, I use whatever base 36 code digits are supplied to me, and if they are less than enough for a whole deck of cards, I duplicate and concatenate the existing code digits until the total length matches the number of cards, and then I use card swapping. I loop through indexes 1 to 52, and at each stop I swap the current with one of those digits. The problem is that with this method, a single digit code appears to shuffle the entire deck so well, that it just looks very well shuffled. I think for a better effect will be a way of using a small amount of random number information to make a deck "slightly shuffled".

Here's one thought. For 52 cards, let's say the max random code digits needed is 52 digits (base 52). This will make the cards very random. In the case of a 4-digit number (base 52), I could reduce the swap dynamic accordingly. Instead of generating a random number from 0 to 51 per card, I could generate a random number from 1 to 4 to swap to only within 4 spaces of where each card began. So if someone supplies GAWK as a code, that's got 4 digits in it. I want to distribute the GAWK information across 52 digits. So I can take 1/13th of each digit and apply that to each card, and the swap dynamic goes down (swap distance from starting deck index).

So if its a base 52 code, and I'll say the 4 digits in base 10: 5, 10, 20, 30 - those are the 4 digits for shuffling. Since 52/4 = 13, I can use 1/13th of the information in each digit and apply it to the shuffling of one card. The desired result is a deck that seems less shuffled to the player. The hurdle seems to be how to distribute a 4 digit code, or 3, or 7 or however many, into a small amount of shuffling per card for 52 cards (or 60, or 6. So what is 1/13th of 5-10-20-30? It means that less than half of 13 doesn't swap the card at all (0). A code of 5 is 5/13 = 0.385, less than half of one. A code of 10 is more than half, 10/13 = 0.77 or closer to one than one half. If I rounded up, then 7 to 20 would all be reduced to 1. 21 to 34 would be reduced to 2. The reduced numbers would be used to swap the cards. So, if it is a 1, then the card at index 1 would be swapped with the card at index 2. It seems to me that the deck might seem less shuffled.
Markgm is offline  
December 28th, 2010, 07:59 AM   #6
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Re: Lightly or heavily shuffling a deck of cards

Quote:
Originally Posted by Markgm
I'm not that picky. Using a standard shuffling algorithm, we'll generate random numbers one for each card, right? And each card will be given a new place in a new order. For a 52-card deck, that's 52 random numbers being used, or it could be thought of as a base-so-and-so 52-digit number. At that point, we say the deck is very well shuffled.

OK, so you figure this out. Is there a way to make the entire deck shuffled with half as much randomizing information? Can you think of any way at all to try to shuffle 52 cards with 26 numbers, or with 4? If you had nothing but a 4-digit number to shuffle a 52-card deck, what would you do to get it as shuffled as you could, and would it be just as random? Can we just use a 4-digit number and skip the 52 numbers above? Not likely.
You need a number picked uniformly at random from (a multiple of) 52! to perfectly shuffle a deck -- that is, you need lg 52! = 225.5... bits of entropy. If you have enough entropy but not an appropriate multiple then there are methods of getting what you need; for example, if you have a stream of random bits you can pull 226 off and see if the value is less than 52!. If so take it; if not, take another 226 and try again. (There are less wasteful methods.)

If you need to do it with too few bits then you're going to have to choose some fixed way of clumping outcomes together. What way is best will depend on your application.

For example, suppose you have a single whole number n in the range 1..52. One method you could use would be to choose the n-th card and cut the deck at that point, putting that card on top; a second would be to put the n-th card on top of the deck. Now consider three games, A, B, and C. In game A a player draws the top two cards and wins an amount based on the second card drawn (then the game ends). In game B the players take turns drawing cards until the 2 of clubs is drawn; the player drawing the next card wins an amount based on its value. (If the two of clubs is the last card, the 'next card' is the first card drawn.) In game C a player draws the top card and wins an amount based on the card drawn (then the game ends). For game A the first method is superior; for game B the second method is superior; for game C they are identical.

So there is no overall 'best' way to partially shuffle a deck; it depends on your application.


A very nice introduction to the subject (focusing on the 'usual' method of shuffling) is
http://projecteuclid.org/DPubS?service= ... 1177005705
CRGreathouse is offline  
Reply

  My Math Forum > Science Forums > Art

Tags
cards, deck, heavily, lightly, shuffling



Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
A deck of cards pedro malafaya Elementary Math 3 May 27th, 2013 07:56 AM
Probability with Deck of Cards flyingL123 Advanced Statistics 1 October 16th, 2011 10:05 PM
Deck of Cards Probability carolinegustin Probability and Statistics 3 March 27th, 2011 07:28 PM
Fair deck of 52 Cards wowbringer Algebra 1 March 17th, 2011 09:05 PM
Possibilities with a standard deck of cards? Krimi Algebra 3 January 19th, 2008 07:52 PM





Copyright © 2019 My Math Forum. All rights reserved.