Quiz Hint: Why Every Even Permutation Is Solvable

Loading...

University of California San Diego 提供のコース

Mathematical Thinking in Computer Science

472件の評価

University of California San Diego

Mathematical Thinking in Computer Science

472件の評価

Specialization Introduction to Discrete Mathematics for Computer Science における 5 の 1 コース

Mathematical thinking is crucial in all areas of computer science: algorithms, bioinformatics, computer graphics, data science, machine learning, etc. In this course, we will learn the most important tools used in discrete mathematics: induction, recursion, logic, invariants, examples, optimality. We will use these tools to answer typical programming questions like: How can we be certain a solution exists? Am I sure my program computes the optimal answer? Do each of these objects meet the given requirements? In the course, we use a try-this-before-we-explain-everything approach: you will be solving many interactive (and mobile friendly) puzzles that were carefully designed to allow you to invent many of the important ideas and concepts yourself. Prerequisites: 1. We assume only basic math (e.g., we expect you to know what is a square or how to add fractions), common sense and curiosity. 2. Basic programming knowledge is necessary as some quizzes require programming in Python.

レッスンから

Solving a 15-Puzzle

In this module, we consider a well known 15-puzzle where one needs to restore order among 15 square pieces in a square box. It turns out that the behavior of this puzzle is determined by mathematics: it is solvable if and only if the corresponding permutation is even. We will learn the basic properties of even and odd permutations. The task is to write a program that determines whether a permutation is even or odd. There is also a more difficult bonus task: to write a program that actually computes a solution (sequence of moves) for a given position assuming that this position is solvable.

Project: The Task1:31

Quiz Hint: Why Every Even Permutation Is Solvable13:07

コースの提供者

Alexander S. Kulikov
Visiting Professor
Department of Computer Science and Engineering
Michael Levin
Lecturer
Computer Science
Vladimir Podolskii
Associate Professor
Computer Science Department

Let me try to give a short.

No, no, not short hint for the last problem.

How to show that every even

permutation is possible in the key.

We already know that every possible permutation is even.

But now we want to prove that the reverse statement is,

we can achieve everything in permutation and this is a mathematical account and

that it should be translated into programming side.

So, you should write the programming using this stand out situation

you have mathematical proof and you need to implement it.

Anyway, first, we start with some mathematics

which is not related to this game, buzzing which

is just the general things from group theory.

So, let's tell you what is the three-cycle.

So, two-cycle is transposition.

So two-cycle, we have A and B and

we want A to go to the place of B and B to go to the place of A.

This is transposition and then you can get what is three-cycle.

It's just we have A, B and C and A should go here.

B should go here and C should go here.

So, it's a three-cycle.

So, is it even or odd that's the first question?

And then it's easy to check, if it's even.

We know how to check this,

because we just need to present it as a sequence of transpositions.

So first, you want to put A here.

B here and C here.

So first, you make a transposition with A and B.

So after that, here you have A and here you have B.

So, A is in the right place.

A should be here, but B and C are in the wrong place.

B should be here and C here.

So, the second disposition is needed to exchange B and C.

So, it's an even permutation.

So, this is our first step and

second step is that every even permutation

can be obtained by three-cycles.

So we know that if we make several three-cycles,

then we have even permutation.

Because each of them is a sequence of even number of dispositions.

So in total, we have also even thing.

But now, we want to show the reverse statement that every even

permutation can be obtained in this way.

It's rather easy, we should recall how we did this for two-cycles.

For two-cycles, we just placed the right thing here, then the right thing here and

the right thing here and each can be done with a permutation.

And now if we want to place something in the right place,

then we cannot do a transposition.

We need to do a three-cycle.

So, we need some temporary location.

And so, we make this three cycle and this is what we need.

The problem with that at the end, we don't have temporary locations.

So if we here, everything, except the last thing is correct.

Then we are no more able to do this, but

then we have only two things.

And so, they can be either in the order we want or in the reverse order.

But if they are in the reverse order, then one more transposition is needed.

And this is impossible, because both our global permutation

which we want to get and our current permutation are even.

So, they cannot differ by one transposition.

So automatically, we get to last thing in the correct order before we

had the last thing in the correct place.

But now, we have two last things in the correct order.

So, every even permutation can be obtained by three cycles.

So, this is about general things and more computations.

Now, we return to our game and there are two observations about this game.

So, the first observation is that at least some three-cycles are very easy.

So we have a board and there is a special three-cycle, which is very easy to obtain.

So, imagine we have this red things.

We have here, I think it's 11.

Yeah, 11, 12 and this is 15.

So this three-cycle is easy to obtain, so we can get in this place.

We can get 11 here.

12 here and 15 here.

No and of course, you see how you do this.

