Permutation

For other uses, see Permutation (disambiguation).

In mathematics, the notion of permutation is used with several slightly different meanings, all related to the act of permuting, that is rearranging, a number of objects or values. In algebra and in particular in group theory, a permutation of a set S is a bijective map from S to itself; the associated rearrangement of S is the one in which each element takes the place of its image under the bijection. In combinatorics a permutation of a finite set S is any ordering of its elements in a list; in this sense the permutations of S differ precisely by rearrangement of the elements in the list. When S is given with an initial ordering, such as S={1,2,3,...,n}, these two meanings can be almost identified, since applying a permutation in the first sense to this initial ordering gives an alternative ordering of the elements, a permutation in the second sense. Thus the permutations of {1,2,3} are [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1]. The term permutation is also used less formally to designate the act of rearranging parts of an object, or the result thereof; one might define an anagram of a word as a permutation of its letters, or say that X³Y+7+Y²Z is (obtained by) a permutation of the terms of the polynomial X³Y+Y²Z+7. The act of permuting can also refer to substitution of symbols, for instance when saying that Y³Z+Z²X+7 is obtained from the mentioned polynomial by a (cyclic) permutation of the variables X, Y, Z. These statements can be given a precise meaning by considering an appropriate symmetric group action.

In combinatorics the second sense of "permutation" is sometimes broadened. In elementary combinatorics, the name "permutations and combinations" refers to two related problems, both counting possibilities to select k distinct elements from a set of n elements, where for k-permutations the order of selection is taken into account, but for k-combinations it is ignored. In fact counting k-permutations is used as a step towards counting the number ${\tbinom {n}{k}}$ of k-combinations, and also towards computing the number n! of permutations of the set in either of the two meanings mentioned above. However k-permutations do not correspond to such permutations unless k = n, that is, unless the selection involves all available elements. In a different broadening of the notion of permutation, one can start, rather than with a set S, with a finite multiset M in which some values may occur more than once. A (multiset) permutation of M is a sequence of elements of M in which each of them occurs exactly as often as it occurs in M. Thus for M=[1,1,1,2,3,3], the sequence [3,1,2,1,1,3] is a multiset permutation of M, but [3,1,2,1,2,3,1] is not.

Permutations occur, in more or less prominent ways, in almost any domain of mathematics. They often arise when different orderings on certain finite sets are considered, possibly only because one wants to ignore such orderings and needs to know how many configurations are thus identified. For similar reasons permutations arise in the study of sorting algorithms in computer science. In algebra, an entire subject is dedicated to the detailed study of permutations, through the notion of symmetric group. The key to its structure is the possibility to compose permutations: by performing two given rearrangements in succession, the combination defines a third rearrangement.

The rule to determine the number of permutations of n objects was known in Hindu culture at least as early as around 1150: the Lilivati by the Indian mathematician Bhaskara contains a passage that translates to

The product of multiplication of the arithmetical series beginning and increasing by unity and continued to the number of places, will be the variations of number with specific figures.

A first case where at first sight unrelated mathematical questions are studied with the help of permutations occurs around 1770, when Joseph Louis Lagrange, in the study of polynomial equations, observed that properties of the permutations of the roots of an equation are related to the possibilities to solve it. The development that came forth from this work ultimately resulted, through the work of Évariste Galois, in Galois theory, which gives a complete description of what is possible and impossible with respect to solving polynomial equations (in one unknown) by radicals. In modern mathematics there are many similar situations, where understanding a problem requires studying certain permutations related to it.

Generalities

The notion of permutation is used in the following contexts.

In group theory

In group theory and related areas, one considers permutations of arbitrary sets, even infinite ones. A permutation of a set S is a bijection from S to itself. This allows for permutations to be composed, which allows the definition of groups of permutations. If S is a finite set of n elements, then there are n! permutations of S.

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. In this sense a permutation of a finite set S of n elements is equivalent to a bijection from {1, 2, ... , n} to S (in which any i is mapped to the i-th element of the sequence), or to a choice of a total ordering on S (for which x<y if x comes before y in the sequence). In this sense there are also n! permutations of S.

