Enumeration

Loading...

Del curso dictado por Rice University

Principles of Computing (Part 1)

431 calificaciones

Rice University

Principles of Computing (Part 1)

431 calificaciones

Curso 3 de 7 en SpecializationFundamentals of Computing

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.

De la lección

Combinatorics, generators, and debugging

This week, we will learn how to use combinatorics to solve problems.

The Importance of Combinatorics 4:32

Enumeration10:27

Permutations and Combinations13:35

Combinatorics and Password Breaking 15:32

Conoce a los instructores

Scott Rixner
Professor
Computer Science
Joe Warren
Professor
Computer Science
Luay Nakhleh
Associate 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.

© 2019 Coursera Inc. Todos los derechos reservados.

Descargar en la App Store

Consíguelo en Google Play