You just need to make one step rotation in this direction and then 15 is going here.

No, first, you move 12, then you move 11, then you move 15, then you move this one.

Everything is okay.

So, one three-cycle is possible.

So that's a special three-cycle or if you repeat this twice,

you'll get three-cycle in the other direction.

It's okay in both cases.

So the question is how to obtain every arbitrary cycle,

if we know how to get this one special one and

then we need this next step is that every three

pieces can be placed into this red zone.

So, I made some symbolic things.

So if you take any three places, if the rest of course,

they're not so many possibilities.

But if they have any free places in the rest, you can and

you want to put them there in the red zone.

It's always possible.

For each of them, you know where you want to put it in the red zone and

there's possible without any restriction of other pieces.

So, other pieces can go wherever they want.

You just look at this time.

Actually, if you played ten minutes in this game, you know that it's easy.

The problems start when you are close to the end.

If you put only three pieces, that's just trivial.

But of course, we need some proof and

this proof unfortunately requires some case analysis.

So imagine we want to put this piece here, then how can we do it?

First, we can put it to the left side.

If we put the empty piece somewhere and then we make a rotation along the cycle,

so we remove this piece until it goes.

Now, it's already on the left side.

But if it were somewhere, we can just put it there,

then we can make a rotation along this line and put it here and

then after that we make rotation in this cycle and put it there.

So in this way, we can put it here.

So now, this thing is in the correct place and

then we need to put other two not touching this one.

So you should not make any changes here, but

you should make cycles like if you have [INAUDIBLE] which one.

If you have for example, this one and you want to put there and

you can move it first out of this, then move it here and then bring here.

And so, it's not difficult.

So every three pieces can be placed in the red zone,

but maybe now you are confused why we do all these.

Because first, we do something in the red zone and

there's enough of completely different story,

how to put three pieces in the red zone.

But now, there is the most important part of the argument is

something from grew fewer.

Let me show it like this, symbolically.

So, imagine we want to make some cycle.

First, we make some S sequence of three-cycles and put that,

six sequence not six-cycles, sorry, sequences moves in the game and

these three pieces are placed in the red zone.

So, these three pieces go somewhere.

I don't know.

Like this, like this, like this.

Then what we do?

We make the cycle in the red zone.

So in the red zone, we make a cycle.

It's not bad, so okay.

So, we make a cycle here.

So it goes here and goes here, and this goes here.

So this is the red cycle, which as we know is easy.

And now what we do, this is the most important step.

What we do, we do the reverse.

So we do the same movements, SNS, but in other directions.

So, that usually is noted by s minus 1.

So, we put things here.

And now these three things go back,

so this one goes here.

This one goes here.

This one goes here.

This one goes here.

So, what have we achieved in this way?

If you see that these things are moved in the red zone,

then cycles made there and then they are rolled back.

So we achieve the cycle we want and all other pieces here, they are moved somehow.

They are not untouched.

They are moved in unknown place.

And by then, he already don't move them.

So here on the second stage, they remain in the same place.

So in the third stage, they will go back exactly where they were initially.

So, we get the three-cycle here and all of the other pieces are on the same place.

So, we obtained everything.

So, we conclude that every three-cycle

is possible according to game rule.

And now we know that every permutation is a combination of three-cycles and

every even permutation is a combination of cycles, and every third cycle is possible.

So, these two things show that every even permutation is possible.

So, this is the proof.

The only thing there remains to do is to implement this in terms

of the program and it's a bit complicated.

Because here, it's easier when [INAUDIBLE] we make hand waving and say, look,

it's easy.

Blah, blah, blah.

But as programmers, we need to consider all the cases carefully and

not miss any case.

So you should be very careful on the second part and

then the other things are less complicated, and final remark.

There is another problem which shouldn't be mixed with this when you are asked to

provide the shortest, shortest path.

So you need to provide minimal sequence of moves,

which gives the desired permutation.

This is much more difficult problem.

It's required a lot of memory and some tricks to optimize them, so

it's not that easy and it's another story completely.

What we did is only the existence proof, so we prove that some part exist.

And therefore, there is always the shortest possible.

We have no tools to find the shortest pass up to now.

So sorry for if this was kind of, since it's most complicated thing.

I did not, I tried to explain it fast.

I didn't make slides, but

it's more challenging probably to follow this.

But I hope it's more or less clear.

コース一覧で検討

サインアップは無料です。今すぐサインアップして、パーソナライズされたお勧め、更新、サービスを利用しましょう。

コーセラは、世界トップクラスの教育を世界中に配信しています。最高峰の大学や組織とのパートナーシップに基づくオンラインコースが提供されています。

© 2019 Coursera (株)すべての権利予約します。

App Storeからダウンロード

Google Playで取得