0:00

Next, we're going to

Â look at an easy application of sorting to a related problem called shuffling.

Â So, suppose you have a deck of cards,

Â one of the things that you might want to try to do is to

Â simply rearrange those cards into random order, that's called shuffling.

Â Here's a way to get shuffling done using a sort,

Â it seems like the opposite.

Â The idea is just generate a random real number for every array entry,

Â and then sort using those random numbers as the keys.

Â That's an effective way to get things shuffled.

Â And it's possible to prove that that produces

Â a uniformly random permutation of the input if there's no duplicate values,

Â assuming that you have real numbers that are generated uniformly at random.

Â And that just means that it's well shuffled,

Â that every possible way of shuffling the deck appears with equal probability.

Â That's fine, but it requires a sort,

Â sort seems like a lot of work for this problem.

Â And the question is, can we do better?

Â Can we have a faster way to shuffle?

Â Do we really need to pay the cost of a full sort?

Â The answer to that question is, no.

Â There's actually a very easy way to rearrange

Â an array so that the result is a uniformly random permutation,

Â and only require linear time to get the job done.

Â Let's look at a demo.

Â The idea is to pass through the array from left to right with an index i,

Â as we've been doing.

Â But now, we start with the array in order,

Â and actually it doesn't matter how we start the array.

Â And every time we pick an integer between zero and i uniformly at random,

Â and swap a of i with that integer.

Â So let's look at the beginning,

Â we don't do anything, we just swap it with itself.

Â Now with i equals two,

Â i pointing to the second card,

Â we generate a random integer between zero and i.

Â In this case, it's the one to the left and we swap those.

Â Increment i, generate a random integer,

Â this time it's going to be the first one again, swap them.

Â Increment i, generate a random integer, swap them.

Â Increment i, generate a random integer, swap them.

Â And continue in that way, swap.

Â So for every i, we do exactly one swap.

Â Now, a card could be involved in more than one swap,

Â but that's not an issue.

Â The point is that the cards to the left of i are uniform randomly shuffled.

Â In this case, sign are the same,

Â there is no swap.

Â Increment i, generate a random r, swap them.

Â And at the end,

Â we have the deck shuffled.

Â That's a linear time shuffling algorithm making use of randomness.

Â It was proved actually a long

Â time ago even before computer implementations that if you do that,

Â you get a uniformly random permutation and it only takes linear time.

Â So, that's definitely a way to get a deck shuffled quite easily, easy to implement.

Â Now, it's key that the uniform random number be between zero and i minus one.

Â You'll often see programmers thinking

Â that they're implementing a shuffle and for every entry,

Â they just choose a random place in the array to exchange it with,

Â and that doesn't really work.

Â You could do the items between i and minus one,

Â the ones you haven't seen yet,

Â and that would also work.

Â But, doing the whole array doesn't give you a uniformly random result.

Â So, with that one copied at this code,

Â it's almost trivial and it's a method in our standard random class.

Â Now, if you're going to be using methods that depend on randomness in real applications,

Â you do have to be careful.

Â So, this isn't just an example about software security,

Â there's a lot of difficult and deep issues to worry about in software security,

Â and we're not going to worry about all of them.

Â But one thing that we can do is make sure that our algorithms work as advertised.

Â So, here's an example of an implementation for online poker.

Â Here's the code that you can find on the web for how to shuffle a deck of cards,

Â that's pretty similar to our code but it's actually got more than a few bugs.

Â So, our first one is,

Â the way that random works,

Â it actually never gets to 52,

Â which means that the last card can end up in the last place,

Â so it's definitely not shuffled because of that.

Â Maybe that one's minor but it also is picking a random card from the whole deck,

Â and as we just pointed out, that's not uniform,

Â it should be between one and i or between i plus one and 52.

Â 5:47

Another problem is in this implementation,

Â the random uses just a 32-bit seed,

Â if you do that, there's not enough possible shuffles.

Â The number of possible shuffles is much more and it's 52,

Â it's 52 factorial which is a lot bigger than two to the 32nd,

Â so it's not close to random or uniform.

Â The other thing is that the seed is just the number of

Â milliseconds since midnight and that cuts down the number of shuffles even more.

Â And in fact, it didn't take that much hacking for someone to realize

Â that after seeing five cards and figuring out what the server clock was doing,

Â you could get all the future cards in real time in a program,

Â and that's a pretty tough thing to have happen if you're implementing online poker.

Â You might want to make sure that if you're

Â advertising that you're doing a random shuffle,

Â then you go ahead and do so.

Â