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
element 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
demonstrated informally as follows. In constructing a permutation,
there are
n possible choices for the first element
of the sequence. Once it has been chosen, elements are left, so for
the second element there are only possible choices. For the first
two elements together, that gives us
- n × (n − 1) possible permutations.
For selecting the third element, there are then 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 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
\mathbf{p}(n,r), _n\mathbf{P}_r, or sometimes \mathbf{P}_r^n,
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 it has just been shown that . The general
case is given by the formula:
- P(n, r) = \frac{n!}{(n-r)!}.
As before, this can be demonstrated 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 .
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 . In this
case,
n = 10 and
r = 3. Using the formula to
calculate
P(10,3),
- P(10,3) = \frac{10!}{(10-3)!} = \frac{10!}{7!} = \frac{7!\times
8 \times 9 \times 10}{7!} = 8 \times 9 \times 10 = 720.
In the special case where
n =
r the formula
above simplifies to:
- P(n,r) = \frac{n!}{0!} = \frac{n!}{1} = n!.
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
^{n}P_{r},
P_{n,r}, or
_{n}P_{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 \{0\} \subset
\{0,1\} \subset \{0,1,2\}. 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:
- \begin{pmatrix}
1 & 2 & 3 & 4 & 5 \\2 & 5 & 4 & 3 &
1\end{pmatrix}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^{−1}
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 cycle using
cycle notation (last three examples
above). It works as follows: starting from one element
x,
we write the sequence (
x s(
x)
s^{2}(
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
\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_{1} x_{2} ...
x_{L}) stands for the permutation that
maps
x_{i} on
x_{i+1} (
i=1...
L−1) and
x_{L} on
x_{1}, and
leaves all other elements invariant.
L is called the length
of the cycle. Since these cycles have by construction
disjoint support (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 P \circ Q or Q \circ P. Since function composition is
associative, so is the product operation
on permutations: (P \circ Q) \circ R = P \circ ( Q \circ R).
Likewise, since
bijections have
inverses, so do permutations, and both P
\circ P^{-1} and P^{-1} \circ P 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 (P \circ Q)^{-1}= Q^{-1} \circ P^{-1}, 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^{−1}, which undoes the
action of applying
P. In essence, performing
P
then
P^{−1} 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_{1}
i_{2} ...
i_{n}) and a
permutation
P, then
PQP^{−1} =
(
P(
i_{1})
P(
i_{2}) ...
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 p=p_1p_2\dots p_n 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.
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.
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.
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
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,
- P(n,r) = r! \times C(n, r).
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_{1}, x_{2}, ...,
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 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[] 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++
p = i = n-j;
r[p] = Math.floor((k/=(j-1))%j);
while(i++
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.
- Find the highest index i such that s[i]
s[i+1]. If no such index exists, the permutation is the last
permutation.
- Find the highest index j > i such that
s[j] > s[i]. Such a j must exist, since
i+1 is such an index.
- Swap s[i] with s[j].
- 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:
- ABC
- ACB
- BAC
- BCA
- CAB
- 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:
- how does one encode the permutation state into a unique value
k, and
- 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 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
Notes
- Combinatorics of Permutations, ISBN 1584884347, M. Bona, 2004,
p. 3
- Combinatorics of Permutations, ISBN 1584884347, M. Bona, 2004,
p. 4f
- Combinatorics of Permutations, ISBN 1584884347, M. Bona, 2004,
p. 43
- Combinatorics of Permutations, ISBN 1584884347, M. Bona, 2004,
p. 43ff
- 3GPP TS 36.212
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