Archive for January, 2010

Shuffles & randoms

Wednesday, January 20th, 2010

I was asked a question about shuffling yesterday which got me thinking. How do you write an algorithm to truly shuffle a deck of cards without any bias?

There are a couple of well-known algorithms to do this, both popularized by Donald Knuth. At a very abstract high-level they are:

  1. generate a random number for each card in the deck then sort the cards by number. If two cards are assigned the same number then try again;
  2. go through the deck, taking each card in turn and swap it with some random position in the deck.

Clearly #1 could take a longer time to run since you’ve got to sort cards and deal with clashes. Although with only 52 cards in a deck you are probably not too worried about algorithmic complexity.

#2 looks good on the surface but there are a few gotchas to be aware of. With a deeper mathematical analysis you can see why. The first is that if you swap cards with any position in the pack you will not get an even distribution with shuffles. This is because you’ve written an algorithm that has n^n execution paths and there are only n! permutations. Using the wikipedia example consider just 3 cards: your algorithm can produce 3^3 = 27 outcomes but there are only 6 permutations for shuffling. You cannot fit 27 into 6 so there must be some outcomes from your algorithm that are more likely (see pigeonhole principal).

The solution is to swap with the portion of the pack that has not yet been swapped with.

Wikipedia has a clear article on shuffling and implementations with further details on the impact of using the mod operator with random numbers (again, the space of randoms being generated then having mod applied is not an even distribution). A final note is that you need to seed your random number generator or it’ll be pseudo-random. Or better yet use random.org

Bookmark and Share
[del.icio.us] [Digg] [Google] [LinkedIn] [StumbleUpon] [Windows Live] [Yahoo!] [Email] More »
Powered by Bookmarkify™

Tags:, ,
Posted in algorithms | No Comments »

Location based services for mobiles

Friday, January 8th, 2010

Location based services have been around for a number of years in the research community. They were always fun to build and excellent research vehicles but needed something to change before hitting the streets. Well, now we’re beginning to carry GPS enabled devices these services have hit the mainstream. I regularly use Yelp and Around Me on the iPhone to find local restaurants, gas stations, and coffee shops. The integration with the maps application is a fantastic coupling. Now Google have released their search services with the “Near me now” service (iPhone and Andriod in US only).

Location data for these applications is usually derived from GPS readings but it is not limited to that. You can use wifi spotting, video capture, parse user calendars or discover location by inference (I am near Alice and Alice knows where she is so I can find where I am). But in practice are these other inputs really required? Or are they all part of a larger model of the real world?

Location based services are a manifestation of pervasive computing in the real world. Next will come more complex context aware services with social aspects and recommendations. I’ve oft heard the question “who will pay for the infrastructure for pervasive computing?”. I think the answer is still “we will” but now you can add “and already are”.

Bookmark and Share
[del.icio.us] [Digg] [Google] [LinkedIn] [StumbleUpon] [Windows Live] [Yahoo!] [Email] More »
Powered by Bookmarkify™

Tags:, , ,
Posted in google, mobile phones, pervasive computing | No Comments »