• 1 day ago
Transcript
00:00Next question which we will talk about is find permutation
00:02What is permutation in math?
00:05Arrangement called permutation
00:06If I have n elements
00:09I can arrange these n elements
00:10I will say permutation 1
00:14I will say permutation 2
00:15I will say permutation 2
00:16I will say permutation 3
00:19I have a string
00:20which I want to tell all the arrangements
00:23I want to tell all the permutations
00:26For example, if I have here
00:28A, B, C
00:29The first permutation is A, B, C
00:31The second permutation is A, C, B
00:33I have exchanged these letters
00:37The third is B, A, C, B, C, A, B, C, B
00:41How many permutations are the total?
00:43The total number of permutations is equal to 6
00:46In fact, here I will tell you a little thing
00:50When I have n elements
00:52If our math is strong
00:5411, 12th
00:55Then I will tell you
00:56How many permutations are n factorial permutations
01:00If I have a string
01:02Which has n characters
01:04Or size n
01:05How many permutations are n factorial permutations?
01:09If I have an array
01:10Which is equal to length
01:12And the permutations in the elements
01:15That will also be n factorial
01:17So when there are n elements
01:18There are n factorial permutations
01:21We will see this later
01:22Like the subsets
01:23We will see permutations
01:24How many permutations
01:25From n factorial
01:26But there are so many
01:27Here you will see
01:28Size is 3
01:30And what is 3 factorial?
01:32That is equal to 3 into 2 into 1
01:34Is equal to 6
01:35So I have 6 permutations
01:37Now we will see an approach
01:39How many permutations
01:41How many permutations
01:41We actually calculate
01:42How many permutations
01:43What I am doing
01:44I will start with my string
01:46A, B, C
01:47And I will take a empty string
01:49I will take an empty string
01:51Now I am visualizing
01:53But this is not an array
01:54This is a string
01:55What is what I am doing
01:57In the string
01:57I am visualizing
01:59In fact
01:59I am taking a empty string
02:00It will not be wrong
02:02But this is my empty string
02:05I have taken a string
02:05Which I have taken in the same way
02:06In the beginning, my answer is this is my empty string.
02:10First of all, if my answer is three places in the beginning,
02:16because my first string is three places,
02:18then there will be one place where either A or B,
02:22or C,
02:23according to that, there will be A or B or C.
02:28There will be some choices in this way.
02:31For the first place, I will see the choices in the beginning.
02:33Let's say that in the first index,
02:36I have a choice for A,
02:37that I wrote the answer inside A,
02:41and what was the rest of my string?
02:43The rest of my string was B,
02:45meaning A, which I have transferred into the answer,
02:49and the rest of the characters, letters,
02:51were kept inside my normal string.
02:53Another choice was what?
02:55The other choice was that I have added B in the beginning.
03:00In this place, I added A.
03:02I added A and C.
03:03The other choice was that I have added B.
03:05If I removed B from here,
03:07then what will be the original string?
03:09A and C.
03:10The third choice was that I could take the answer here,
03:14that I added C.
03:15In the first place,
03:16the 0th place,
03:18and the rest of the string,
03:19A and B.
03:20So,
03:22I have three choices.
03:24So,
03:25I have three choices for this level.
03:25I have three choices for this 0th position.
03:30Now,
03:31I see the next level choices.
03:33Here,
03:33I have two choices.
03:36The first choice is that I take B.
03:37Here, what was the choice?
03:38A was the choice for B,
03:40or C.
03:41Here,
03:41one choice for B,
03:42and one choice for C.
03:43The second choice was B.
03:44The choice was B.
03:45The answer was B.
03:47The answer was A.
03:47And the final string was C.
03:50The other choice was C.
03:53The other choice was C.
03:53I have A, C.
03:55And the original string was B.
03:58I can say,
03:59here,
03:59I have a choice.
04:01But the choice here is a single choice.
04:03So,
04:05I have a final string in the last string.
04:07I have an A, B, C.
04:08And the first string was left.
04:11So,
04:11what happened?
04:12First,
04:13I took A,
04:13then I took B,
04:15then I took C,
04:16and I took these choices until I took.
04:18When I took the first string,
04:20I took the first string,
04:21and I took the first string.
04:24I took the first string.
04:26And the string of all the letters,
04:29they didn't transfer.
04:31As I did,
04:32I will do this.
04:34I will print this ABC.
04:35Because this ABC is one of my permutations.
04:38So,
04:38I will print it here.
04:39As my,
04:41one of my answers.
04:44This type of backtracking,
04:45this is enumeration backtracking.
04:47That means,
04:48I will tell all permutations.
04:50I mean,
04:50I will tell all solutions.
04:52Now,
04:53if I go back from here,
04:55after that,
04:56here,
04:58I have another choice in this level.
05:00There is no choice.
05:01So,
05:02I will go up another level.
05:02I will go up.
05:03Now,
05:03what do I do?
05:04I will go here.
05:05Here,
05:06I have one choice.
05:07Which is my B.
05:09When I got the choice.
05:11When I got the choice,
05:11what made my final string?
05:12What made my final string?
05:13My final string.
05:14My initial string.
05:16My initial string.
05:17there is no other choices.
05:18So,
05:18this is my permutations.
05:21A,
05:21B.
05:21Now,
05:22what do I do?
05:23I will go back here.
05:24I will go back here.
05:25I will go back here.
05:26There are all choices here.
05:27There are all choices here.
05:28There are all choices here.
05:30After coming here,
05:31A's choice is complete.
05:33Now,
05:34I will see B's choices.
05:35In B's choices,
05:37I have A's original.
05:39B is my final answer.
05:40I can take two choices here.
05:43One choice is A's.
05:44One choice is C's.
05:45As I got the choice of A's,
05:46my final string is B's.
05:48And I have A's answer.
05:50Now,
05:50I can take one other choice.
05:52Which is my A's choice.
05:54That is my final string.
05:57And at the point,
05:59you see,
06:00there will be a C's.
06:02With my final string,
06:03And P will be a C's.
06:04And then,
06:05My final string will be B.
06:06Then,
06:07I will print off my original string.
06:10So,
06:11I will print off my permutations as one of my permutations.
06:14What do I do here?
06:15I will come back from here.
06:16Go back here.
06:17the choices have gone here.
06:18For this,
06:19the choices have gone here.
06:20So,
06:20the choices have gone here.
06:22Just check that We have our C's choice.
06:23My string became bc and my original was just a. Now I can take another choice from here.
06:32What choice can I take from here? I can take a choice from here.
06:34Like I took a choice from here, my final string became bc.
06:37My original string remains here. I have left here.
06:43If I can't take any other choices here, I will print it as one of my permutations which is bc
06:49a.
06:49What will I do here? I will go back here. I will not go back here.
06:55I will put my a and b in the beginning seat.
07:01I will put all the choices here.
07:02Now I will put the c and then what will happen?
07:05The original string was a and the final string was c.
07:09I have two choices here.
07:12The tree is a little bigger.
07:14One choice is a and one choice is b.
07:16As I have a choice of a and my final string became c,
07:20and my original string was only b.
07:23Then I have one choice that has a, b.
07:26Then I will put it as a final string would become c, a b.
07:29My original string would become empty.
07:31Then with c & a b, there is no other choices.
07:33So I'll change c and b after that.
07:35If I will come back here, there will be no choices.
07:38If I will come back here, I will not.
07:39So I will again b that way.
07:40I will explore B. When I will explore B, I will choose B. It will become C, B.
07:46Original will remain A. Now the last choice will remain A.
07:53What will be here? String. String will become C, B, A. Original will be empty.
07:59I will print C, B, A. What do I have seen?
08:04I will explore all of the choices. I will explore all of the permutations.
08:11I have all permutations on this last level of recursion.
08:14I will print those permutations.
08:17I will count all of these permutations.
08:20What do I have done? I have a choice on every level.
08:23The first letter I have to place.
08:26I have to place the whole string.
08:28I will sit in the current position.
08:33How do I have a reason?
08:36If I have N places.
08:38I have many choices for the first.
08:41If I have 1 here, I have 1.
08:44How many choices for the second place?
08:45I have 1 here.
08:46How many choices for the third place?
08:49I have 2 choices.
08:51I have 1 here.
08:52How many choices for the fourth place?
08:54I have 3 choices.
08:55If I have N places in this way,
08:57I will have a single choice for the last place.
08:59If I calculate this,
09:02this turns out to be
09:03N into N minus 1 into N minus 2
09:06till 1.
09:08This is my N factorial.
09:10If I have N elements
09:12or I have N places,
09:14the total number of permutations
09:16always have N factorial.
09:18How many final permutations have here?
09:22This is equal to N factorial.
09:25How many times for the first permutation
09:26to reach a permutation?
09:27How many times for the end?
09:28Why?
09:29Because I had to analyze all the letters
09:30that I had to place in which place.
09:34I had to analyze the first place
09:35for the second place,
09:37for the third place.
09:37I had to analyze the size of the string.
09:39I had to analyze the same places
09:40that I had to analyze the letter here.
09:43That's why,
09:44N factorial
09:45has total permutations.
09:48N time
09:51is equal to N factorial.
09:56Now,
09:57we will write our code
09:57and see how we can print all permutations.
10:02Before we write all permutations,
10:04I will summarize it.
10:06What do I have to do?
10:08Every time
10:09I have N places
10:11I have N places
10:12this is my recursive tree.
10:14If I write my permutations functions
10:16then
10:17I will take a string
10:18with str
10:19and
10:20I will take another string
10:21with the answer.
10:23What do I have to do every time?
10:24I have to ask
10:25what I have to ask
10:25to one character
10:26to the place.
10:30So,
10:30I will run a loop
10:31that will go
10:32from i is equal to 0
10:33to str
10:35length
10:36Now,
10:37whatever character
10:38will come
10:38for me
10:39I will have two choices.
10:40So,
10:40in every level
10:41whatever the string
10:42will be
10:43there will be
10:43many choices
10:44for me
10:44to write them.
10:47To write them
10:47I will add
10:49string.character
10:52at
10:52i
10:53and
10:54my answer
10:55and
10:56my string
10:57I will remove
10:59that character
10:59at
11:00i
11:02so,
11:04I will remove
11:05the next level
11:05to access
11:06that character
11:06because
11:07that character
11:08I have already
11:08written
11:09here
11:10if I have
11:10a choice
11:11then
11:11I will take
11:12a choice
11:15because
11:15a choice
11:16already
11:16is
11:17and
11:17I will
11:18understand
11:18this
11:18by
11:18code
11:18help
11:18you
11:18see
11:19so much
11:19that
11:19you
11:19you