[MUSIC] Welcome to class. This week's topic is combinatorics, in which we study how to take a set of items and kind of combine them to make more complicated objects. In this lecture I'm going to talk about enumeration, so let me show you an example of enumeration. We have four fingers. We can count through them, just the way Scott does. One, two, three four. It turns out there's more ways we can enumerate fingers. I'm going to count to fifteen using my fingers. Let's see if I can do it. One, two, three, four, five six, seven, eight, nine, 10, 11, 12, 13, 14, 15. I've just enumerated some fingers. Let's go on to lecture and find out more about how enumeration works. Alright. Let's talk about enumeration. So we're here looking here at the class page that I put together to discuss enumeration, and so I was just going to walk you though some of the basic concepts to start. So we're going to use a lot of the same terminology that we developed for probability we're going to think about having a set of outcomes. So you can think these are your, actually the outcomes for a trial. And in probability we really only look at a single trial and what could happen, the probabilities for that. Here we're going to consider a sequence of trials and those are going to have a sequence of outcomes. So for example, on a coin flip we might have heads or tails. So the sequence of outcomes might be heads, heads, tail. Or for rolling a six sided die the outcome might be one, two, three, four, five, six. So a sequence would be one, two, three, one. For the first part of analysis we're going to look at the case whenever we can have one outcome be repeated in the sequence. In other words we can go one, two, three and then actually choose the outcome one again. In the next lecture we're going to look at the case whenever you're not allowed to repeat outcomes. The class page walks through one kind of preliminary piece of counting to understand exactly how many outcomes we can have if we're allowed to repeat outcomes. The analysis is pretty straightforward. If we have the set of outcomes has size M, and we're looking at sequences of size N, then what happens is we have impossibilities for the first outcome, M probabilities for the second outcome, M impossibilities or the third outcome, all the way up to M impossibilities for the last outcome. So when you multiply all those together, you get M to the N. So, you get a lot of possible sequences. Now what I'm going to do in the next segment is I'm going to walk you through how to actually compute all these sequences. This is going to be helpful because you're going to use this code in this week's mini project on Yahtzee. Alright, let's talk about how to enumerate sequences of possible outcomes. So here I have some Python code that I've written that does that. I have a function gen-all-sequences. It takes two things as input, a set of outcomes, and a length of the sequence. Before we examine the code, let's just run some examples. So, I've got a function down here that does that for me. So we start off, let's let the set of outcomes be the digits zero to nine, and we're going to look at all the outcomes of length zero. So how many outcomes do we expect? Let's see, the formula said that it was M to the N, where M was the number of outcomes in our set, and N was the length of the sequence. So that would be ten to the zero, so we would expect one possible sequence of outcomes for things that are length zero. So, let's just run it and see what happens. And sure enough it generated, well it generated one sequence it was the empty tuple, the, the thing in our sequence that's everything of length zero. Okay lets change this to one and run it and see what comes out. And you can see here we have a set and a set consists of ten sequences. Zero. Then one. Then two. Then three. Essentially just all the possible outcomes in a tuple. Okay, let's make this two so how many do you think we're going to get? We're going to get 10 squared, so we should get 100. So let's run that. Sure enough, we get 100 sequences. So here we have the tuple (0,0), then the tuple (0,1) and if we scroll over here we can see we get things like (2,9), (3,0), (3,1) and so forth. So let's go back now and look at the code. How does gen all sequences work? Well, let's look at the code. So, here it is. It's actually not very long. Essentially, it's just an iterative process. It starts off by initializing the answer to be the set consisting of the empty tuple. Notice if the length is zero we just skip this loop and return back that exact answer. Lett's say the length was one, then we'll execute the body of this loop one time. The way this works is it makes a new set in which we're going to hold the answer for the current iteration and then we go through and grab every sequence in the current set. Okay, for the first case that would be the empty tuple and we just append every item inside the set of outcomes of that tuple. So we do empty tuple plus zero, empty tuple plus one, empty tuple plus two up to empty tuple plus nine. So when we finish that, we have a set consisting of the tuple of zero, the tuple of one, the tuple of two and so on. Okay, what happens if we want to make all sequences of length two? Okay, we start out at that point where answer consists of the ten tuples we just discussed. It pulls every single one of those tuples out. And appends zero to nine to it. So, when we're done, we come up with exactly 100 tuples. You can try this out with more examples down here to get a better feel for this. You should understand this code. You're not going to have to write this code, but you're going to use it this week in Yahtzee. Okay in the first part of this video we talked about enumerating sequences of outcomes. Now in some applications the actual order in that sequence is not particularly important. Let me kind of make that idea precise. Let's consider a dice game like Yahtzee. So in Yahtzee we roll five dies, and we might get something that looks like maybe five, four, three, two, one, two is one particular outcome for a Yahtzee die roll, or one, two, two, three, four. The critical thing to note here is that those really correspond to the same Yahtzee hands because the scoring rules in Yahtzee only worry about how many ones we've rolled. How many twos we've rolled, how many threes we rolled, how many fours we've rolled, so both of these hands have the same number of ones, twos, threes, and fours. So, when we're working in situations like this, we'd like to have kind of a way to avoid having two different tuples of outcomes correspond to the same hand, and so the way we can do that is we could take this particular sequence of outcomes, four, three, two, one, two, and we could sort it. The sort that would come out would be one, two, two, three, four. Likewise, one, two, two, three, four is already sorted. So the critical thing here to note is that equivalent Yahtzee hands, we think about a sequence of outcomes, actually had the same sorted representation. So, in this week's mini project we're going to represent Yahtzee hands by sorted tuples of die values that we will only have one particular unique representation for a Yahtzee hand. Now, I want to finish out the lecture by talking a little bit about how we can actually create these sorted sequences of outcomes. So let's go do that. Alright let's finish off lecture. So here we're looking at the code that we provided for gynsorted sequences. Now we could have built gynsorted sequences in a manner very similar to how we went through and built gen all sequences. But, we're going to be a little lazy here. If we got all the sequences we can just do a little processing in Python and just essentially kind of really weird thing except for the sort of sequences. Here's how we do it, we generate all the sequences. Now I should warn you, sometimes they can be a lot larger. Hopefully you'll know enough counting to figure out when they're going to be a lot larger. So we take all the sequences in that set. We sort them and then we turn them back into a tuple. And then we place those all in a set. Okay so notice that removes duplicate tuples, so all those things that got sorted out in the same tuple all those duplicates get removed. And we return the answer. Now, let me just show you the example so you can see how this kind of modifies the set of sequences. So up here I've configured it. We're going to run an example on which the outcomes, where the colors red, green and blue are looking for everything of length two. So if we run this, we're going to expect nine sequences of two outcomes, and we can kind of look at those. We have red red, red green, red blue, green red, green green, and so forth. We could also go through and do the same thing. We have the set of outcomes of red, green, blue, things of length two. We run those, and how many are we going to get? Well, we're going to get a smaller number because we're going to remove some of the duplicates when we sort. We get six outcomes. Kay, so we had nine here. We had six here, so what were the duplicates that got removed? Well, let's look at this a little more carefully here. So if you look at this, we had the tuple red green. At some point down here we had green red. Okay? We sorted green red, we got green red, we sorted red green, we got green red. So kind of those tuples compress to a single tuple. What about blue red? Let's see, we had blue red here. Okay, and then we had down at the end we had, where is red blue? There's red blue. So what happened is, there were three pairs of tuples when we sorted them, they kind of went down to one tuple so we went from nine tuples to six tuples. For Yahtzee, the amount of compression is actually more substantial. Okay, so those are kind of two variants of the kind of enumeration you might do in this class and other classes, involving common combinatorics. Okay, see you next lecture. [SOUND]
