1:17

So let's look at the basic properties of permutations.

Â And we talked about permutations before,

Â as an example when introducing labeled structures and analytic combinatorics.

Â So here's just one colorful metaphor to describe permutations that we discussed.

Â You have a group of N students, and they go to a party.

Â And they maybe become inebriated, that when the party's over,

Â they each wind up in a random room.

Â So you have the students have numbers 1 through 16 and

Â the rooms have numbers 1 through 16.

Â Then what you have if you arrange in order by student,

Â what you have is a random ordering of the numbers 1 through 16, or a permutation.

Â So we looked at those from the standpoint of analytic combinatorics

Â as a sequence of labeled atoms where each possible ordering is different.

Â So there's six permutations of three elements, and

Â 24 permutations of four, and so forth.

Â And so there's n factorial permutations of n elements, and from the point of view

Â of generating functions, the exponential generating functions for permutations,

Â the counting sequence is N factorial.

Â And we have a normalizing factor N factorial, so those cancel out, and

Â it's the exponential generating function for

Â permutations is sum of Z to the n of 1 over 1-Z.

Â And this is just a quick review of what we talked about in

Â the analytic combinatorics lecture.

Â So now, there's many,

Â many interesting properties of permutations that have been studied.

Â So one thing that's often of interest is what's called the inverse of

Â a permutation.

Â Another way to think of a permutation is as a mapping

Â of the set of numbers from 1 through N to itself.

Â So our student to room, that's a mapping from 1 to 9, 2 to 12, and so

Â forth, where all the numbers from 1 through N appear in the mapping.

Â So there's a concept known as the inverse of a permutation,

Â which is just the inverse of that mapping.

Â And one way to look at that is to rearrange the permutation

Â table so that it's in order by the rooms, and then flip it.

Â So permutation maps students to rooms,

Â the inverse of that permutation maps rooms to students.

Â So it says that in room 1 has student 7 in it,

Â room 2 has student 13 in it, and so forth.

Â Whereas the permutation told us which student was in which room.

Â And there's lots of direct applications of inverse.

Â How do you compute the inverse?

Â It's a very simple process, here's the code for it.

Â And the code is only slightly complicated because nowadays,

Â arrays in Java and C and other languages are zero-based.

Â The first thing's at zero, and

Â we've been using permutations the first things at one.

Â But let's look at an example and then we'll go back to the code.

Â So if we have this permutation shown on the right, where 1 maps to 8,

Â 2 maps to 1, and so forth.

Â We want to compute the inverse of that permutation.

Â The process is very simple.

Â We start out with an empty array, and

Â the first thing we do to get the inverse 1 goes to 8.

Â So in the inverse, 8 is going to have to go to 1.

Â So we simply put a 1 in position 8 in the inverse.

Â And then we just move from left to right, we put a 2 in position 1,

Â 3 in position 3, 4 in position 7, 5 in position 6,

Â 6 in position 2, 7 in 9, 8 in 4, and 9 in 5, and so forth.

Â So since we know that each thing appears only once,

Â there's no collision in this process.

Â In simply one pass through the array, as shown in the for

Â loop in the code at left, we can fill in the inverse, in this case, the array B.

Â And since the arrays are zero-based,

Â we have to subtract 1 from the permutation number.

Â So when 2 goes into position 1, it goes into the first position in the array,

Â which is position 0, so we subtract one.

Â And then we're using index i that goes from 0 to N-1, so

Â we're ready to stick with the convention that we've been using.

Â With 1 through N, we just add 1 to i.

Â So that's an easy computation, one pass through,

Â we can compute the inverse of a permutation.

Â And here's a sample application, one of the simplest cipher

Â mechanisms is simply, it's called a substitution cipher, is,

Â first generate a random permutation of the letters A through Z.

Â And in this case, we use a minus sign for a blank.

Â And we'll talk about generating random permutation in a minute.

Â And then we use that mapping to encrypt a message.

Â So if the message, which is called the plaintext, is, attack at dawn,

Â then the random permutation tells us that A should map to W, T to P,

Â T to P again, A to W again, C to L, and so forth.

Â And that gives us the ciphertext, and it's encrypted.

Â We can send that ciphertext, and an eavesdropper couldn't figure out

Â what the plaintext is without knowing the random permutation.

Â So that's a simple cipher system.

Â And now, but the receiver of the message, in order to be able to understand

Â what the message says, has to have the inverse of that permutation.

Â So that's a key that's transmitted, and they're generated in some other way.

Â But in order to decrypt, we need the inverse of the permutation.

Â 13:36

And the key concept, as we saw, was,

Â we need a model for the input to a sorting algorithm.

Â And one thing to start with is to say that the inputs are randomly ordered.

Â They represent a random permutation.

Â The question is, is that a realistic model?

Â And the answer is that absolutely it's a realistic model if we

Â just apply a random permutation to the input before the sort.

Â So the input might not be in random order, in this case, it's in reverse order.

Â But if we randomly permute it, then we absolutely have a situation

Â where we're sorting a set of items that are random permutations.

Â So the model is exact.

Â So if we study properties of random permutations, then we get properties

Â of our sorting algorithms, and that's what we're going to be doing.

Â That's what we did for quicksort, and we'll do for

Â several other sorting algorithms today.

Â So in order to do this, though,

Â you need to be able to generate a random permutation properly.

Â And actually, at the beginning, people would get this wrong and

Â generate things that looked like they were randomly permuted, but

Â actually did not generate each permutation with equal likelihood.

Â So nowadays, we use a method articulated by Knuth and probably earlier.

Â We just go from left to right and

Â exchange each entry with a random entry to its right.

Â So there's a two liner or

Â four liner, five liner to generate a random permutation.

Â i goes from 0 to n, we generate a index r that is somewhere between i and

Â n minus 1, between the current position and the end of the array.

Â And then exchange the element at position i with the element at position r.

Â So again, if we start with this input, maybe that's in reverse order.

Â And the first case generates a index that points to N and exchange T and N.

Â And next time, we're going to exchange S with L and

Â then T with R, and then R with P, and so forth.

Â So each time, the element that gets picked is picked at random from

Â the ones that have not been chosen yet.

Â And continuing that process, we get a random permutation of the input arrays.

Â Where if we just want to generate a random permutation,

Â just start with 1 through N as the input, and you get out a random permutation.

Â And this process generates all permutations with equal likelihood,

Â and that's easy to see.

Â The first entry is equally likely to be any one of the N entries.

Â We're picking any value from 0 to N minus 1 at random,

Â we could get any one of them, so there's N possibilities for the first entry.

Â Similarly, there's N minus 1 possibilities for the second entry, and so forth.

Â So there's a total of N factorial different permutations that

Â are possible to be generated, and they're all equally likely.

Â