This course teaches a calculus that enables precise quantitative predictions of large combinatorial structures. In addition, this course covers generating functions and real asymptotics and then introduces the symbolic method in the context of applications in the analysis of algorithms and basic structures such as permutations, trees, strings, words, and mappings.
Left-Right-Minima
Loading...
Del curso dictado por Princeton University
Analysis of Algorithms
37 calificaciones
De la lección
Permutations
The study of sorting algorithms is the study of properties of permutations. We introduce analytic-combinatoric approaches to studying permutations in the context of this relationship.
Conoce a los instructores
Robert SedgewickWilliam O. Baker *39 Professor of Computer Science
Computer Science
So next we're going to look at properties of permutations.
And as our main example we're going to talk about what's called left to right
minima in permutations.
So this is a parameter of permutations.
So I want to talk some about the general approach that we use for
analyzing parameters, and we talked about it last time for trees.
So we talked about leaves in random binary trees last time.
So we're going to use the cumulative cost approach because we can
use this symbolic method in a very straight forward manner.
Recall that we're going to define generating functions for
the counting sequence and for the accumulating cost.
And then we're going to have a construction, and the construction will
give a generating function equation for the accumulating generating function.
And then we're going to either solve to get an explicit formula,
or find another way to extract coefficients to get the counting sequence.
And the cumulated cost and then we divide the cumulated cost by
the counting sequence in order to get the expected value.
And we did that for the leaves and binary trees last time.
And that's the general approach
that we typically use in analytical common torques to analyze parameters.
Now for permutations, there's a small trick.
There's also a small trick for strings, we'll see next time.
And so, first thing is we're going to use exponential
generating function for the accumulated cost.
So, and it's exponential in the size so we're going to consider
the generating functions of the form b of z = the sum over all permutations.
Whatever the cost of the parameter that we're analyzing,
times z to the size of the permutation over the size factorial.
And that's again, if you group them by their size.
That's z to the m over N factorial times the cost.
So exponential cumulative generating function.
What we'll do is treat that as an OGF to get the expected value out directly.
It's a little, so b sub n is the total accumulated cost.
That's the total cost for all permutations of size N.
B sub N over N factorial is the average.
So this works because N factorial is both
the normalizing factor, and it's the counting sequence.
So really this is shorthand for N factorial times the coefficients of ZP and
BZ is the total cumulative cost.
N factorial is also the counting sequence.
So if we just extract the coefficient of Z to the N.
We get the average for permutations.
So that's what we're going to do, is we're going to work with the, an exponential
accumulated generating function, but then when it's time to extract coefficients.
We'll just extract coefficient at z to the n and
immediately get the average value of the parameter.
So the application is an elementary method known as selection sort.
It takes quadratic time for randomly ordered permutations, but
it's the method of choice for some situations.
For example, when records are large,.
You can read about that in the algorithms book,
and it's a very simple algorithm that goes through from left to right.
The first thing it does is find the minimum element in the permutation,
exchanges that with the first.
Then it finds the minimum in what remains, and exchanges that with the second and
so forth.
So, first question is, how many times
there's a variable that keeps track of the current minimum in this code.
And the question is, how many times is that variable updated?
Assuming that all the keys are distinct.
So, in this example, we start out thinking that S is the minimum, O is less.
So we update it.
R and T are being but I is less.
So we update it again.
G, E and finally A is the 5th update.
So, for this permutation, min is updated five times in the first pass.
This quantity is called the number of left to right minima in the permutation.
So, that's what we want to analyze first.
Now so, that's our question.
How many left to right minima are there in a random permutation?
Now, from a practical standpoint,
this question is maybe less important than some of the others we talk about.
Because this cost is not significant compared to the number of compares.
But still, it's a fundamental property of permutations that we want to study.
So a left to right minima, or we call an lrm, in a permutation.
It's a parameter, a permutation, and
it's an element that's smaller than any item to its left.
So if a permutation begins with one, like the ones on the top in
this example It's only got one left-right minimum the one.
If it begins with two.
It's got exactly two.
The two and the one.
If it begins with three.
It might have two, or it might have three and so forth.
Permutation in reverse order size N has N left-right minima.
Each new one is a minima.
And so, these tables in our standard form show for
each permutation the number of left-right minima off to the side.
Then the total cumulative cost is just summing those numbers,
or the [COUGH] for three elements, accumulated costs.
There's two that cost.
One and three that cost two, and one that costs three sets of total of 11.
Divide that by n factorial, the average number of left to right
minima in a random permutation of size three is 1.833.
And similarly, for size four, it's 2.083, and so forth.
How many left to right minima in a random permutation of size n.
So, that's our questions.
And again, as usually, it's very worth while to fully compute small values
both to get an appreciation for the intricacies of the problem.
And also to have precise values to check against when we complete the analysis.
So that's what this table is.
So what we're going to do is use a combinatorial construction to help
us derive directly a relationship
that the cumulative generating function has to satisfy.
And that's figuring out which construction to
use is the art of analytic combinatorics for these kinds of problems.
So for left to right minima, we're going to use a star product construction.
Where we say a permutation is a permutation starred with an element,
and that gives us a permutation one bigger and
it has to be renumbered in all consistent ways.
And that just corresponds to, giving the last element.
The numbers from one through n plus one and
then renumbering the other elements in the permutation accordingly.
So now if you look at the original permutation.
In this case, has three left to right minima.
All the permutations that we got from the star product have the same
number of left to right minima,
with the exception of the first one has an extra one, which is the one at the end.
So that construction and that observation tells us if we
know the number of left to right minima in the original permutation.
We know the number of left to right minima in all the permutations that we
constructed.
And that's, there's p + 1 of them, and
every one of them has the same number of left to right minima as p did.
So those copies, and then there's one extra one.
The one that ends in one.
So that's the combinatorial construction for permutations.
And then we're going to use that to derive a formula that
the generating function, the cumulated generating function, has to satisfy.
P plus one lrm or plus one.
So to compute the average number of left right minima in a permutation.
We define the cumulated generating function, which is the sum for every
permutation of its number of left-right minima times the size or size factorial.
And again, if you group the permutations by their size,
that gives the cumulated cost.
The exponential generating function for
the cumulated cost, which we'd know at the end.
So now if we apply the construction.
Every permutation gives us p+1 permutations.
So in the number of left-right minima in those permutations is size of
people of one algorithm p+1 size of the permutations that we construct zero p+1.
So, applying that construction it immediately applies
that equation on the generating function.
And that's an easy equation to simplify.
So the first term, if size of p plus one lrm of p,
and that size of p plus one cancels with the size
of p plus one factorial below the z size p plus one.
So that gives us the first sum, lrm of p plus one over p factorial.
And then the second term, the plus one just throws out
a second term with z over p plus one or p plus one factorial.
So that's a simplification.
Now both of those we can evaluate.
The first one if you look up at the first equation is just z b of z.
In the second one if you group by size of the permutation,
just gives z to the k plus one over k factorial.
Z to the k plus one over k plus one,
because there's a k factorial permutations of size k.
And that'll cancel with a k plus one factorial, just leaving a k plus one, and
that generating function is just log of one over one minus z.
So now just solving for
b of z we get b of z = 1 over 1-z, log of 1 over 1-z.
And remember that's the ordinary generating function for
the harmonic number.
And remember our trick for permutations,
if we just extract the coefficient of z to the n in that.
Then we get the B*Zn / N!,
which is our average number of left-right minima and it's just the harmonic number.
A direct derivation of average number of left-right minima
using combinatorial construction.
And it's a good idea to check those against the actual values that
we observed at the beginning.
And sure enough those were the harmonic numbers.
It's also possible to get the generating function equation
through analytic combinatorics, and I'll talk about that in a minute.
But it's worthwhile to think in terms of these direct counting equations.
And we'll worry about the analytic combinatorics in parameters a little bit,
mostly in the second part of the course.
It's worthwhile to get a little bit of experience working with it in this form,
to really have a feeling for the power in generality of a method.
So that's left to right minima.
Now a similar question in terms of parameters on permutations.
Suppose we want to know the number of cycles that are in
a permutation with size N.
And again, if we look at this table.
The number of cycles in each one of the permutation's is written to the left.
And we can go ahead and compute the accumulated costs.
And probably you already recognize that it's the same number.
So now we're going to look at why it's the same number.
So to analyze the average number of cycles in a random permutation
we'll use the same basic approach.
We'll look at a construction that constructs permutations.
Given one permutation construct of size n construct n plus one of size n plus one.
And use that construction to rearrange the terms of the sum and generating function
function to imply a relationship that that generating function has to hold.
So for cycles,
what we're going to do is we have a permutation that's a set of cycles.
We're going to insert, and it's a size n.
We're going to insert n plus one into every position in every cycle,
including the null cycle.
So first thing is, put seven in the null cycle.
So that creates a new cycle of size one, and
then put seven in every position in the one cycle.
There's only one place that makes it two cycle with two and seven in it, and
then in the two cycle.
There's two places to put it, 376 or 367.
And in the three cycle, there's three places to put it.
Either 4715, 4175, or 4517.
So, that permutation of size six.
We construct seven permutations of size seven.
And so now the question is,
how many cycles are there in all of these permutations?
And so, if the number of cycles in the original perm is cycles of p.
Then how many are there in all of these.
Well, they all have the same number of cycles.
Except the case where we added a new cycle by adding to the null cycle.
So, there's p plus one, copies the original perm, and
all of the same number of cycles.
And then, there's one extra for that extra singleton cycle.
So immediately now, you can see
that's exactly the same relationship that we had for left to right minimum.
And so, what that means is the derivation's going to be exactly the same.
So, instead of LRM, I wrote cycles but it's the very same derivation.
We apply the construction and use that to essentially reorder the terms in the sum.
We say the generator function also has to equal that expression.
Then it simplifies in exactly the same way to get down to the harmonic numbers.
Average number of cycles in a random permutation of size N is A sub N.
Now, when we have the same generating function again,
often in combinatorics, when we see that.
What we like to do is find a correspondence,
a one to one correspondence between the number of LRM and the number of cycles.
So it's a reasonable question, is there a one to one correspondence.
This is a famous one, and the answer is yes.
So what you could do, if you have a set of cycles.
You can build a permutation corresponding to that set of cycles.
A unique permutation corresponding to that set of cycles.
By looking at the smallest element in each cycle, call that the leader of the cycle.
So the first one, the four is the leader.
The second one, the one is the leader.
The single cycle there's only one.
The third one, the 14 is the leader.
And the last one, the two is the leader.
So we identify the leader of each cycle.
And then what we'll do is write down the cycles in decreasing order of the leader.
So we pick the largest leader and then write down its cycle,
just by following the cycle.
So in this case, the largest one is 14.
That's where we write 14, 60.
The next largest leader is just the five.
The next one is that first one, where the leader is four.
So we write down four, ten, six, 15.
And then the big one at the end, we write down two, 12, eight, three, 11, 13.
And then the one containing the one is one, seven, nine.
Now we don't write down, we didn't demark
the cycles in any way, but that's a permutation.
And so, I said it was unique and that means we can use a corresponding
process to get the set of cycles corresponding to any permutation.
What’s the set of cycles corresponding to this permutation?
So we’re given the permutation.
What we do is, identify the left to right minima.
Those are the leaders.
Remember we pick the leader as the smallest in the cycle, and
then we wrote them down in decreasing order of the leaders.
So between each leader, say between four and two.
Everybody on the same cycle as four is bigger.
And so, as soon as we get to somebody that's smaller than four,
that's the leader of the next cycle.
So that's how we break up the permutation into cycles and that immediately
shows that the number of left to right minima is equal to the number of cycles.
because this correspondence is one to one, and works for any permutations.
So that's a famous correspondence between left to right minima in cycles.
That so, now we can write down the cycles just by finding the lrm,
and then simply writing the cycles out as before.
So that's a couple examples of parameters and permutations,
left-right minima and number of cycles.
Explora nuestro catálogo
Inscríbete de manera gratuita y obtén recomendaciones personalizadas, actualizaciones y ofertas.
Coursera brinda acceso universal a la mejor educación del mundo, al asociarse con las mejores universidades y organizaciones, para ofrecer cursos en línea.
© 2018 Coursera Inc. Todos los derechos reservados.