There is also a weaker meaning of the term "permutation" that is sometimes used in elementary combinatorics texts, designating those sequences in which no element occurs more than once, but without the requirement to use all elements from a given set. Indeed this use often involves considering sequences of a fixed length k of elements taken from a given set of size $n>k$. These objects are also known as sequences without repetition, a term that avoids confusion with the other, more common, meanings of "permutation". The number of length k sequences without repetition of elements of a set of size n is

$n^{\underline {k}}=n\cdot (n-1)\cdot (n-2)\cdots (n-k+1)$,

a number known as the k-th falling factorial power of n, and for which many other names and notations are in use.

If M is a finite multiset, then a multiset permutation is a sequence of elements of M in which each element appears exactly as often as is its multiplicity in M. If the multiplicities of the elements of M (taken in some order) are $m_{1}$, $m_{2}$, ..., $m_{l}$ and their sum (i.e., the size of M) is n, then the number of multiset permutations of M is given by the multinomial coefficient

${n \choose m_{1},m_{2},\ldots ,m_{l}}={\frac {n!}{m_{1}!\,m_{2}!\,\cdots \,m_{l}!}}$.

Permutations in group theory

Main article: Symmetric group

In group theory, the term permutation of a set means a bijective map, or bijection, from that set onto itself. The set of all permutations of any given set S forms a group, with composition of maps as product and the identity as neutral element. This is the symmetric group of S. Up to isomorphism, this symmetric group only depends on the cardinality of the set, so the nature of elements of S is irrelevant for the structure of the group. Symmetric groups have been studied most in the case of a finite sets, in which case one can therefore assume that S={1,2,...,n} for some natural number n, which defines the symmetric group of degree n. Any subgroup of a symmetric group is called a permutation group. In fact by Cayley's theorem any group is isomorphic to a permutation group, and every finite group to a subgroup of a finite symmetric group. However, permutation groups have more structure than abstract groups, and different realizations of a group as a permutation group therefore need not be equivalent.

Notation

There are two main notations for permutations of a finite set S. In two-line notation, one lists the elements of S in the first row, and for each one its image under the permutation below it in the second row. For instance a particular permutation of the set {1,2,3,4,5} can be written as:

$\sigma ={\begin{pmatrix}1&2&3&4&5\\2&5&4&3&1\end{pmatrix}}$;

this means that σ satisfies σ(1)=2, σ(2)=5, σ(3)=4, σ(4)=3, and σ(5)=1.

Alternatively, we can write the permutation using cycle notation, which focuses on the effect of successively applying the permutation. It expresses the permutation as a product of cycles corresponding to the orbits (with at least two elements) of the permutation; since distinct orbits are disjoint, this is loosely referred to as "the decomposition into disjoint cycles of the permutation. It works as follows: starting from some element x of S with σ(x) ≠ x, one writes the sequence (x σ(x) σ(σ(x)) ...) of successive images under σ, until the image would be x, at which point one instead closes the parenthesis. The set of values written down forms the orbit (under σ) of x, and the parenthesized expression gives the corresponding cycle of σ. One then continues choosing an element x of S that is not in the orbit already written down, and such that σ(y) ≠ y, and writes down the corresponding cycle, and so on until all elements of S either belong to a a cycle written down or are fixed points of σ. Since for every new cycle the starting point can be chosen in different ways, there are in general many different cycle notations for the same permutation; for the example above one has for instance

${\begin{pmatrix}1&2&3&4&5\\2&5&4&3&1\end{pmatrix}}={\begin{pmatrix}1&2&5\end{pmatrix}}{\begin{pmatrix}3&4\end{pmatrix}}={\begin{pmatrix}3&4\end{pmatrix}}{\begin{pmatrix}1&2&5\end{pmatrix}}={\begin{pmatrix}3&4\end{pmatrix}}{\begin{pmatrix}5&1&2\end{pmatrix}}.$

Each cycle (x₁ x₂ ... x_l) of σ denotes a permutation in its own right, namely the one that takes the same values as σ on this orbit (so it maps x_i to x_i+1 for i < l, and x_l to x₁), while mapping all other elements of S to themselves. The size l of the orbit is called the length of the cycle. Distinct orbits of σ are by definition disjoint, so the corresponding cycles are easily seen to commute, and σ is the product of its cycles (taken in any order). Therefore the concatenation of cycles in the cycle notation can be interpreted as denoting composition of permutations, whence the name "decomposition" of the permutation. This decomposition is essentially unique: apart from the reordering the cycles in the product, there are no other ways to write σ as a product of cycles (possibly unrelated to the cycles of σ) that have disjoint orbits. The cycle notation is less unique, since each individual cycle can be written in different ways, as in the example above where (5 1 2) denotes the same cycle as (1 2 5) (but (5 2 1) would denote a different permutation).

