Next, let's take a look at some examples where we use arrays to perform some interesting computations. First one we'll do is a simple one. Let's create a deck of cards and then we'll be able to use that as a basis for some interesting computations involving decks of cards. So, to do this, we're going to define three arrays. The first one is all the possible ranks that a card could be. They could be the numbers 2-10, and then jack, queen, king, and ace. So, there's 13 different ranks and we use the literal representation to create that array and then down at the bottom is what the array of ranks looks like. Then we build another one of length four that gives the suits, clubs, diamonds, hearts, and spades. Then with those too, what we're going to do is build our deck which is an array of size 52 and we'll start with an empty array and then for deck and then we'll write the code to fill it in with the 52 cards. To do that, we're going to use nested for loops. So, that's what the code looks like and it's got this, it's a nested for for all these possible suits for all the possible ranks. Fill in a deck with a card of rank I and suit J. So, the right- hand side is okay. In the left-hand side, you have to think about a little bit to see what it's doing and we'll take a look at that in a second. I just mentioned we use four and 13 because in lecture, it's pretty clear that for you to understand that there's four suits and 13 ranks. In actual code would rank.length and suit.length instead of those specific values and even deck.length instead of 52. Okay, so, we start with I and J at zero and you can see those up above the suit and rank and then the first thing is I is zero and J is zero, so I plus 13 J is zero, so deck of zero gets the first rank which is two and the first suit which is clubs, so two of clubs. Next thing we do is increment I, J is still zero, so, it's going to be deck one and that's going to get the three of clubs, the rank one and still suit zero. So, now, you can see J stays zero, I increments, and we go through and fill in the first 13 positions of the array with all the clubs. J is zero, so we're just getting deck of I. So, now, we do the King and the Ace. Now, when I has reached 13, then we're going to increment J and start at I equals zero again and now, we have J equals one, so and I is zero so we're talking about deck 13, and deck 13 gets a rank of zero which is the two and suit of one which is diamonds. So now, we'll go through the whole thing with diamonds. The value of J stays fixed and the value of I increments so essentially, we copy the diamonds into deck. So, now, you can see how this loop works. This is the entire program and if we run that, we get the result that we want. I just have to point out, I'm sure some of you are wondering in Unicode, you get to use symbols like clubs, diamonds, hearts, and spades. You don't really get color though, that's artistic license for the lecture again just to make it a little easier to read our output. So, that's a complete program that creates a deck of cards and now, we can look at some interesting computations that we can perform with decks of cards. Before we do that, however, just to make sure that everybody is thinking properly about nested loops and index computations on arrays, think about what happens if we switch the order of the four loops. So, instead of J equals 0-4, I equals 0-13, we do I equals 0-3, J equals 0-4. The answer is that the array is going to get filled in in a different order, but the output is going to be all the same. So, I stays at zero and we increment J, what does that mean? That means the next thing is we do I equals zero and J equals one, so we do deck 13 next. It's still the same card that went in deck 13 before but what we do is we put in all the twos and then J gets back to zero, I goes up to one and now we do put in all the threes. So, at this point, we're at J equals two and I equals one, so, 13 times 2 is 26, add one is 27 so we'd fill in 27. We do all the threes and so forth. So, the answer to the question is the computation has the same result but the stuff goes in in different order and eventually, we get to do the aces and then the last one that gets put in actually in both cases is ace of spades gets put in at the end. So, there's that and I just point this out, if you have an old printing of the textbook, there's an error related to this. Okay, what if we wanted the cards in the deck in a different order? Now we have them by suit, what if we wanted it by rank? So, how would you write code to put all the twos, then all the threes and then all the fours and like that? That's worth thinking about and here's the solution. We do I equal 0-13, J equals 0-4. Again, we could switch the order and get in different order but now, we say deck of four I plus J equals rank of I plus suit J, let's see how that works. So, again, we start out with the two of clubs and now when we increment J first, four I plus J gives us the two of diamonds. I stays at zero and we increment J. So, we go through all the twos, then increment I and now, we do all the threes. Looks very much the same but it's different computation. It puts the cards in the array by rank not by suit. Either one is fine as we'll see because the very next thing we're going to do is shuffle the cards. Okay, so, let's look at picking a random card. That's a comic relief break. Okay, so, let's say what we want to do is print a random sequence of N cards and our method is going to be, we're going to take the value N from the command line and we perform the following steps N times. We're going to calculate a random index R between 0 and 51 and then print the card at that position. So, we'll just use that same program where we printed the deck but instead of printing the deck, what we're going to do is instead of just printing it out, we're going to use math.random and we looked at this code before the end of the lecture when we were talking about data types. This code here gives each value between 0 and 51 equally likely, and so then we just print it out. This method actually works. It doesn't have to be cards, it can be any array of anything. We can randomly choose an element from the array using this method. So, that's the code. It's the same code as before except it's got that random choice ahead of time. So, if you want to draw 10 cards, you get a different result every time. Now, remember, this sample is width replacement, that is you can get the same card twice in this sampling. So, another interesting problem to look at is what if you wanted it without replacement? That's a little more like what you're thinking about probably, which is how do you simulate shuffling and dealing from a deck of cards? So, what we want to do is I want to have a shuffled deck and I want to deal out a hand of N cards and so, our algorithm is going to be shuffle the deck and then deal. We do more complicated things in a game where we want to do multiple hands and so forth but let's start with the simple one, shuffle and then deal. So, here's an effective algorithm for shuffling. We're going to consider each card index from 0-51, we're going to calculate a random index between I and 51, and we're going to exchange deck I with that one. So, we're going to move through the deck and for every card, we're going to find a random position further on to exchange that one with and then move on. Then we'll print the first N cards in the deck and that's a way to get N random cards without replacement. That's the whole code for it, for I from 0-52, so that's every card in the deck. We compute an integer R that's between I and 51, so that's slightly modifying that code that we did. This one gives a random integer in the range from I plus 1-51 and you can check that and then we exchange the card at position R with the one at position I and then we just print out N of them. Now, let's do a trace of that computation to be sure that we appreciate how it works We'll just do it for 10 cards and they're all clubs. So, we start at I equals zero and we generate a random position R, in this case, it comes out to be seven and then exchange the two of clubs with the card at that position which was the nine of clubs. Then for I equals one, it's R equals three, we exchange the three with the five and I equals two, it turns out to be nine so we changed the four with the jack and so forth, each time exchanging the card at position I with the card that randomly generated position. At the end, there's really nothing to do. So, it looks randomly ordered at the end. This is the order along the diagonal here and it's worth thinking about why this method works. It's not obvious. There's other methods that you might think about and people implement other methods that don't really work and this is not a complete proof but at least I think I can convince you that it works all right. So, the first thing is it only uses exchanges within the deck so you know that the deck after the shuffle has the same cards as before. That's important. You could write code that winds up having 13 clubs in it and you might not know if you didn't do a trace. So, the other thing is that the way we wrote the code, the card at position i has n minus i equally likely values. So, that means if we go through the entire deck, we start with the first one has n equally likely values, and the next one n minus one and so forth, multiply those out you get n factorial equally likely values for the whole deck. It doesn't matter what the initial order is, and there's n factorial different ways to arrange n cards. So, that's should convince you that this method is effective. Again, this could be any type of data, any array you run the same method and you're going to get it shuffled. Then what we did in our one application was just so we shuffle and then deal. So, if you want a poker hand, you do five, if you want a bridge hand, you do 13. You're not going to get duplicates there because we made sure that what we did was shuffle the deck and then pick out the cards that we want. If you want to deal out four bridge hands, you could adjust this code appropriately or however many poker hands. So, this is the basis for writing programs to process deck of cards. If you wanted to calculate the probability that you get a full house you could use a simulation like this to get started, and there's lots of other things that you might want to do. We're going to look at a more basic mathematical problem called the coupon collector problem. This is a classical problem as we'll see and it's very simple to explain. So, you've got coupons that you might get from some source, maybe baseball cards or magic cards or we'll do it in terms of playing cards, and you get them randomly each type of coupon equally likely, and what you want to do is collect all different types. You want to have one of each of the different types, and the question is how many coupons do you need to get the full collection. For example, let's say we're looking for, we have a random sequence of cards coming through, and we want to collect all possible ranks. So, here's our sequence. So, nine of clubs is the first thing. So, we collect, we know we have a nine and then we get a five and then we get an eight, and a 10, and after a while we get something that we've already seen. Now, we've already had a 10 of diamonds now we get to 10 of hearts. So, that doesn't add to our collection. Queen does, three does, nine doesn't add to our collection, we already had one of those. Five doesn't, and we get another nine, that doesn't help. After a while, we start to get cards that we've already had much more frequently. We already had an eight, finally we get a six. So that's good. So now we're looking for a four, a jack or a king. No, there's a king that's good. So now we're just looking for a four or a jack. We've got another 10. This is sampling without replacement, with replacement by the way. We're just taking random cards, so we can get two tens of hearts. We get another ace. There's our four so now we're waiting till we get a jack and luckily we got one right away. So, in this case in order to get one of each of the 13 different values, we had to look at 22 cards. So, then the question is if we get random coupons, get a random sequence of cards, how long we're going to have to wait to get a full collection. So, we can use an array to study this problem. So, what we're going to do is, well, we'll just number our coupons from zero to M minus one, and then we're going to generate random int values between zero and M minus one, and what we want to do is count the number used to generate each value at least once. The key to the implementation is going to be a Boolean array, that's an array of variables of type Boolean. They're either true or false, and Java initializes them all to false, and whenever we get a value r and the coupon, then we're going to check the rth value in the array. If it's true that means we already saw it so we're going to ignore it. If it's false that means we have a new distinct value, and so then we're going to set it to true. Then we're going to count the cards as we go. So, this is the code to implement the coupon collector problem. We'll take our number of coupons M from the command line, and we'll start having collected zero cards, and we'll also keep track of the number of different cards, distinct cards that we've seen, but we're not keeping track of anything else. For every value we're just keeping track of have we seen it before or not. We started out saying no we haven't seen anything, they're all false. As long as the number of values that we have is less than M, we're going to keep going, we're going to keep going until we get all M different values. So, when we keep going we're going to generate a new card, so that's a random value between zero and M minus one. We're going to count it, and that's the number of cards that we've generated. Then we're going to check to see if we've seen it before. So, not found means that we haven't seen it before. So, that means we have a new different values so we're going to count that and keep track of it, and then we're going to set the entry in the found array according to that to be true so that next time we'll skip it. If we've already seen the value we just don't do anything and stay in the while loop. Then at the end we just print out the total number of cards that we've seen. That's a coupon collector simulation. Let's take a look. If you run it, say for 13, you can see that you get a bunch of different values. So, we're going to have to run it a lot of times and take an average to try to answer the question of what's the average number of cards you expect to do. But before we do that, let's look at a trace. So, this is for M equals six. So, we start out with, we haven't seen anything, everything is zero. First card comes in, that's a two. We look at found of two that's false, so we make it true, and that's the card and it's a new distinct value. We get a zero. Again, when increment both of them a four, we set the corresponding entry to true and that's a new value. We get another zero, and so we check the entry at zero, and that's true. So, not found is false so we skip it, and just increment the number of cards. One, we increment them both. Two, we've seen two before so we just increment cards. Five is new, we increment of both and now we're looking for three, and finally we get a three and we've seen ten cards, and we have six distinct values, that's M equals six and so then we break out of the wild loop. So, that's the code for the coupon collector problem. Now, this is a classical problem, dates back to the 18th, 19th century. As I mentioned before, mathematicians, when probability was coming into existence were very interested in games of chance. So, it's actually been known for a couple of centuries that the number of cards that you need to generate to get all M is about M natural log N plus 0.57721 M, about that. So, we can calculate what this expected weight is for various situations, like the one we did with suits you expect to do about eight. If you want to do the ranks, you're going to expect to do about 41 according to this formula. If you want to collect all of the 1,200 baseball cards that were published in a certain year you're going to have to get 9,000 of them before you get them all, and if you want to do all 12,534 magic cards that were existence at a certain point, you're going to have to get about 125,000 of them. Now, we can test these by running our coupon program, and we actually do pretty well. The computer simulation can really help us validate mathematical analysis, and it can also validate software behavior a little bit. But we have to do more than one run. So, for example, this is actually a famous test for whether a sequence of numbers is got the same properties as a random sequence of numbers. It better satisfy this formula to get all possible values. So, once we have the simulation debugged and working, then we can run at a lot of times just like we did for gambler's ruin. Remember, for gambler's ruin, we got it working once but then we put in a loop and ran it for a long number of trials and then computed the average over the trials. So we can do that same thing for coupon collector. Put that code inside a loop where we run it for a large number of trials, and then print out the average cards over trials. Now, that's a huge computation with the loops who were performing lots and lots of random numbers and coupon collection experiments, but we can take a look at this question, what is the expected number coupons needed to acquire a full collection? Again, from Laplace, we have these ideas from mathematical analysis, but running that program on the previous slide we can run it I guess a million times, and we get values that are extremely close to what Laplace's formula predicts. This is an interesting computation made possible by arrays, and it helps us validate a scientific hypothesis. Is this analysis correct? Looks pretty good, and as far as this test goes looks like math. random simulates randomness. Actually I met there's other tests that math.random doesn't do quite so well on, but this one we have the ability to at least validate this hypothesis. Interesting computation made possible by arrays.
