shuffle a deck of cards with one random number

the other day at work a guy was talking about a site that had a flawed method for shuffling a deck of cards. although it used a random number generator, the algorithm was flawed and it was possible in some cases to determine what cards your opponents had.

this got me thinking a bit about shuffling a deck of 52 cards. I was slightly surprised when I realized it is possible to shuffle a deck of 52 cards using only one number from a random number generator. it's not too difficult. it's something that could be a high school math problem. let's define the random number generator as a device that will produce a uniformly-distributed random number R in the range [0, 1).

I'll let it sit for a couple of days then post an answer

--

here's the solution.

there are 52! ways to arrange a deck of cards, about 10⁶⁸ or 80,658,175,170,943,900,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000. the important thing is that it is a finite set.

first enumerate the 52! permutations into a fixed ordered list L.

then using the random number R, let list_index = 1 + floor(R * 52!).

list_index will be an integer in the range [1, 52!]. the item in L at position list_index will be the sorted deck. qed.


so basically this is the same as arranging [0, 1) into 52! equal size partitions, and returning the piece that R lands in.


--

this solution also leads to another high school math/computer science problem. it would not be practical to create a list of 52! elements of size 52 bytes each.

here is the problem. describe a way to arrange L such at, given list_index, you can determine what the ordered 52 cards are for that list_index without having to do a lookup into L.

here is a sketch of a solution. arrange an original deck of cards in some specific fixed way such as { Ace of diamonds, King of diamonds, ... 3 of clubs, 2 of clubs }

now given any first card in the shuffled deck, there will be 51! ways to arrange the remaining cards. so if list_index is between [1, 51!] then the first card must be the Ace of diamonds, if between [51! + 1, 2 * 51!] then the first card is the King of diamonds, and so on

after determining the first card, remove that card from the original deck of cards, leaving the remaining 51 cards. now, use div and mod functions on list_index to similarly determine your "path" through list_index, removing the chosen card from your list at each stage. after 52 such iterations you will have the unique shuffled deck that corresponds to list_index.

Mathematics of sudoku

I've been doing the Metro News sudoku lately. I got thinking about the math in sudoku and the sudoku problem space. There's enough in there to make a high school level math problem or two.

Now the sudoku puzzles promise there's no math involved. And that's true. Although it's a 9x9 grid of numbers, the use of 1-9 is a convenience. Any set of 9 distinct symbols would work. You could use 9 Egyptian hieroglyphs, or the first 9 letters of the Greek alphabet and it would work the same and still be a sudoku.

I got thinking about the total problem space. How many ways are there to arrange 9 rows of the numbers 1-9. well that's not too hard to calculate. there are 9 factorial, 9! ways to arrange any row. so 362,880 ways a set of 9 symbols can be arranged.

The "first" or "bottom" row requires some consideration. I originally thought there were 9! ways to arrange the first row. I'm now pretty sure there is just one way to create the first row based on the definition

The first row consists of the 9 distinct symbols in any order. For convenience the symbols can be labeled S₁, S₂, S₃, ... S₉

Thus there is actually only one way to arrange the bottom row. For subsequent rows the actual symbols in the rows below matter so the usual combinatrics should apply.

Now in the total problem space each row is independent, so the total number of 9 cell rows above the first row is 9!⁸ which is 300,679,807,141,676,000,000,000,000,000,000,000,000,000,000 or about 10⁴⁴.

Now within this space only some of the arrangements will be valid sudoku. I was thinking how many sudoku are there, and how sparse within the total problem space are arrangements which are valid sudoku. I knew it would be sparse. Think about it this way. Working from the bottom row up, suppose you have 8 rows filled in. Then for the final top row there is just one way out of 362,880 to arrange the top numbers so that the result is a sudoku. This is because at each point along the top row the 8 numbers "below" will be filled, leaving only one possible number that can go into each of the 9 slots along the top, thus there is only 1 way to build the top row given 8 sudoku compliant rows below.

I was able to work out an upper bound on the number of sudoku there can be. I used the method of going left to right, bottom to top. Note again, there is only 1 way to fill in the bottom row. At each point I determined the optimistic maximum number of available numbers there could be, based on how many numbers were filled in to the left, below, or within the 3x3 subgrid. For example in the third row up, 7 numbers in, there are two numbers below filled, 6 numbers to the left filled, 0 within the 3x3 grid filled. so there are optimistically 3 numbers available that can go into this slot.

Now this is optimistic counting as it assumes that the smaller sets of numbers are proper subsets of the larger set used to determine the size of available numbers. Again this is an upper bound ballpark calculation. so filling it in the grid ended up looking like this

when you multiply the number from each row together it comes out to 42,118,945,229,525,500,000,000,000 or about 10²⁵.

dividing the numbers we can see how sparse the sudoku solutions are within the total space, only 1 in 7,138,825,663,917,590,000  arrangements of the 9x9 number grid is a sudoku. so 7 x 10¹⁸, or 1 in 7 billion billion. so it's pretty sparse.

Metro News Halifax sudoku

I was visiting someone at the hospital about a month ago. I ended up waiting in the family sitting room on the ward. There happened to be a Metro News Halifax there. I noticed there was a sudoku puzzle on the last page. With time to fill, I worked on the puzzle. It took a little while as I was rusty but I was able to finish it.

I hadn't done a sudoku in quite a while. At least 6 years or more. Years ago I got a sudoku book for Christmas and on my own I figured out some techniques for solving the puzzles.

Since that time at the hospital I've been grabbing the Metro News each day and doing the sudoku. Metro News is free yay. It's hard to imagine ever paying for a newspaper but that's for another post.

The Metro News sudoku are not difficult. On a scale of 1 to 3 difficulty the puzzles are usually at most 1 star. about once a week there will be a two star where I have to think a bit to finish it. I'm always able to finish the puzzle without getting stuck or having to guess.

To put it another way, more mathematically, at any point in the Metro News sudoku I can always uncover a number. I've got a bit more to say about some math around sudoku but I'll save that for a later post.

Now I was a little surprised talking to someone recently about the daily puzzle. I'm told that her coworker seldom is able to do the sudoku and ends up getting frustrated and throwing the Metro newspaper lol. So apparently many people are unable to finish the puzzle and can only complete the very easiest ones which they run 1-2 times a week.

So I'm offering a service here to people in Halifax. I can solve the Metro News sudoku 100% of the time. For a fee I'll meet with you at some convenient public place like a library. I can show you enough techniques so that you too will be able to solve the Metro sudoku every time.

I can see some use for this service. After all I would think there is some personal satisfaction in going from unable to solve, to being able to solve every time. That would seem to have some value. Maybe you are among a group of people, none of whom can solve it every time. if you suddenly leaped ahead and were able to 100% solve then you may then be seen as smarter than your former equals in this area. is that worth anything? meh, maybe. anyway my email is to the right so drop me a line.