An orbit of size 1 (a fixed point x in S) has no corresponding cycle, since that permutation would fix x as well as every other element of S, in other words it would be the identity, independently of x. It is possible to include (x) in the cycle notation for σ to stress that σ fixes x (and this is even standard in combinatorics, as described in cycles and fixed points), but this does not correspond to a factor in the (group theoretic) decomposition of σ. If the notion of "cycle" were taken to include the identity permutation, then this would spoil the uniqueness (up to order) of the decomposition of a permutation into disjoint cycles. The decomposition into disjoint cycles of the identity permutation is an empty product; its cycle notation would be empty, so some other notation like e is usually used instead.

Cycles of length two are called transpositions; such permutations merely exchange the place of two elements.

Product and inverse

Main article: Symmetric group

The product of two permutations is defined as their composition as functions, in other words σ·π is the function that maps any element x of the set to σ(π(x)). Note that the rightmost permutation is applied to the argument first, because of the way function application is written. Some authors prefer the leftmost factor acting first, but to that end permutations must be written to the right of their argument, for instance as an exponent, where σ acting on x is written x^σ; then the product is defined by x^σ·π=(x^σ)^π. However this gives a different rule for multiplying permutations; this article uses the definition where the rightmost permutation is applied first.

Since the composition of two bijections always gives another bijection, the product of two permutations is again a permutation. Since function composition is associative, so is the product operation on permutations: (σ·π)·ρ=σ·(π·ρ). Therefore, products of permutations are usually written without parentheses; they are also usually written without a dot or other sign to mark the product

The identity permutation, which maps every element of the set to itself, is the neutral element for this product. In two-line notation, the identity is

${\begin{pmatrix}1&2&3&\cdots &n\\1&2&3&\cdots &n\end{pmatrix}}$.

Since bijections have inverses, so do permutations, and the inverse σ⁻¹ of σ is again a permutation. Explicitly, whenever σ(x)=y one also has σ⁻¹(y)=x. In two-line notation the inverse can be obtained by interchanging the two lines (and sorting the columns if one wishes the first line to be in a given order). For instance

${\begin{pmatrix}1&2&3&4&5\\2&5&4&3&1\end{pmatrix}}^{-1}={\begin{pmatrix}2&5&4&3&1\\1&2&3&4&5\end{pmatrix}}={\begin{pmatrix}1&2&3&4&5\\5&1&4&3&2\end{pmatrix}}$

In cycle notation one can reverse the order of the elements in each cycle to obtain a cycle notation for its inverse.

Having an associative product, a neutral element, and inverses for all its elements, makes the set of all permutations of S into a group, called the symmetric group of S.

Every permutation of a finite set can be expressed as the product of transpositions. Moreover, although many such expressions for a given permutation may exist, there can never be among them both expressions with an even number and expressions with an odd number of transpositions. All permutations are then classified as even or odd, according to the parity of the transpositions in any such expression.

Multiplying permutations written in cycle notation follows no easily described pattern, and the cycles of the product can be entirely different from those of the permutations being composed. However the cycle structure is preserved in the special case of conjugating a permutation σ by another permutation π, which means forming the product π·σ·π⁻¹. Here the cycle notation of the result can be obtained by taking the cycle notation for σ and applying π to all the entries in it.

One can represent a permutation of {1, 2, ..., n} as an n×n matrix. In order that multiplications of matrices correspond to multiplication of permutations, one must associate to σ the matrix M whose entry M_i,j is 1 if i=σ(j), and 0 otherwise. The resulting matrix has exactly one entry 1 in each column and in each row, and such a matrix is called a permutation matrix.

Permutations in combinatorics

In combinatorics a permutation of a set S with n elements is a listing of the elements of S in some order (each element occurring exactly once). This can be defined formally as a bijection from the set { 1, 2, ..., n } to S. Note that if S equals { 1, 2, ..., n }, then this definition coincides with the definition in group theory. More generally one could use instead of { 1, 2, ..., n } any set equipped with a total ordering of its elements.

