1 00:00:00,012 --> 00:00:08,724 Today, our topic is Permutations, another basic combinatorial structure that we 2 00:00:08,724 --> 00:00:13,306 study because it has numerous applications in analysis of algorithms. 3 00:00:15,205 --> 00:00:20,594 Again, continuing the orientation that we introduced in the last lecture, we're on 4 00:00:20,594 --> 00:00:25,357 the second part of the class where we're surveying fundamental combinatorial 5 00:00:25,357 --> 00:00:30,288 classes and mathematical techniques that we covered in the first half of the 6 00:00:30,288 --> 00:00:33,777 class. Primarily analytic combinatorics to study 7 00:00:33,777 --> 00:00:38,682 properties of these classes. Last time we studied trees, mostly, from 8 00:00:38,682 --> 00:00:44,137 the standpoint as unlabeled structures which we analyze with ordinary generating 9 00:00:44,137 --> 00:00:46,857 functions. This time we're going to switch to 10 00:00:46,857 --> 00:00:52,677 labeled structure as permutations. in exponential generating functions. 11 00:00:52,677 --> 00:00:58,932 again there's many more, examples i the book then you can possibly cover in 12 00:00:58,932 --> 00:01:02,827 lectures. what we try to do in lectures is cover 13 00:01:02,827 --> 00:01:09,222 some of the interesting ones then you can read more, in For the extend your 14 00:01:09,222 --> 00:01:14,432 knowledge by studying from the book. You couldn't possibly cover, all the 15 00:01:14,432 --> 00:01:17,107 examples that are in the book in lectures. 16 00:01:17,107 --> 00:01:21,002 so let's look at the basic properties of permutations. 17 00:01:21,002 --> 00:01:25,877 We talked about permuations before as an example in introducting labeled 18 00:01:25,877 --> 00:01:31,739 strucutres in analytical combinatorics. So here's just 1 colorful metaphor to 19 00:01:31,739 --> 00:01:35,477 describe permutations that we've discussed. 20 00:01:35,477 --> 00:01:41,974 You have a group of N students that go to a party and they maybe become inebriated 21 00:01:41,974 --> 00:01:47,112 that when the party is over they each wind up in a random room. 22 00:01:47,112 --> 00:01:51,946 So if the students have numbers one through sixteen, and the rooms have 23 00:01:51,946 --> 00:01:56,754 numbers one through sixteen. Then, what you have if you arrange in 24 00:01:56,754 --> 00:02:00,727 order by student. What you have is a random ordering of the 25 00:02:00,727 --> 00:02:04,022 numbers one through sixteen, or a permutation. 26 00:02:04,022 --> 00:02:11,726 so in, we looked at those, from the standpoint of analytic combinatorics as a 27 00:02:11,726 --> 00:02:17,908 sequence of labeled atoms. where each possible ordering is 28 00:02:17,908 --> 00:02:22,502 different. So there's six permutations of three 29 00:02:22,502 --> 00:02:25,429 Elements in 24 permutations of 4, and so forth. 30 00:02:25,429 --> 00:02:28,807 And so there's N factorial permutations of N elements. 31 00:02:28,807 --> 00:02:33,688 And from the point of view of generating functions, the exponential generating 32 00:02:33,688 --> 00:02:37,796 functions for permutations it kind of sequences in factorial. 33 00:02:37,796 --> 00:02:40,673 And we have a normalizing factor, N factorial. 34 00:02:40,673 --> 00:02:44,462 So, those cancel out and it's the exponential generating. 35 00:02:44,462 --> 00:02:50,437 Function for permutations, is sum of z^n 1/1-z. And this is just a quick review of 36 00:02:50,437 --> 00:02:54,404 what we talked about, in the analytic combinatorics lecture. 37 00:02:54,404 --> 00:03:00,062 so now, this, many, many interesting properties of permutations that have been 38 00:03:00,062 --> 00:03:03,845 studied. so, one thing that's often of interest is 39 00:03:03,845 --> 00:03:06,992 what's called the inverse, of a permutation. 40 00:03:06,992 --> 00:03:11,980 Another way to think of a permutation is as a mapping of the numbers from one 41 00:03:11,980 --> 00:03:15,833 through n, the set of numbers from 1 through n, to itself. 42 00:03:15,833 --> 00:03:21,366 so our student to room then, that's a mapping from one to nine, two to 12 and 43 00:03:21,366 --> 00:03:26,932 so forth where all the numbers from one through n appear in the mapping. 44 00:03:26,932 --> 00:03:30,582 Thing. So there's a concept known as the inverse 45 00:03:30,582 --> 00:03:35,657 of a permutation. which is just the inverse of that mapping 46 00:03:35,657 --> 00:03:40,732 and one way to look at that is to rearrange the permutation table. 47 00:03:40,732 --> 00:03:44,974 so that it's in order by the rooms and then, flip it. 48 00:03:44,974 --> 00:03:51,453 so permutation maps students to room, the inverse of that permutation maps rooms to 49 00:03:51,453 --> 00:03:55,225 students. So, it says that student room 1 has 50 00:03:55,225 --> 00:03:59,180 student 7 in it, room 2 has student 13 in it and so forth. 51 00:03:59,180 --> 00:04:04,422 where as the permutation told us which student was in which room. 52 00:04:04,422 --> 00:04:09,457 and there's lots of direct a- a- applications of inverse. 53 00:04:09,457 --> 00:04:14,618 how do you compute the inverse? it's a very simple process. 54 00:04:14,618 --> 00:04:19,962 here's the code for it and the code is only slightly complicated because 55 00:04:19,962 --> 00:04:24,432 Nowadays arrays in Java, C, and other languages are uh,zero-based, the first 56 00:04:24,432 --> 00:04:28,889 thing's at 0, and we've been using permutations the first thing's at 1 but 57 00:04:28,889 --> 00:04:32,263 let's look at an example and then we'll go back to the code. 58 00:04:32,263 --> 00:04:37,716 So if we had this permutation shown on the right where 1 maps to 8, 2 maps to 1 59 00:04:37,716 --> 00:04:41,576 and so forth. we want to compute the inverse of that 60 00:04:41,576 --> 00:04:45,542 permutation. The process is very simple we start out 61 00:04:45,542 --> 00:04:50,968 with an, an empty array. and the first thing you do, to get the 62 00:04:50,968 --> 00:04:56,197 inverse, one goes to eight so in the inverse, eight is going to have to go to 63 00:04:56,197 --> 00:04:59,388 one. So we simply put a one in position eight 64 00:04:59,388 --> 00:05:03,090 in the inverse. And then we just move from left from 65 00:05:03,090 --> 00:05:06,602 right we put a 2 in position 1, 3 in position 3. 66 00:05:06,602 --> 00:05:09,816 Four in position seven. Five in position six. 67 00:05:09,816 --> 00:05:12,303 Six in position two. Seven in nine. 68 00:05:12,303 --> 00:05:15,411 Eight in four. And nine in five and so forth. 69 00:05:15,411 --> 00:05:19,633 so since we know that, each thing appears only once. 70 00:05:19,633 --> 00:05:25,362 There's no collision in this process, and simply one pass through the array is 71 00:05:25,362 --> 00:05:28,289 showed in the for loop in the code at left. 72 00:05:28,289 --> 00:05:32,372 you can fill in the inverse in this case, the array. 73 00:05:32,372 --> 00:05:38,610 Be and since the arrays are 0 based we have to subtract 1 from the permutation 74 00:05:38,610 --> 00:05:42,095 number. so when 2 goes into position 1 it goes 75 00:05:42,095 --> 00:05:47,442 into the first position in the array which is position 0, so we subtract 1. 76 00:05:47,442 --> 00:05:53,534 and then we're using index i that goes from 0 to n -1 so we really need to stick 77 00:05:53,534 --> 00:05:58,706 with the convention we've been using with 1 through n we just add 1 to i. 78 00:05:58,706 --> 00:06:04,290 So that's an easy computation one pass through we can compute the inverse of a 79 00:06:04,290 --> 00:06:08,920 computation. and here's a, a sample application, one 80 00:06:08,920 --> 00:06:15,587 of the simplest cipher mechanisms is simply to, it's called a substitution 81 00:06:15,587 --> 00:06:21,799 cipher, is first generate a random permutation of the letters A through z 82 00:06:21,799 --> 00:06:25,700 and in this case we use a minus sign for a blank. 83 00:06:25,700 --> 00:06:30,752 we'll talk about generating random permutation in a minute. 84 00:06:30,752 --> 00:06:35,216 and then we use that mapping to encrypt a message. 85 00:06:35,216 --> 00:06:40,687 So if the message what's just called the plain text, plain text, is attack at 86 00:06:40,687 --> 00:06:45,996 dawn. Then the random permutation tells us that 87 00:06:45,996 --> 00:06:50,237 A should map to W. T to P, T to P again, A to W again. 88 00:06:50,237 --> 00:06:55,878 C to L and so forth. And that gives us a cypher text, and it's 89 00:06:55,878 --> 00:07:01,572 encrypted we can send that cypher text and an eaves-dropper. 90 00:07:01,572 --> 00:07:07,031 couldn't figure out what the plain text is, without knowing the random 91 00:07:07,031 --> 00:07:10,725 permeation. So, that's a simple sipher system and 92 00:07:10,725 --> 00:07:16,505 now, but the receiver of the message, in order to be able to understand what the 93 00:07:16,505 --> 00:07:20,485 message says. Has to have the inverse of that 94 00:07:20,485 --> 00:07:25,269 permutation. so that's a key that's transmitted in, or 95 00:07:25,269 --> 00:07:30,467 generated in some other way. But in order to decrypt, we need the 96 00:07:30,467 --> 00:07:36,377 inverse of the permutation. and the inverse will tell us that W is 97 00:07:36,377 --> 00:07:41,168 supposed to go to A. P is supposed to go to T and so forth And 98 00:07:41,168 --> 00:07:45,701 so that just a computing the inverse as in the previous slide. 99 00:07:45,701 --> 00:07:51,822 and that gives a mechanism for converting the cipher text back to the plain text. 100 00:07:51,822 --> 00:07:56,572 So that's a very simple application of the inverse of a permutation. 101 00:07:56,572 --> 00:08:06,739 now actually this type of cypher system is not so often used nowadays because it 102 00:08:06,739 --> 00:08:11,762 always maps each character to the same character. 103 00:08:11,762 --> 00:08:17,867 And so actually an eavesdropper, can figure out by the frequency of occurrence 104 00:08:17,867 --> 00:08:22,587 of the letters which, which letter codes to which letter. 105 00:08:22,587 --> 00:08:29,982 and actually not too difficult to solve a cipher system built this way from that 106 00:08:29,982 --> 00:08:35,657 frequency frequency analysis. but it's useful as maybe a piece of a 107 00:08:35,657 --> 00:08:40,511 cipher system. sometimes we work with what's called the 108 00:08:40,511 --> 00:08:47,326 lattice representation of a permutation. We simply make an end-by-end matrix. 109 00:08:47,326 --> 00:08:51,432 and down at the bottom is the permutation. 110 00:08:51,432 --> 00:08:57,947 so it makes a, a, example for a mutation. And all we do is for each entry in the 111 00:08:57,947 --> 00:09:02,640 permutation, we put a block in the corresponding row. 112 00:09:02,640 --> 00:09:08,122 So the first column corresponds to ninth we put a block in row nine. 113 00:09:08,122 --> 00:09:12,811 Second column, 12. Put a black in red 12. 114 00:09:12,811 --> 00:09:17,550 11-10. then 5, and then so forth. 115 00:09:17,550 --> 00:09:23,442 So we have N blocks marked in that permutation. 116 00:09:23,442 --> 00:09:28,731 In that lattice in it is a direct correspondence to that permutation. 117 00:09:28,731 --> 00:09:34,223 and then, what's interesting and it doesnt take too much thought to convince 118 00:09:34,223 --> 00:09:39,472 yourself this works, is if you look on the columns that are marked one by one 119 00:09:39,472 --> 00:09:45,547 The first column is marked as 7, the second one is 13 and so forth. 120 00:09:45,547 --> 00:09:52,397 And if you just read off the columns that marked, what you get is the inverse of 121 00:09:52,397 --> 00:09:57,997 the permutation. so [COUGH] the, in the permutation, 1 122 00:09:57,997 --> 00:10:02,082 maps to 9. And then in the incerse, 9 maps to 1. 123 00:10:02,082 --> 00:10:07,767 so that block is interpreted both ways and, in fact, if you take the transpose 124 00:10:07,767 --> 00:10:12,387 of the representation of the permutation in terms of the lattice, you get 125 00:10:12,387 --> 00:10:17,742 representation of the inverse. so that's sometimes a, a useful way to or 126 00:10:17,742 --> 00:10:24,187 interesting way to look at permutations. and re- remember when we talked about 127 00:10:24,187 --> 00:10:30,704 introduced analytic combinatorics, we talked about the cycle representation of 128 00:10:30,704 --> 00:10:35,702 a permutation. so if Student 4 was at room. 129 00:10:35,702 --> 00:10:42,412 In room, [COUGH], in room 10, in, goes to room 10, he's going to find student 6 130 00:10:42,412 --> 00:10:46,527 there, student 6 is going to go to room 15 and so forth. 131 00:10:46,527 --> 00:10:50,872 eventually Student 4 will find his room that way. 132 00:10:50,872 --> 00:10:58,252 so, doing that for every position, in the permeation, we, it's, we saw that, 133 00:10:58,252 --> 00:11:03,552 there's a set of cycles that's equivolent to any given permeation. 134 00:11:03,552 --> 00:11:09,308 [COUGH] and, with that set of cycles representation, we're able to analyze 135 00:11:09,308 --> 00:11:14,572 interesting properties of permutation. I mention that 'cuz we're going to extend 136 00:11:14,572 --> 00:11:20,215 some of that analysis later on. and [COUGH], then the tool, the main tool 137 00:11:20,215 --> 00:11:26,305 that we use to study permutations when introduce it for analytic combinatorics. 138 00:11:26,305 --> 00:11:31,272 and today the starting is the symbolic method for labeled classes. 139 00:11:31,272 --> 00:11:35,821 we had a, number of common notarial constructions. 140 00:11:35,821 --> 00:11:42,017 Other natural ways to define sets of label objects including permutations with 141 00:11:42,017 --> 00:11:46,332 restrictions on cycle lengths and other properties. 142 00:11:46,332 --> 00:11:52,150 And the symbolic method is a set of transfer theorems, or a, a transfer 143 00:11:52,150 --> 00:11:58,547 theorem, that defines a correspondence between a construction and operation on a 144 00:11:58,547 --> 00:12:04,416 generating function so when we build constructions, we get generating 145 00:12:04,416 --> 00:12:08,457 functions. so for example The, one way to count 146 00:12:08,457 --> 00:12:15,061 permutations using the symbolic method, define the class of all permutations and 147 00:12:15,061 --> 00:12:21,301 the exponential generating function, which is each permutation, Z to the size 148 00:12:21,301 --> 00:12:27,748 divided by size factorial, which is equivalent to sum of N of the number of 149 00:12:27,748 --> 00:12:34,561 permutations of size N, z/N factorial. The combinatorial construction, that 150 00:12:34,561 --> 00:12:39,588 creates permutations. So is that a permutations either empty or 151 00:12:39,588 --> 00:12:43,383 it's a star product of an atom and a permutation. 152 00:12:43,383 --> 00:12:47,568 And that transfers immdediately to the OGF equation. 153 00:12:47,568 --> 00:12:51,652 1+zP(z). and that has a solution, 1/1-z). 154 00:12:51,652 --> 00:12:56,601 and then the co-efficient is z/N, and that is N factorial. 155 00:12:56,601 --> 00:13:02,071 So, a fine application of the study of permutation is sorting algorithms. 156 00:13:02,071 --> 00:13:08,318 chapter 2 of our algorithm book has numerous classic sorting out algorithms. 157 00:13:08,318 --> 00:13:14,409 And, these things are very efficient, well studied, widely used and extremely 158 00:13:14,409 --> 00:13:17,694 useful. And one reason that we've been able to 159 00:13:17,694 --> 00:13:22,922 develop them to the point where they're so efficient is that we have mathematical 160 00:13:22,922 --> 00:13:26,572 models based on permutations that help us understand them. 161 00:13:26,572 --> 00:13:31,646 And we saw examples of that in the very first lecture and second lecture when we 162 00:13:31,646 --> 00:13:35,562 talked about the analysis of quick sort and merge sort. 163 00:13:35,562 --> 00:13:42,407 and the key concept as we saw, was we need a model for the input to a sorting 164 00:13:42,407 --> 00:13:46,937 algorithm. and 1 thing to start with is to say that 165 00:13:46,937 --> 00:13:52,483 the inputs are randomly ordered. They perform, they represent a random 166 00:13:52,483 --> 00:13:56,293 permutation. the question is, is that a realistic 167 00:13:56,293 --> 00:14:01,501 model? and the answer is, that absolutely it's a realistic model. 168 00:14:01,501 --> 00:14:06,425 if we just apply a random permutation to the input before the sort. 169 00:14:06,425 --> 00:14:12,095 so the input might not be in random. In the motor in this case it's in reverse 170 00:14:12,095 --> 00:14:17,587 order but if we randomly permute it then we absolutely have a situation where 171 00:14:17,587 --> 00:14:23,053 we're sorting a set of items that are random permutations so the model is 172 00:14:23,053 --> 00:14:25,627 exact. So if we study properties of random 173 00:14:25,627 --> 00:14:29,347 permutations then we get properties of our sorting algorithms. 174 00:14:29,347 --> 00:14:33,867 And that's what we're going to be doing. that's what we did for quick sort and 175 00:14:33,867 --> 00:14:37,032 we'll do for several other sorting algorithms today. 176 00:14:37,032 --> 00:14:41,959 so in order to do this though, you need to be able to generate a random 177 00:14:41,959 --> 00:14:46,857 permutation properly. and actually at the beginning people 178 00:14:46,857 --> 00:14:50,824 would get this wrong. They'd generate things that looked like 179 00:14:50,824 --> 00:14:55,867 they were randomly permuted. But actually did not generate each 180 00:14:55,867 --> 00:15:01,507 permutation with equal likelihood. so nowadays,uh, we use a method 181 00:15:01,507 --> 00:15:05,458 articulated, by Knuth and probably earlier. 182 00:15:05,458 --> 00:15:10,369 And just go from left to right. And exchange each entry with a random 183 00:15:10,369 --> 00:15:16,677 entry to its right. so there's a 2 liner, a 4 liner, a 5 184 00:15:16,677 --> 00:15:26,612 liner to a generate a random permutation, I goes from 0 to N we generate a, index r 185 00:15:26,612 --> 00:15:33,559 that is somewhere between i and n-1 between the current position and the end 186 00:15:33,559 --> 00:15:39,566 of the array and then exchange the element at position i with element at 187 00:15:39,566 --> 00:15:46,839 position r So again if we start with this input maybe that's in reverse order. 188 00:15:46,839 --> 00:15:53,652 and first case generates an index that points to N in exchange to T and N. 189 00:15:53,652 --> 00:16:00,710 And next, next time were going to exchange S with L, and then T with R, and 190 00:16:00,710 --> 00:16:08,807 then R with P, and so forth. so each time the element that gets picked at random 191 00:16:08,807 --> 00:16:12,727 from the ones that had not been chosen yet. 192 00:16:12,727 --> 00:16:19,277 and we continue in that process we get a random permutation of the input arrays. 193 00:16:19,277 --> 00:16:25,562 Or if we just want to generate a random permutation just start with 1 through N 194 00:16:25,562 --> 00:16:29,202 as the input and you get out a random permutation. 195 00:16:29,202 --> 00:16:34,757 In this process generates all permutations with equal likelihood and 196 00:16:34,757 --> 00:16:39,414 then that's easy to see. the first entry is equally likely to be 197 00:16:39,414 --> 00:16:45,187 anyone of the N entries, where picking any value from 0 to N-1 at random, we 198 00:16:45,187 --> 00:16:50,982 could get any one of them, so there's N possibility for the first entry. 199 00:16:50,982 --> 00:16:56,237 Similarly, there's N-1 possibility for the second entry, and so forth. 200 00:16:56,237 --> 00:17:00,857 So there's a total of N factorial different, choices, different 201 00:17:00,857 --> 00:17:04,337 permutations that are possible to be generated. 202 00:17:04,337 --> 00:17:08,852 And they're all equally likely. That's the basic properties of 203 00:17:08,852 --> 00:17:12,517 permutations. And next, we'll going into looking at 204 00:17:12,517 --> 00:17:14,125 analyzing some of them.