Welcome back.
Notice that when the input array had three distinct elements, there were six permutations that we needed
to identify.
Now why is this number six or how can we identify this without writing out all the possible permutations?
Now, this probably is not required for solving this question, but it's a good thing to know.
So over here we have three elements.
And notice that in each of these permutations we have three elements.
For example over here also we have three elements over here also we have three elements.
So there are three positions.
And it's just about the different ways in which I can fill these positions with these three numbers,
because this is the input.
So the first position over here can be filled in three different ways.
Notice over here I have one, I have two and I have three.
So again if you take a look at all these six permutations, there are only these three ways of filling
the first position.
Now once I have filled the first position, I would be left with only two elements because I would have
used one of the three elements to fill and put it over here so the next position can be filled in two
ways.
Now again, notice over here, let's say I filled the first position with one.
Now that's these two cases over here.
Now in these two cases, I have only two ways of filling the second position.
So that's why once I'm done with filling the first position with one value, I can only fill the next
position in two ways.
And then once I've used two elements to place them over here and here, I'm just left with one way.
So that's why I will be able to fill this place only in one way.
So notice over here, once I filled one over here and two over here, there's just one way of filling
the last position, which is with three.
So that's why I can do this only in one way.
Therefore, the total number of ways in which I can fill these three positions with these three unique
values is this three into two into one.
So that's three into two into one, which gives me the answer as six.
And that's why we have six distinct permutations over here when we have three elements.
Now also notice that this six over here is nothing but three factorial, because again, we know that
three factorial is three into two into one.
Now that we have learned to identify the number of distinct permutations that are expected, what would
be the case if we have four elements?
Let's say the input is one, two, three, four.
In that case we would have four factorial permutations or 24 permutations.
All right.
So we have understood how to identify the number of permutations.
And this is a good to know thing.
Now let's proceed and try to think about how to solve this question.
So let's say the input which is given to us is one two, three.
And we need to identify all the permutations of this array.
If I were to write the indices that's zero one and two.
Now the approach that we can take is notice that if I just swap elements among themselves, like for
example, if I swap three and one, I can get three, two, one, which is one of the permutations.
Or if I can just swap two and three, I'll get one, three, two, which is again another valid permutation.
Or if I swap two and one I would get two, one three, which is again another valid permutation.
So I just need a systematic way of swapping elements among themselves so that I can identify all the
possible permutations.
So this is the approach that we will discuss over here.
And once I have identified a valid permutation let me add it to an array.
Let's say we can call that array permutations.
And then finally, once we are done identifying all the permutations we will just return this array.
So this is the approach that we are going to take.
So to identify all the permutations I need a systematic way of swapping elements among themselves.
And let me take two pointers for this.
So that's I and J.
Now J again will help me to swap the element at I with the element at j.
And for each value of I, j is going to start from the value of I till the last index, which is two
in this case.
So to start with we'll say that I is equal to zero.
And j is going to take the values from I, that is from zero till the last index which is index two.
So I'm going to swap zero and zero zero and one and zero and two.
If I swap the element at zero with the element at zero itself, that's swapping one with one itself.
So over here I'll have 123 itself.
Next.
If I swap the element at index zero with the element at index one, then I would have swapped these
two elements.
So I will get two, one, three.
And finally, if I swap the element at index zero with the element at index two, I will get 321.
Now again, this is not the way that the algorithm would go.
It would go deeper and then only it will go to the next branch.
But over here, I'm writing it down for our understanding, and at a later point we will once again
quickly trace how the algorithm would actually work.
So once we have done swapping zero with zero, we will increment the value of I and call the same function
recursively again.
So I is going to be equal to one and j in that case is going to start at the value of I which is one,
and it will go till the last index which is two.
So there are going to be two cases one where J is one, and the second case where j is two.
So for the case where I is equal to one, I am going to swap one and one and one and two.
And this is going to happen in each of these branches.
So for this branch where the instance of numb's at this point looks like this.
When I swap one and one, I will again get one, two, three.
And when I swap one and two, these two elements are going to be swapped, because this is index one
and this is index two.
So I will get 132.
All right.
And in a similar manner over here I'll get again two, one three.
And then I'll get two, three, one over here when I swap these two values.
And over here I'll get three, two, one.
And I will get 312.
Now once this is done this part over here will again recursively call the same function incrementing
I.
So I at that point will become two.
And when I is equal to two, I will hit the base case because j can can take nothing more, right?
J can just take the value two and there is no point in just swapping two with two.
So at this point I would have hit the base case and I will take a copy of this and add it to the permutations
array.
So over here, the same thing will happen in this case as well, because when I get one, three, two
and recursively call the same function again, I would be equal to two.
Therefore, I make a copy of it and put it over here.
And in a similar manner I'll make a copy of this and this as well.
And notice over here, when I'm done with this, I would have added all the permutations, all the valid
unique permutations to this array over here, and I can just return it.
So this is the approach that we will take to solve this question.
Notice that we are solving the question in place or changes to the state of the problem are made in
place, or all of these are actually the same array we have over here.
This and this, for example, are not two different arrays.
It's the same array, but we are just swapping it and making copies to get all the possible permutations.