One combinatorial property that is related to the group theoretic interpretation of permutations, and can be defined without using a total ordering of S, is the cycle structure of a permutation σ. It is the partition of n describing the lengths of the cycles of σ. Here there is a part "1" in the partition for every fixed point of σ. A permutation that has no fixed point is called a derangement.

Other combinatorial properties however are directly related to the ordering of S, and to the way the permutation relates to it. Here are a number of such properties.

Ascents, descents and runs

An ascent of a permutation σ of n is any position i < n where the following value is bigger than the current one. That is, if σ = σ₁σ₂...σ_n, then i is an ascent if σ_i < σ_i+1.

For example, the permutation 3452167 has ascents (at positions) 1,2,5,6.

Similarly, a descent is a position i < n with σ_i > σ_i+1, so every i with $1\leq i<n$ either is an ascent or is a descent of σ.

The number of permutations of n with k ascents is the Eulerian number $\textstyle \left\langle {n \atop k}\right\rangle$; this is also the number of permutations of n with k descents.

An ascending run of a permutation is a nonempty increasing contiguous subsequence of the permutation that cannot be extended at either end; it corresponds to a maximal sequence of successive ascents (the latter may be empty: between two successive descents there is still an ascending run of length 1). By contrast an increasing subsequence of a permutation is not necessarily contiguous: it is an increasing sequence of elements obtained from the permutation by omitting the values at some positions. For example, the permutation 2453167 has the ascending runs 245, 3, and 167, while it has an increasing subsequence 2367.

If a permutation has k − 1 descents, then it must be the union of k ascending runs. Hence, the number of permutations of n with k ascending runs is the same as the number $\textstyle \left\langle {n \atop k-1}\right\rangle$ of permutations with k − 1 descents.

Inversions

An inversion of a permutation σ is a pair (i,j) of positions where the entries of a permutation are in the opposite order: $i<j$ and $\sigma _{i}>\sigma _{j}$. So a descent is just an inversion at two adjacent positions. For example, the permutation σ = 23154 has three inversions: (1,3), (2,3), (4,5), for the pairs of entries (2,1), (3,1), (5,4).

Sometimes an inversion is defined as the pair of values (σ_i,σ_j) itself whose order is reversed; this makes no difference for the number of inversions, and this pair (reversed) is also an inversion in the above sense for the inverse permutation σ^-1. The number of inversions is an important measure for the degree to which the entries of a permutation are out of order; it is the same for σ and for σ^-1. To bring a permutation with k inversions into order (i.e., transform it into the identity permutation), by successively applying (right-multiplication by) adjacent transpositions, is always possible and requires a sequence of k such operations. Moreover any reasonable choice for the adjacent transpositions will work: it suffices to choose at each step a transposition of i and i + 1 where i is a descent of the permutation as modified so far (so that the transposition will remove this particular descent, although it might create other descents). This is so because applying such a transposition reduces the number of inversions by 1; also note that as long as this number is not zero, the permutation is not the identity, so it has at least one descent. Bubble sort and insertion sort can be interpreted as particular instances of this procedure to put a sequence into order. Incidentally this procedure proves that any permutation σ can be written as a product of adjacent transpositions; for this one may simply reverse any sequence of such transpositions that transforms σ into the identity. In fact, by enumerating all sequences of adjacent transpositions that would transform σ into the identity, one obtains (after reversal) a complete list of all expressions of minimal length writing σ as a product of adjacent transpositions.

The number of permutations of n with k inversions is expressed by a Mahonian number, it is the coefficient of X^k in the expansion of the product

$\prod _{m=1}^{n}\sum _{i=0}^{m-1}X^{i}=1(1+X)(1+X+X^{2})\cdots (1+X+X^{2}+\cdots +X^{n-1})$,

which is also known (with q substituted for X) as the q-factorial [n]_q! .

Counting sequences without repetition

In this section, a k-permutation of a set S is an ordered sequence of k distinct elements of S. For example, given the set of letters {C, E, G, I, N, R}, the sequence ICE is a 3-permutation, RING and RICE are 4-permutations, NICER and REIGN are 5-permutations, and CRINGE is a 6-permutation; since the latter uses all letters, it is a permutation of the given set in the ordinary combinatorial sense. ENGINE on the other hand is not a permutation, because of the repetitions: it uses the elements E and N twice.

