WEBVTT 00:00.120 --> 00:07.410 Hello again! In this video, we are going to look at permutations. A permutation is a possible arrangement 00:07.410 --> 00:11.010 of some elements from a group, or a set, or a range. 00:12.030 --> 00:16.350 For example, if you have some people around for dinner, there are various different ways you can get 00:16.350 --> 00:17.850 them to sit at the table. 00:18.300 --> 00:21.090 And each of those seating arrangements is a permutation. 00:22.860 --> 00:27.060 Or you could have a pack of playing cards, and when you shuffle the cards, you get a different 00:27.070 --> 00:29.730 arrangement of the cards, and that is different permutations. 00:30.390 --> 00:33.630 The permutations represent all the possible arrangements. 00:34.260 --> 00:38.850 So if we have "abc", the permutations are "abc", "acb" and so on. 00:39.570 --> 00:41.610 And I have written those in alphabetical order. 00:42.690 --> 00:47.670 The relevance of this is that there are algorithm functions, which are related to permutations. 00:51.130 --> 00:56.860 next_permutation() will take an iterator range, and it will reorder the elements within that range 00:57.070 --> 00:58.360 to give the next permutation. 00:58.690 --> 01:00.280 And that will be in ascending order. 01:00.880 --> 01:05.830 So for example, if we have "abc", then the next permutation of that will be "acb". 01:07.670 --> 01:13.580 If the result is the last permutation in alphabetical order, then this will return false. 01:14.510 --> 01:17.480 Otherwise, if there are more permutations, it will return true. 01:18.140 --> 01:22.970 So that means, if we have all the elements in ascending order, we can call next_permutation() in a 01:22.970 --> 01:25.280 loop and that will give us all the permutations. 01:26.710 --> 01:31.030 So there is some code to do that. So we just keep calling next_permutation(). 01:31.570 --> 01:36.970 So if we start with "abc", then the next permutation is "acb", and this will return true because there 01:36.970 --> 01:37.510 are more. 01:37.960 --> 01:42.970 And it will keep on going. When it gets to "cba", which is the last one, this will return false. 01:43.120 --> 01:48.370 And then the loop will terminate. As usual for things which involve ordering, 01:48.370 --> 01:52.930 this uses the less-than operator by default, but you can provide a predicate function if you want 01:52.930 --> 01:53.620 something different. 01:54.910 --> 01:56.380 So let's try this out. 01:56.450 --> 01:58.110 It is just the code we had before, really. 02:00.430 --> 02:00.940 And there we are. 02:01.060 --> 02:05.350 So we get the permutations of "abc" in ascending alphabetical order. 02:09.210 --> 02:15.210 There is also a prev_permutation(), which will give the previous permutation, and we can do the same trick here 02:15.210 --> 02:17.370 to get the permutations in reverse order. 02:17.970 --> 02:22.050 But to do this, we need to sort the elements in descending order first. 02:22.800 --> 02:25.620 The default for the sort() algorithm is to use the ascending order. 02:25.950 --> 02:30.450 So we need to provide a lambda expression which does different sorts. 02:31.020 --> 02:36.840 So if we have a limited expression which uses greater-than instead of less-than this will sort the 02:36.840 --> 02:38.220 elements in descending order. 02:41.890 --> 02:48.340 So here is the same code again. We have this call to sort. The lambda expression which uses greater-than instead 02:48.340 --> 02:53.040 of less-than, to change the order, and then we can call prev_permutation(). 02:53.380 --> 02:58.630 So this will give the last permutation, then the last but one, and so on. And it will stop when it gets to the 02:58.630 --> 02:59.140 first one. 03:01.950 --> 03:02.490 And there we are. 03:02.520 --> 03:05.340 Those are the permutations in reverse alphabetical order. 03:07.740 --> 03:11.400 Finally, we can check whether two iterator ranges of permutations of each other. 03:11.640 --> 03:16.110 So this is quite useful, actually. If you have two ranges which contain the same elements, but in a different 03:16.110 --> 03:19.350 order, this will recognize that they actually have the same elements. 03:20.790 --> 03:23.940 And this one will use the equality operator, by default. 03:25.880 --> 03:33.410 So here we have two vectors, and then we call is_permutation(). These two contain the same elements 03:33.410 --> 03:35.720 in a different order, so we expect to see this. 03:38.690 --> 03:41.060 And there we are, "vec" is a permutation of "vec2". 03:42.560 --> 03:48.820 And if we change them, so they are different. So they have different elements. Then they are not a 03:48.820 --> 03:49.430 permutation. 03:53.030 --> 03:56.090 So these are two vectors with the same elements, but in a different order. 03:56.810 --> 03:58.310 Okay, so that is it for this video. 03:58.670 --> 04:01.460 I will see you next time, but until then, keep coding!