permutation

This article's introduction section may not adequately summarize its contents. To comply with Wikipedia's lead section guidelines, please consider expanding the lead to provide an accessible overview of the article's key points. (September 2009)

In several fields of mathematics the term permutation is used with different but closely related meanings. They all relate to the notion of mapping the elements of a set to other elements of the same set, i.e., exchanging (or "permuting") elements of a set. For example, a permutation of {1,2,3,4} may be {3,2,1,4}, {2,4,1,3}, {3,4,2,1}, or purely {2,1,4}. A permutation is simply an ordered arrangement of the elements of a set.

Definitions

The general concept of permutation can be defined more formally in different contexts:

In combinatorics

In combinatorics, a permutation is usually understood to be a sequence containing each element from a finite set once, and only once. The concept of sequence is distinct from that of a set, in that the elements of a sequence appear in some order: the sequence has a first element (unless it is empty), a second element (unless its length is less than 2), and so on. In contrast, the elements in a set have no order; {1, 2, 3} and {3, 2, 1} are different ways to denote the same set.

However, there is also a traditional more general meaning of the term "permutation" used in combinatorics. In this more general sense, permutations are those sequences in which, as before, each element occurs at most once, but not all elements of the given set need to be used.

For a related notion in which the ordering of the selected elements form a set, for which the ordering is irrelevant, see Combination.

In group theory

In group theory and related areas, the elements of a permutation need not be arranged in a linear order, or indeed in any order at all. Under this refined definition, a permutation is a bijection from a finite set onto itself. This allows for the definition of groups of permutations; see Permutation group.

Counting permutations

In this section only, the traditional definition from combinatorics is used: a permutation is an ordered sequence of elements selected from a given finite set, without repetitions, and not necessarily using all elements of the given set. For example, given the set of letters {C, E, G, I, N, R}, some permutations are ICE, RING, RICE, NICER, REIGN and CRINGE, but also RNCGI – the sequence need not spell out an existing word. ENGINE, on the other hand, is not a permutation, because it uses the elements E and N twice.

If n  denotes the size of the set – the number of elements available for selection – and only permutations are considered that use all n  elements, then the total number of possible permutations is equal to n!, where "!" is the factorial operator. This can be shown informally as follows. In constructing a permutation, there are n  possible choices for the first element of the sequence. Once it has been chosen, n − 1 elements are left, so for the second element there are only n − 1 possible choices. For the first two elements together, that gives us

n × (n − 1) possible permutations.

For selecting the third element, there are then n − 2 elements left, giving, for the first three elements together,

n × (n − 1) × (n − 2) possible permutations.

Continuing in this way until there are only 2 elements left, there are 2 choices, giving for the number of possible permutations consisting of n − 1 elements:

n × (n − 1) × (n − 2) × ... × 2.

The last choice is now forced, as there is exactly one element left. In a formula, this is the number

n × (n − 1) × (n − 2) × ... × 2 × 1

(which is the same as before because the factor 1 does not make a difference). This number is, by definition, the same as n!.

In general the number of permutations is denoted by , , or sometimes , where:

• n  is the number of elements available for selection, and
• r  is the number of elements to be selected (0 ≤ r ≤ n).

For the case where r = n  it has just been shown that P(n, r) = n!. The general case is given by the formula:

As before, this can be shown informally by considering the construction of an arbitrary permutation, but this time stopping when the length r  has been reached. The construction proceeds initially as above, but stops at length r.  The number of possible permutations that has then been reached is:

P(n, r) = n × (n − 1) × (n − 2) × ... × (n − r + 1).

So:

n! = n × (n − 1) × (n − 2) × ... × 2 × 1

     = n × (n − 1) × (n − 2) × ... × (n − r + 1) × (n − r) × ... × 2 × 1

     = P(n, r) × (n − r) × ... × 2 × 1

     = P(n, r) × (n − r)!.

But if n! = P(n, r) × (n − r)!, then P(n, r) = n! / (n − r)!.

For example, if there is a total of 10 elements and we are selecting a sequence of three elements from this set, then the first selection is one from 10 elements, the next one from the remaining 9, and finally from the remaining 8, giving 10 × 9 × 8 = 720. In this case, n = 10 and r = 3. Using the formula to calculate P(10,3),

In the special case where n = r  the formula above simplifies to:

The reason why 0! = 1 is that 0! is an empty product, which always equals 1.

In the example given in the header of this article, with 6 integers {1..6}, this would be: P(6,6) = 6! / (6−6)! = (1×2×3×4×5×6) / 0! = 720 / 1 = 720.

Since it may be impractical to calculate n! if the value of n  is very large, a more efficient algorithm is to calculate:

P(n, r) = n × (n − 1) × (n − 2) × ... × (n − r + 1).

Other, older notations include ⁿP_r, P_n,r, or _nP_r. A common modern notation is (n)_r which is called a falling factorial. However, the same notation is used for the rising factorial (also called Pochhammer symbol)

n(n + 1)(n + 2)⋯(n + r − 1)r.

With the rising factorial notation, the number of permutations is (n − r + 1)_r.

Permutations in group theory

As explained in a previous section, in group theory the term permutation (of a set) is reserved for a bijective map (bijection) from a finite set onto itself. The earlier example, of making permutations out of numbers 1 to 10, would be translated as a map from the set {1, ..., 10} to itself.

More abstractly, a permutation can be considered a filtration (a chain of subsets): the ordering {0,1,2} corresponds to the filtration . From the point of view of the field with one element, an ordering on a set corresponds to a maximal flag (a filtration on a vector space), considering a set to be a vector space over the field with one element; this connects properties of the symmetric group and other Coxeter groups with properties of algebraic groups.

Notation

There are two main notations for such permutations. In relation notation, one can just arrange the "natural" ordering of the elements being permuted on a row, and the new ordering on another row, as follows:

which stands for the permutation s of the set {1,2,3,4,5} defined by s(1)=2, s(2)=5, s(3)=4, s(4)=3, s(5)=1.

If we have a finite set E of n elements, it is by definition in bijection with the set {1,...,n}, where this bijection f corresponds just to numbering the elements. Once they are numbered, we can identify the permutations of the set E with permutations of the set {1,...,n}. (In more mathematical terms, the function that maps a permutation s of E to the permutation f∘s∘f⁻¹ of {1,...,n} is a morphism from the symmetric group of E into that of {1,...,n}, see below.)

Alternatively, we can write the permutation in terms of how the elements change when the permutation is successively applied. This is referred to as the permutation's decomposition in a product of disjoint cycles using cycle notation (last three examples above). It works as follows: starting from one element x, we write the sequence (x s(x) s²(x) ...) until we get back the starting element (at which point we close the parenthesis without writing the starting element for a second time). This is called the cycle associated to x's orbit following s. Then we take an element we did not write yet and do the same thing, until we have considered all elements. Thus the above example can be written as

Each cycle (x₁ x₂ ... x_L) stands for the permutation that maps x_i on x_i+1 (i=1...L−1) and x_L on x₁, and leaves all other elements invariant. L is called the length of the cycle. Since these cycles have by construction disjoint supports (i.e. they act non-trivially on disjoint subsets of E), they do commute (for example, (1 2 5) (3 4) = (3 4)(1 2 5)). The order of the cycles in the (composition) product does not matter, while the order of the elements in each cycles does matter (up to cyclic change; see also cycles and fixed points). The canonical way of representing such cycles is to start by the smallest element of each cycle.

A 1-cycle (cycle of length 1) simply fixes the element contained in it, so it is often not written explicitly. Some authors define a cycle to exclude cycles of length 1.

Cycles of length two are called transpositions; such permutations merely exchange the place of two elements. (Conversely, a matrix transposition is itself an important example of a permutation.)

The set of permutations of a set is often denoted by the factorial sign: X! is the set of permutations of X.

Product and inverse

One can define the product of two permutations as follows. If we have two permutations, P and Q, the action of first performing P and then Q will be the same as performing some single permutation R. The product of P and Q is then defined to be that permutation R. Viewing permutations as bijections, the product of two permutations is thus the same as their composition as functions. There is no universally agreed notation for the product operation between permutations, and depending on the author a formula like PQ may mean either or . Since function composition is associative, so is the product operation on permutations: .

Likewise, since bijections have inverses, so do permutations, and both and are the "identity permutation" (see below) that leaves all positions unchanged. Thus, it can be seen that permutations form a group.

As for any group, there is a group isomorphism on permutation groups, obtained by assigning to each permutation its inverse, and this isomorphism is an involution, giving a dual view on any abstract result. Since , from an abstract point of view it is immaterial whether PQ represents "P before Q" or "P after Q". For concrete permutations, the distinction is, of course, quite material.

Special permutations

If we think of a permutation that "changes" the position of the first element to the first element, the second to the second, and so on, we really have not changed the positions of the elements at all. Because of its action, we describe it as the identity permutation because it acts as an identity function. Conversely, a permutation which changes the position of all elements (no element is mapped to itself) is called a derangement.