Let n be the size of S, the number of elements available for selection. In constructing a k-permutation, there are n  possible choices for the first element of the sequence, and this is then number of 1-permutations. Once it has been chosen, there are n − 1 elements of S left to choose from, so a second element can be chosen in n − 1 ways, giving a total n × (n − 1) possible 2-permutations. For each successive element of the sequence, the number of possibilities decreases by  which leads to the number of

n × (n − 1) × (n − 2) ... × (n − k + 1) possible k-permutations.

This gives in particular the number of n-permutations (which contain all elements of S once, and are therefore simply permutations of S):

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

a number that occurs so frequently in mathematics that it is given a compact notation "n!", and is called "n factorial". These n-permutations are the longest sequences without repetition of elements of S, which is reflected by the fact that the above formula for the number of k-permutations gives zero whenever k > n.

The number of k-permutations of a set of n elements is sometimes denoted by P(n,k) or a similar notation (usually accompanied by a notation for the number of k-combinations of a set of n elements in which the "P" is replaced by "C"). That notation is rarely used in other contexts than that of counting k-permutations, but the expression for the number does arise in many other situations. Being a product of k factors starting at n and decreasing by unit steps, it is called the k-th falling factorial power of n:

$n^{\underline {k}}=n\times (n-1)\times (n-2)\times \cdots \times (n-k+1)$,

though many other names and notations are in use, as detailed at Pochhammer symbol. When k ≤ n the factorial power can be completed by additional factors: n^k × (n − k)! = n!, which allows writing

$n^{\underline {k}}={\frac {n!}{(n-k)!}}$.

The right hand side is often given as expression for then number of k-permutations, but its main merit is using the compact factorial notation. Expressing a product of k factors as a quotient of potentially much larger products, where all factors in the denominator are also explicitly present in the numerator is not particularly efficient; as a method of computation there is the additional danger of overflow or rounding errors. It should also be noted that the expression is undefined when k > n, whereas in those cases the number n^k of k-permutations is just 0.

Permutations in computing

Some of the older textbooks look at permutations as assignments. 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.

Numbering permutations

Factoradic representation of integers can be used to provide a natural numbering of permutations. It is a mixed radix representation, where for numbers less than n! the bases for successive digits are n, n − 1, ..., 2, 1; thus each number leads to a sequence d_n, d_n−1, ..., d₂, d₁ of "digits", where d_i is a non-negative integer less than i. These digits can be used for making the choices of the terms of the sequence forming the permutation σ: the n possible values of d_n allow choosing the first term σ₁, the n − 1 possible values of d_n−1 allow choosing the second term σ₁ among the remaining n − 1 elements of the set, and so forth. More precisely, each d_n+1−i gives the number of remaining elements strictly less than the term σ_i. Since those remaining elements are bound to turn up as some later term σ_j, the digit d_n+1−i counts the inversions (i,j) involving i as smaller index (the number of values j for which i < j and σ_i > σ_j).

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;
}

Algorithms to generate permutations

Unordered generation

For every number $k$, with $0\leq k<n!$, where $n!$ is the factorial of $n$, the following algorithm generates a unique permutation of the initial sequence $s_{j}$, $j=1,2,3,...,n$:

 function permutation(s, k) {
     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.

A Python implementation:

  def permutation(s, k):
    for j in range(1, len(s)):
      i = k % (j + 1)
      s[i], s[j] = s[j], s[i]
      k = k / (j + 1)

Lexicographical order generation

For every number $k$, with $0\leq k<n!$, the following pseudocode algorithm generates the corresponding lexicographical permutation of the initial sequence $s_{j}$, $j=1,2,3,...,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! (24) permutations possible using these 4 characters. What we now want to do, is find out which character leads the permutation (ie is its 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.

Software implementations

Calculator functions

Many scientific 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 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 ). 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

• Alternating permutation
• Binomial coefficient
• Combination
• Combinatorics
• Convolution
• Cyclic order
• Cyclic permutation
• Even and odd permutations
• Factoradic
• Superpattern
• Josephus permutation
• List of permutation topics
• Levi-Civita symbol
• Permutation group
• Probability
• Random permutation
• Rencontres numbers
• Sorting network
• Substitution cipher
• Symmetric group
• Twelvefold way
• Weak order of permutations
• Permutation polynomial

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
• An algorithm to list all the permutations