O'Reilly logo

An Introduction to the Analysis of Algorithms, Second Edition by Philippe Flajolet, Robert Sedgewick

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Chapter Seven. Permutations

Combinatorial algorithms often deal only with the relative order of a sequence of N elements; thus we can view them as operating on the numbers 1 through N in some order. Such an ordering is called a permutation, a familiar combinatorial object with a wealth of interesting properties. We have already encountered permutations: in Chapter 1, where we discussed the analysis of two important comparison-based sorting algorithms using random permutations as an input model; and in Chapter 5, where they played a fundamental role when we introduced the symbolic method for labelled objects. In this chapter, we survey combinatorial properties of permutations and use probability, cumulative, and bivariate generating functions ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required