If one has some permutation, called P, one may describe a permutation, written P⁻¹, which undoes the action of applying P. In essence, performing P then P⁻¹ is equivalent to performing the identity permutation. One always has such a permutation since a permutation is a bijective map. Such a permutation is called the inverse permutation. It is computed by exchanging each number and the number of the place which it occupies.

An even permutation is a permutation which can be expressed as the product of an even number of transpositions, and the identity permutation is an even permutation as it equals (1 2)(1 2). An odd permutation is a permutation which can be expressed as the product of an odd number of transpositions. It can be shown that every permutation is either odd or even and can't be both.

One theorem regarding the inverse permutation is the effect of a conjugation of a permutation by a permutation in a permutation group. If we have a permutation Q=(i₁ i₂ ... i_n) and a permutation P, then PQP⁻¹ = (P(i₁) P(i₂) ... P(i_n)).

We can also represent a permutation in matrix form; the resulting matrix is known as a permutation matrix.

Properties

Ascents, descents and runs

An ascent in a permutation is any position i where the following value is bigger than the current one. That is, if is a permutation, then any position i with p_i < p_{i + 1} is called an ascent.

For example, the permutation 3452167 has the ascends 1,2,5,6.

Similarly, a descent is a position i with p_i > p_{i + 1}.

The number of permutations with a given number of ascents or descents is equal to the Eulerian number A(n,k), where n is the number of elements of the permutation and k is the given number of ascents or descents.^[1]

An ascending run of a permutation is a subsequence of the permutation in which the values raise from position to position.

For example, the permutation 3452167 has the ascending runs 345,2,167.

If a permutation has k − 1 descents, then it must be the union of k ascending runs. Hence, the number of permutations with k ascending runs is the same as the number of permutations with k − 1 descents.^[2]

Inversions

An inversion is a pair of entries of a permutation which appear in ascending order, even though the entry that appears first is greater than the entry that appears second.^[3]

For example, the permutation 23154 has three inversions: (2,1),(3,1),(5,4).

The number of permutations with k inversions is expressed by Mahonian numbers^[4]

Relationship to the combination formula

The formula for computing permutations and combinations differ only by a factor of r!

The logic behind this is that C(n, r) gives us the number of ways to chose r out of n people. Once we have chosen r people, we can arrange them in r! ways. P(n,r) gives us the number of ways to arrange r out of n people. Thus,

In computing

Some of the older textbooks look at permutations as assignments, as mentioned above. In computer science terms, these are assignment operations, with values

1, 2, ..., n

assigned to variables

x₁, x₂, ..., x_n.

Each value should be assigned only once.

The assignment/substitution difference is then illustrative of one way in which functional programming and imperative programming differ; pure functional programming has no assignment mechanism. The mathematics convention is nowadays that permutations are just functions and the operation on them is function composition; functional programmers follow this. In the assignment language a substitution is an instruction to switch round the values assigned, simultaneously; a well-known problem.

Numbering permutations

Factoradic numbers can be used to assign unique numbers to permutations, such that given a factoradic of k one can quickly find the corresponding permutation.

Algorithms to generate permutations

Unordered generation

For every number k, with 0 ≤ k < n!, the following algorithm generates a unique permutation of the initial sequence s_j, j = 1, ..., n:

 function permutation(k, s) {
     for j = 2 to length(s) {
        swap s[(k mod j) + 1] with s[j]; // note that our array is indexed starting at 1
        k := k / j;        // integer division cuts off the remainder
     }
     return s;
 }

The formula k mod j returns the least significant digit of k in the factorial base and k := k / j removes that digit, shifting the remaining digits to the right. The first line of the for loop, at each step, swaps the jth element with one of the elements that are currently before it. If we consider the swaps in reverse order, we see that it implements a backwards selection sort, first putting the nth element in the correct place, then the (n − 1)th, etc. Since there is exactly one way to selection sort a permutation, this algorithm generates a unique permutation for each choice of k.

The Fisher–Yates shuffle is based on the same principle as this algorithm.

Lexicographical order generation

For every number k, with 0 ≤ k < n!, the following algorithm generates the corresponding lexicographical permutation of the initial sequence s_j, j = 1, ..., n:

 function permutation(k, s) {
     var int n:= length(s); factorial:= 1;
     for j= 2 to n- 1 {             // compute (n- 1)!
         factorial:= factorial* j;
     }
     for j= 1 to n- 1 {
         tempj:= (k/ factorial) mod (n+ 1- j); // (1)
         temps:= s[j+ tempj]
         for i= j+ tempj to j+ 1 step -1 {
             s[i]:= s[i- 1];      // shift the chain right
         }
         s[j]:= temps;
         factorial:= factorial/ (n- j);
     }
     return s;
 }

Notation

