Hello all and welcome back.
So in this video let's continue our discussion and solve the question.
Return permutations of a string.
Now in the last video we already saw how we can print the same.
But now instead of printing, we have to return them as a list.
So let's get started.
Now we have already seen what permutations are, and for ABC, I know that my permutations are going
to be six, which are ABC, acb.
BC a b a c and c a b c b a right.
While we are printing, of course we have to maintain an answer, maintain things which we have taken
and send that across recursion.
But when we have to return them as a list, of course the approach is going to be different.
So let's now went back to our basics and understand how we used to solve the problem.
So see everyone.
If we have ABC what I'm going to do is what I'm going to do is I'm going to take A and ask B, ask my
recursion to work for BC.
Okay, so let us write according to the framework The very first step used to be the base case.
Now base case.
I know till now we are having lots of practice in this.
If s is equals to an empty string then we can just return inside a list.
This empty string.
Right.
Second is I will just ask my recursion that hey, give me all the answers.
Give me all the answers of whatever list I am giving you.
Right?
Whatever list I am giving you.
So while making the recursive call.
I will just ask my recursion to give me small answer or small permutation, small string permutation,
where I will just ask to return for s from one to n, right?
So I'm going to pass BK and say that hey A, I am going to take care of you.
Just give me all the permutations of PC.
Now I have to of course assume you don't have to question the step?
Repeated it lots of times.
And your small answer?
You have to see that it is going to be BC and CA.
Okay, sorry CB.
Now your volume is using this.
Can you now actually create your permutations?
I think yes you can.
Okay.
How you can do that?
If you actually understood the last question and last video, please make sure that you see that properly.
This problem is not just broken down into this.
So you have a with you and you have BC, you have a with you and you have CB.
So all you have to do, you have these three positions and you have to make sure that for each and every
of the small answer, you are able to add the character on which you are working to these positions,
right?
So I hope that is clear everyone.
So one of the permutation is going to be a BC, then it is going to be b B.
A.
C.
And there is going to be b.
C.
S one, two and three.
So we are adding on 123.
Similarly here a c b c a b and c b a.
So 123123.
One thing to note here.
Of course you can always just send the first half which is a B and then work on it.
Then your answer is going to be the way we got it the last time.
But if you would have done enough practice all the questions, then this approach should also be clear
to you.
So what I'm trying to say is that you can also do something like this wherein for a, B, c you are
saying that, hey, I am sending you a, B and I will work on C.
So the approach is going to be exactly the same.
Okay, so let us now solve this everyone.
The code is going to be a lot easier if you understood this particular thing.
So def return.
Permutations.
Okay.
One second.
Um.
I think I will have to name this file again.
One minute.
It's not a Python file.
I forgot to add the.
So dot p y will make it Python.
Nice.
So def permutations I will be getting a string s one.
And I will have to just make sure that I return all the strings.
Right.
So answer can mean this.
Return permutations.
And let's say I am passing ABC.
So again this will work for each and every of the string just ABC.
I am using so because we have been doing everything using the same thing right.
Substring sub sequences now permutations.
Great.
So now let us do this everyone.
The very first is a base case.
I know that if my s one is empty, then I can return this only because this is going to be the permutation.
So this is the base case okay.
Now next is recursive call.
So my small answer or let me take permutations of small string.
It is going to be return permutations.
And I just want to pass this thing at this step.
At this step, you do not have to question, you do not have to question, but you actually have got
something like this.
So for our case A, B, c you would have gotten b c and c b okay.
Now next you just have to assume that okay this is the answer which you have.
And write the code here.
Right.
We have to write the code at your end.
Now once this is the answer what exactly I have to do.
Let me let me take an answer okay.
Or let me take all permutations.
So see for each permutation in this particular answer.
So I am taking the each and every permutation.
So first I am going to take BC.
Then what I have to do is very similar to something which we did in the last class, right in the sorry
in the last video where I have this particular string with me, I have to find these three locations
and add my current character.
So let me just have this current character as well.
I'm making these names a lot more readable so that while you are revising, you are able to quickly
grasp them.
Okay, so not using any, uh, single character name or something, I am using these names so that you
help you are able to grasp them quickly.
So we recommend that whenever you are writing any code or solving any question, please try to use,
uh, as intuitive name as possible so that you are able to quickly revise them.
What?
All I have to do, everyone, is that for position in range zero to length of okay, length of each
permutation plus one.
So it is very similar code.
Very very similar code.
All I have to now do is in all my permutations I have to just append.
I have to just append.
My each poem permutation like this position each permutation so zero till I plus my current cat plus
each permutation I till n.
Right and sorry not I.
My bad.
We have to use position.
So force of habit of using I in the loop.
And I think if you done this properly and you return your permutation all permutation, your code is
done.
And I try to run it or let me print the answer here.
One second.
Yeah.
So you are able to see all the output permutations right now how this code would have done.
Let me just help you do a quick, uh, workaround for this as well, how this code would have run.
So yeah.
We would have first call for ABC.
ABC would have called for BC.
BC would have called for C, and C would have called for empty string.
Now again, this is not something which you have to do while writing your code.
If you end up doing that, hopefully in your Google interview or Disney interview, you will keep on
solving this question.
That is not something which I want.
I want you to make sure that you are all caught up on your basics and solve it quickly.
This is going to return you an.
Empty list.
Okay, when this returns an empty list, you will get in permutation of small string and empty list.
Only a single permutation will be there and just one position will be there.
So you will add.
You will append into this list c pay attention.
I am making sure that I am appending all of these in my all permutations.
Right?
So I am making a new one and I am just appending everything here, right?
Because this time I have to take everything.
So I will have to create my whole answer instead of just extending or taking the answer which I have
got.
Because this is not an answer, right?
This is not an answer.
So this time you are going to return Just see now for the sea.
Of course you have to position where B can be added based on the same logic.
This b this B is going to get added.
It will just return.
It will just have this c here okay.
This loop for each permutation in permutations it will going to run one time.
But here this time we have two positions okay.
So I'm going to get added and I'm going to add two permutations.
And I have BC and CA.
Now this is the same thing.
This is where you have to start.
So you don't have to actually worry on any of these things.
This is from where this is.
You have to assume and then write your code.
And I hope you understand this right.
These are I have already explained that how in this BC we have three positions.
So this will contribute to three permutations.
And this CA this also has three permutation.
Again contributing to sorry this has three position again contributing to three permutations.
And we would have finally got our answers.
If you will see this is going to be the exact order as well.
A b, c BSc BCA.
A b c BSc BCA.
Then I have written A here.
My bad.
It will be B.
So then it should be a c b c a b and c b a.
So a c b c a b and c b.
Okay so cool then everyone I hope this was clear.
Again, this is a very difficult question.
Honestly, it is not an easy question, but using the concept of recursion, which we have built up
over the few last few modules, this question will actually be easily doable by you all.
And yeah, this is one.
These are the types of questions which are combining all the different looping understanding string,
understanding recursion, understanding okay into one single code and then asking you to do it.
That's why it is asking lots of product based companies.
And these are the type of questions which you can expect in any tier one companies.
Okay.
So cool everyone, let's meet in the next video.
I hope this was clear.
Please make sure that you dryrun this month on Python Tutor as well, and try to make this tree at your
end.
Okay?
Thank you.