Hello again! In this video, we are going to look at permutations. A permutation is a possible arrangement
of some elements from a group, or a set, or a range.
For example, if you have some people around for dinner, there are various different ways you can get
them to sit at the table.
And each of those seating arrangements is a permutation.
Or you could have a pack of playing cards, and when you shuffle the cards, you get a different
arrangement of the cards, and that is different permutations.
The permutations represent all the possible arrangements.
So if we have "abc", the permutations are "abc", "acb" and so on.
And I have written those in alphabetical order.
The relevance of this is that there are algorithm functions, which are related to permutations.
next_permutation() will take an iterator range, and it will reorder the elements within that range
to give the next permutation.
And that will be in ascending order.
So for example, if we have "abc", then the next permutation of that will be "acb".
If the result is the last permutation in alphabetical order, then this will return false.
Otherwise, if there are more permutations, it will return true.
So that means, if we have all the elements in ascending order, we can call next_permutation() in a
loop and that will give us all the permutations.
So there is some code to do that. So we just keep calling next_permutation().
So if we start with "abc", then the next permutation is "acb", and this will return true because there
are more.
And it will keep on going. When it gets to "cba", which is the last one, this will return false.
And then the loop will terminate. As usual for things which involve ordering,
this uses the less-than operator by default, but you can provide a predicate function if you want
something different.
So let's try this out.
It is just the code we had before, really.
And there we are.
So we get the permutations of "abc" in ascending alphabetical order.
There is also a prev_permutation(), which will give the previous permutation, and we can do the same trick here
to get the permutations in reverse order.
But to do this, we need to sort the elements in descending order first.
The default for the sort() algorithm is to use the ascending order.
So we need to provide a lambda expression which does different sorts.
So if we have a limited expression which uses greater-than instead of less-than this will sort the
elements in descending order.
So here is the same code again. We have this call to sort. The lambda expression which uses greater-than instead
of less-than, to change the order, and then we can call prev_permutation().
So this will give the last permutation, then the last but one, and so on. And it will stop when it gets to the
first one.
And there we are.
Those are the permutations in reverse alphabetical order.
Finally, we can check whether two iterator ranges of permutations of each other.
So this is quite useful, actually. If you have two ranges which contain the same elements, but in a different
order, this will recognize that they actually have the same elements.
And this one will use the equality operator, by default.
So here we have two vectors, and then we call is_permutation(). These two contain the same elements
in a different order, so we expect to see this.
And there we are, "vec" is a permutation of "vec2".
And if we change them, so they are different. So they have different elements. Then they are not a
permutation.
So these are two vectors with the same elements, but in a different order.
Okay, so that is it for this video.
I will see you next time, but until then, keep coding!