• k / j denotes integer division of k by j, i.e. the integral quotient without any remainder, and
• k mod j is the remainder following integer division of k by j.
• s[n] denotes the nth element of sequence s.

At statement (1), we find out the index which we need to shift to the jth position. For example, let us consider a string "abcde". Suppose we want the 74th permutation. First, consider 4 of the 5 characters which make up the string. There are 4! permutations possible using these 4 characters. What we now want to do, is find out which character which leads the permutation (ie is it's first character). We know that there are 24 permutations starting with a, 24 with b, 24 with c and so on. So, the 74th permutation must definitely start with a d. (since 72 of them already start with a ,b and c). So, shift this character to the 1st position. Now, the string is "dabce". Now we must consider permutations with 3 characters. Since 72 permutations (24 * 3) permutations have been accounted for, we must now find out the 2nd (74 mod 72) permutation of the string "abce". Again, following the same logic as above, we know that there are 6 permutations starting with a. Since we need just the 2nd permutation, we can stop here. The string is now "dabce". Now, consider the permutations with 2 characters. We know that 2! of these start with a b. Since we need the 2nd permutation, it must definitely have a b in the 3rd position. Finally, we look at permutations with 1 character. One of it starts with a c and the other starts with an e. Clearly, we need the latter, because we need the 74th permutation. So shift the e to the 4th position in the string. Therefore, the 74th permutation is "dabec".

A Java implementation:

static public<E> E[] permutation(E[] s, int num) {
       // s is the input elements array and num
       // is the number which represents the permutation
 
	int factorial = 1;
	for(int i = 2; i < s.length; i++)
		factorial *= i; // calculates the factorial of (s.length - 1)
 
	if (num/s.length >= factorial) // Optional. if the number is not in the
                                     // range of [0, s.length! - 1]
		return null;
 
	for(int i = 0; i < s.length - 1; i++){//go over the array
 
               // calculates the next cell from the cells left
               // (the cells in the range [i, s.length - 1])
		int tempi = (num / factorial) % (s.length - i);
 
               // Temporarily saves the value of the cell needed
               // to add to the permutation this time
		E temp = s[i + tempi];
 
               // shift all elements to "cover" the "missing" cell
		for(int j = i + tempi; j > i; j--)
			s[j] = s[j-1];
 
		s[i] = temp; // put the chosen cell in the correct spot
 
		factorial /= (s.length - (i + 1)); // updates the factorial
 
	}
 
	return s;
}

An Actionscript implementation:

function permutation(n:Number, k:Number):Array {
	var r:Array = [], j:Number = 1, i:Number, p:Number;
	r[n-1] = 0;
	while(j++<n){
		p = i = n-j;
		r[p] = Math.floor((k/=(j-1))%j);
		while(i++<n)
			if(r[i] >= r[p])
				++r[i];
	}
	return r;
}

The following algorithm generates the next permutation lexicographically after a given permutation. It changes the given permutation in-place.

1. Find the highest index i such that s[i] < s[i+1]. If no such index exists, the permutation is the last permutation.
2. Find the highest index j > i such that s[j] > s[i]. Such a j must exist, since i+1 is such an index.
3. Swap s[i] with s[j].
4. Reverse all the order of all of the elements after index i

After we've found i, we know that all of the elements after i are a strictly decreasing sequence (otherwise we would have chosen a larger i). Thus, if we consider the permutations of just the elements after index i, they are in their last permutation with respect to each other. The next permutation lexicographically of all of the elements, then, can be found by replacing i with the next smallest number greater than the number at index i, and sorting the remaining numbers in increasing order (the first permutation of just those numbers). The next smallest number greater than the value at index i is at index j, since again all of the numbers after index i are in decreasing order. We can then sort the remaining numbers by reversing them.

Encoding and decoding

One can map every possible permutation state of a given set of size n to a unique factoradic integer k , where k ranges from 1 to n! . Iterating the previous or next permutation becomes a trivial add or subtract one. One can also compactly store this permutation state, compared to storing the permutation itself (as we only need to store Ceiling(Log(n!) / Log(2)) bits compared to n*Ceiling(Log(n) / Log(2)) bits.)

i.e. Given a size of 3, iterating all possible values for k gives the following permutations:

1. ABC
2. ACB
3. BAC
4. BCA
5. CAB
6. CBA

i.e. One could represent a deck of cards using to Log(52!)/Log(2) = 226 bits compared to the standard 6-bits per card * 52 cards = 312 bits.

The question becomes:

1. how does one encode the permutation state into a unique value k, and
2. how does one decode a specific value k into the permutation state.

Encoding and Decoding a given sequence to the unique integer is a variation on Variable Bit Decoding, where the base changes size every iteration. The following sample code demonstrates the beautiful symmetry between Permutations (Variable Bit Decoding) and Combinations (Constant Bit Decoding)

void String_Reverse( char *pSrc, int nLen )
{
    if( nLen > 1 ) {
        char *pMid = pSrc + (nLen >> 1); // floor(nLen/2)
        char *pDst = pSrc + nLen - 1;
        char  nTmp;
        while( pSrc < pMid ) {
             nTmp   = *pSrc; // t <- s
            *pSrc++ = *pDst; //      s <- d
            *pDst-- =  nTmp; //           d <- t
        }
    }
}
 
// Also known as: itoa() !
void Constant_Bit_Decoding( int n, char * const pOutput_, const int nBase )
{
    int  d, r;
    char aDigits[] = "0123456789ABCDEF";
    int  nDigits = 0; // variable length output!
    char *pDst = pOutput_;
 
    if( nBase > 0 )
        do
        {
            d = n / nBase; // nBase = constant
            r = n % nBase; // nBase = constant
            n /= nBase;
            *pDst++ = aDigits [ r ];
 
            // Combinatation: re-use all elements
            nDigits++;
        } while( n > 0 ); // combination: n > 0
 
    // combination: reverse string
    String_Reverse( pOutput_, nDigits );
    *pDst = 0;
}
 
// Unpack Permutation Enumeration
// See: "Procedures of encoding and decoding of permutations"
void Variable_Bit_Decoding( int n, char * const pOutput_, int nBase )
{
    int  d, r;
    char aDigits[] = "0123456789ABCDEF";
    int  nDigits = nBase; // constant length output!
    char *pDst = pOutput_;
 
    if( nBase > 0 )
        do
        {
            d = n / nBase; // nBase = variable
            r = n % nBase; // nBase = variable
            n /= nBase;
            *pDst++ = aDigits[ r ];
 
            // Permutation: Remove 'r'th element
            int nDigits = nBase - r - 1;
            if( nDigits > 0 ) {
                memcpy( aDigits + r, aDigits + r + 1, nDigits );
            }
            nBase--;
        } while( nBase > 0 ); // permutation: nbase > 0
    // permutation: nothing to do
    *pDst = 0;
}
 
int main(int nArg, char* aArg[] )
{
    int nBase = 3;
    int nMax = 6; // nBase!
    char aBuffer[ 32 ];
 
    // print off all combinations of [0 ...nMax] in base nBase
    printf("Combinations:\n#    Base %d\n", nBase );
    for( int iEncoded = 0; iEncoded < nMax; iEncoded++ ) {
        Constant_Bit_Decoding( iEncoded, aBuffer, nBase );
        printf( "%d -> %s\n", iEncoded, aBuffer );
    }
    printf("\n");
 
    // print off all permutations of nBase!
    printf("Permutations:\n#    Enumerate %d!\n", nBase );
    for( int iEncoded = 0; iEncoded < nMax; iEncoded++ ) {
        Variable_Bit_Decoding( iEncoded, aBuffer, nBase );
        printf( "%d -> %s\n", iEncoded, aBuffer );
    }
    printf("\n");
 
    return 0;
}

Software and hardware implementations

Calculator functions

Most calculators have a built-in function for calculating the number of permutations, called nPr or PERM on many. The permutations function is often only available through several layers of menus; how to access the function is usually indicated in the documentation for calculators that support it.

Spreadsheet functions

Most spreadsheet software also provides a built-in function for calculating the number of permutations, called PERMUT in many popular spreadsheets. Apple's Numbers '08 software notably did not include such a function^[5] but this was rectified in Apple's Numbers '09 software package.

Applications

Permutations are used in the interleaver component of the error detection and correction algorithms, such as turbo codes, for example 3GPP Long Term Evolution mobile telecommunication standard uses these ideas (see 3GPP technical specification 36.212 ^[6]). Such applications rise the question of fast generation of permutation satisfying certain good properties. One of the methods is based on the permutation polynomials.

See also

Mathematics portal

Notes

References

• Miklos Bona. "Combinatorics of Permutations", Chapman Hall-CRC, 2004. ISBN 1-58488-434-7.
• Donald Knuth. The Art of Computer Programming, Volume 4: Generating All Tuples and Permutations, Fascicle 2, first printing. Addison-Wesley, 2005. ISBN 0-201-85393-0.
• Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Second Edition. Addison-Wesley, 1998. ISBN 0-201-89685-0. Section 5.1: Combinatorial Properties of Permutations, pp. 11–72.

External links

• Many Common types of permutation and combination math problems, with detailed solutions