This two-part course builds upon the programming skills that you learned in our Introduction to Interactive Programming in Python course. We will augment those skills with both important programming practices and critical mathematical problem solving skills. These skills underlie larger scale computational problem solving and programming. The main focus of the class will be programming weekly mini-projects in Python that build upon the mathematical and programming principles that are taught in the class. To keep the class fun and engaging, many of the projects will involve working with strategy-based games. In part 1 of this course, the programming aspect of the class will focus on coding standards and testing. The mathematical portion of the class will focus on probability, combinatorics, and counting with an eye towards practical applications of these concepts in Computer Science. Recommended Background - Students should be comfortable writing small (100+ line) programs in Python using constructs such as lists, dictionaries and classes and also have a high-school math background that includes algebra and pre-calculus.
Enumeration
Loading...
Del curso dictado por Rice University
Principles of Computing (Part 1)
338 calificaciones
De la lección
Combinatorics, generators, and debugging
This week, we will learn how to use combinatorics to solve problems.
Conoce a los instructores
Scott RixnerProfessor
Computer Science
Joe WarrenProfessor
Computer Science
Luay NakhlehAssociate Professor
Computer Science; Biochemistry and Cell Biology
[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]
Explora nuestro catálogo
Inscríbete de manera gratuita y obtén recomendaciones personalizadas, actualizaciones y ofertas.
Coursera brinda acceso universal a la mejor educación del mundo, al asociarse con las mejores universidades y organizaciones, para ofrecer cursos en línea.
© 2018 Coursera Inc. Todos los derechos reservados.
