HGPA

Permutations

Introduction

A permutation is a particular ordering of a set of objects. Formally, a permutation of a finite set S is an ordered sequence all the elements with each one appearing once.

How many different ways can you order {1,2,3}?

Answer -- 6:

For a set of length n, there are n! permutations. So 3! = 6.

Why is this?

(n)(n-1)(n-2)...(2)(1) is the definition of factorial of n.

We can also talk about the k-permutation of a set: P(n,r) , or nPr = n!/(n-r)!

Generating Permutations

Since O(permutations) is n! we have something that won't run in our lifetime for any decent size n...

Many algorithms seek the best way to order a set of objects:

The lexiographic order of the permutations of {1,2,3} are:

REFERENCES

Permutations. Sal Khan. Kahn Academy.

The Algorithm Design Manual. Second Addition. Steven Skiena. 2008.

Filename: permutations.md (Edit)
Modified: 2016-12-12 (3029e2687e2e0759b246973c668b1845ea24e7df)
Created: 2016-12-12 (3029e2687e2e0759b246973c668b1845ea24e7df)