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.

To Heaven and Back by Mary Neal

Another book read. To Heaven and Back by Mary Neal. This was an account of a medical doctor who drowns while kayaking in Peru. She is dead for several minutes before being revived. While dead she is met by spirits and guided to Heaven. In the book she tells her account of being dead and her time in Heaven.

Interestingly, the Heaven part is only a short passage in the middle of the book. The author writes about her life up to the accident, then the accident when she dies, then another major section of her recovery from the accident and her life in the years after.

It was a very good book. The author writes in an accessible style with short chapters and nice spacing between lines and paragraphs. I was impressed by how spiritual the author is even before her experience with Jesus and angels. I would recommend this book even for those who are skeptical or unsure if God is real.

Neal makes an interesting observation that angels can come in different forms, such as through animals. In her case it was an owl. others report crows carrying messages. a mysterious out of place person who comes seemingly unexpectedly out of nowhere at an opportune time may actually be an angel.

It was a good read for me. I grew up going to church and felt I was religious. sometime around after high school it fell away with me and I've been pretty much disconnected ever since. I still go to church a few times a year but I've never gotten back to the connection I had when I was young. This book was good it got me thinking about spiritual things some.

2015 is come to pass

taking a day off work today. using some of the banked overtime from the death march project that ended 2014. nice relaxing day here.

so 2015 is well begun. for new years I was feeling pretty crummy and sick for over a week before I went back to work. bummer being sick during my time off. oh well darn. so I didn't have much energy. I went to a movie for new years, something I've never done before. I went to see the Hobbit. It was pretty good. I'm not really into the lord of the rings stuff but it was fine. stayed up long enough for the countdown and to bed shortly after.

and 2014 is now in the books. 2015, like 2014 and every previous year, is come to pass. to use the Bible term. it's an important and powerful concept. whatever 2015 brings will end. good or bad, expected or unexpected, good fortune or bad luck. I was told on very good authority to expect change in 2015. so whatever happens will happen. change can be bad but can also be very good. and then there will be a reset and another at least calendar fresh start.

a lot happened in 2014. in the year up to Christmas time, I owned four cars. I had two cars destroyed in accidents by reckless and irresponsible drivers in June and July 2014. driving is still pretty skittish but this current 2010 Corolla I got in July has fortunately been running well. I'm hoping it will get me through 2015 safely and with minimal drama. I'm pleased to be a Corolla driver, that car suits me and my personality.

I also lost my job in 2014. In June my time at RIM was terminated after 6 years there. It's never a true surprise to anyone to get laid off from RIM, still it was an unplanned and abrupt and disruptive life change. Luckily I found work a little over a month later with CGI so it was a relief to get back to work and resume the flow of paycheques. So who would have known in January I'd be working at the site of the former Zellers Bayers Road as December wound down. and so it goes, so much happens during a year and ends up being important that you may have been unaware of or only very vaguely even aware of.

Finally my mother died in December. She had been sick for a long time so it wasn't a shocking or sudden thing. Still back in new years January 2014 I would not have thought at the time this would be Mom's final year.

so all in all I'm glad 2014 ended and now 2015 is begun. and better or worse or in between 2015 will also inescapably come to an end. who knows what this year will bring? what will end up being central this time next year that I'm not even aware of at this time. only time will tell. I can just try to do the right things based on my knowledge and experience, try to be a good person, and hope that positive results will flow from consistently making good life decisions and having a positive attitude.

Mutated by Joe McKinney

I've got through a few books of late. I finished another Joe McKinney Deadworld book. Mutated is pretty good. This picks up the story eight years after Apocalypse of the Dead. He picks up with the Apocalypse characters Nate and Ben. Nate is somehow immune to the zombie infection. As long as they don't tear him to pieces he can take some bites and scratches.

There are some new characters introduced Sylvia, Avery and Niki. At this point 8 years on some survivor settlements have been established. There's also some trade among the settlements along the Mississippi river. Which makes sense since the McKinney zombies drown in deep enough water so that would more likely emerge in the post apocalypse.

A new sinister force has emerged among the zombies. A terrifying Red Man who gets both the zombies and some human black shirt soldiers to work for him. He's overrun 4 of the 5 major survivor compounds. In the story Niki and Nate want to reach a mysterious Dr. Fisher who may be able to turn the tide on the zombies. The Red Man wants to find and eliminate the doctor and wants to use Niki to get to him.

It's a pretty good book. Not as great as Apocalypse of the Dead, but it was satisfying to see Nate again. The new characters are pretty solid. McKinney still captures the terror of the undead well. It's a fast paced read I got through most of it when home sick for a weekend over new years.

I think I have two more Deadworld books to read to complete this series. I'll look for them at the library.