Permutation
In mathematics, a permutation of a set can mean one of two different things:
- an arrangement of its members in a linear order, or
- the act or process of changing the linear order of an ordered set.[1]
An example of the first meaning, is the six permutations (orderings) of the set {1, 2, 3}: written as tuples, they are (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), and (3, 2, 1). Anagrams of a word whose letters are all different are also permutations: the letters are already ordered in the original word, and the anagram reorders them. The study of permutations of finite sets is an important topic in combinatorics and group theory.
Permutations are used in almost every branch of mathematics and in many other fields of science. In
sequences.The number of permutations of n distinct objects is n factorial, usually written as n!, which means the product of all positive integers less than or equal to n.
According to the second meaning, a permutation of a set S is defined as a bijection from S to itself.[2][3] That is, it is a function from S to S for which every element occurs exactly once as an image value. Such a function is equivalent to the rearrangement of the elements of S in which each element i is replaced by the corresponding . For example, the permutation (3, 1, 2) is described by the function defined as
- .
The collection of all permutations of a set form a group called the symmetric group of the set. The group operation is the composition of functions (performing one rearrangement after the other), which results in another function (rearrangement). The properties of permutations do not depend on the nature of the elements being permuted, only on their number, so one often considers the standard set .
In elementary combinatorics, the k-permutations, or partial permutations, are the ordered arrangements of k distinct elements selected from a set. When k is equal to the size of the set, these are the permutations in the previous sense.
History
Permutations called hexagrams were used in China in the I Ching (Pinyin: Yi Jing) as early as 1000 BC.
In Greece, Plutarch wrote that Xenocrates of Chalcedon (396–314 BC) discovered the number of different syllables possible in the Greek language. This would have been the first attempt on record to solve a difficult problem in permutations and combinations.[4]
The rule to determine the number of permutations of n objects was known in Indian culture around 1150 AD. The
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.[6]
In 1677, Fabian Stedman described factorials when explaining the number of permutations of bells in change ringing. Starting from two bells: "first, two must be admitted to be varied in two ways", which he illustrates by showing 1 2 and 2 1.[7] He then explains that with three bells there are "three times two figures to be produced out of three" which again is illustrated. His explanation involves "cast away 3, and 1.2 will remain; cast away 2, and 1.3 will remain; cast away 1, and 2.3 will remain".[8] He then moves on to four bells and repeats the casting away argument showing that there will be four different sets of three. Effectively, this is a recursive process. He continues with five bells using the "casting away" method and tabulates the resulting 120 combinations.[9] At this point he gives up and remarks:
Now the nature of these methods is such, that the changes on one number comprehends the changes on all lesser numbers, ... insomuch that a compleat Peal of changes on one number seemeth to be formed by uniting of the compleat Peals on all lesser numbers into one entire body;[10]
Stedman widens the consideration of permutations; he goes on to consider the number of permutations of the letters of the alphabet and of horses from a stable of 20.[11]
A first case in which seemingly unrelated mathematical questions were studied with the help of permutations occurred around 1770, when
Permutations played an important role in the cryptanalysis of the Enigma machine, a cipher device used by Nazi Germany during World War II. In particular, one important property of permutations, namely, that two permutations are conjugate exactly when they have the same cycle type, was used by cryptologist Marian Rejewski to break the German Enigma cipher in turn of years 1932-1933.[12][13]
Definition
In mathematics texts it is customary to denote permutations using lowercase Greek letters. Commonly, either or are used.[14]
A permutation can be defined as a bijection (an invertible mapping, a one-to-one and onto function) from a set S to itself:
The
Composition is usually written without a dot or other sign. In general, composition of two permutations is not
As a bijection from a set to itself, a permutation is a function that performs a rearrangement of a set, termed an active permutation or substitution. An older viewpoint sees a permutation as an ordered arrangement or list of all the elements of S, called a passive permutation (see § One-line notation below).[17]
A permutation can be decomposed into one or more disjoint cycles which are the
A fixed point of a permutation is an element x which is taken to itself, that is , forming a 1-cycle . A permutation with no fixed points is called a
Notations
Several notations are widely used to represent permutations conveniently. Cycle notation is a popular choice, as it is compact and shows the permutation's structure clearly. This article will use cycle notation unless otherwise specified.
Two-line notation
Cauchy's two-line notation[18][19] lists the elements of S in the first row, and the image of each element below it in the second row. For example, the permutation of S = {1, 2, 3, 4, 5, 6} given by the function
can be written as
The elements of S may appear in any order in the first row, so this permutation could also be written:
One-line notation
If there is a "natural" order for the elements of S,[b] say , then one uses this for the first row of the two-line notation:
Under this assumption, one may omit the first row and write the permutation in one-line notation as
- ,
that is, as an ordered arrangement of the elements of S.
The example above would then be:
(It is typical to use commas to separate these entries only if some have two or more digits.)
This compact form is common in elementary combinatorics and computer science. It is especially useful in applications where the permutations are to be compared as larger or smaller using lexicographic order.
Cycle notation
Cycle notation describes the effect of repeatedly applying the permutation on the elements of the set S, with an orbit being called a cycle. The permutation is written as a list of cycles; since distinct cycles involve disjoint sets of elements, this is referred to as "decomposition into disjoint cycles".
To write down the permutation in cycle notation, one proceeds as follows:
- Write an opening bracket followed by an arbitrary element x of :
- Trace the orbit of x, writing down the values under successive applications of :
- Repeat until the value returns to x, and close the parenthesis without repeating x:
- Continue with an element y of S which was not yet written, and repeat the above process:
- Repeat until all elements of S are written in cycles.
Also, it is common to omit 1-cycles, since these can be inferred: for any element x in S not appearing in any cycle, one implicitly assumes .[23]
Following the convention of omitting 1-cycles, one may interpret an individual cycle as a permutation which fixes all the elements not in the cycle (a cyclic permutation having only one cycle of length greater than 1). Then the list of disjoint cycles can be seen as the composition of these cyclic permutations. For example, the one-line permutation can be written in cycle notation as:
This may be seen as the composition of cyclic permutations:
While permutations in general do not commute, disjoint cycles do; for example:
Also, each cycle can be rewritten from a different starting point; for example,
Thus one may write the disjoint cycles of a given permutation in many different ways. A convenient feature of cycle notation is that inverting the permutation is given by reversing the order of the elements in each cycle. For example,
Canonical cycle notation
In some combinatorial contexts it is useful to fix a certain order for the elements in the cycles and of the (disjoint) cycles themselves. Miklós Bóna calls the following ordering choices the canonical cycle notation:
- in each cycle the largest element is listed first
- the cycles are sorted in increasing order of their first element, not omitting 1-cycles
For example,
(513)(6)(827)(94)
is a permutation of S = {1, 2, . . . , 9} in canonical cycle notation.[24]
Richard Stanley calls this the "standard representation" of a permutation,[25] and Martin Aigner uses "standard form".[22] Sergey Kitaev also uses the "standard form" terminology, but reverses both choices; that is, each cycle lists its minimal element first, and the cycles are sorted in decreasing order of their minimal elements.[26]
Composition of permutations
There are two ways to denote the composition of two permutations. In the most common notation, is the function that maps any element x to . The rightmost permutation is applied to the argument first,[27] because the argument is written to the right of the function.
A different rule for multiplying permutations comes from writing the argument to the left of the function, so that the leftmost permutation acts first.[28][29][30] In this notation, the permutation is often written as an exponent, so σ acting on x is written xσ; then the product is defined by . This article uses the first definition, where the rightmost permutation is applied first.
The function composition operation satisfies the axioms of a group. It is associative, meaning , and products of more than two permutations are usually written without parentheses. The composition operation also has an identity element (the identity permutation ), and each permutation has an inverse (its inverse function) with .
Other uses of the term permutation
The concept of a permutation as an ordered arrangement admits several generalizations that have been called permutations, especially in older literature.
k-permutations of n
In older literature and elementary textbooks, a k-permutation of n (sometimes called a partial permutation, sequence without repetition, variation, or arrangement) means an ordered arrangement (list) of a k-element subset of an n-set.[c][31][32] The number of such k-permutations (k-arrangements) of is denoted variously by such symbols as , , , , , or ,[33] computed by the formula:[34]
- ,
which is 0 when k > n, and otherwise is equal to
The product is well defined without the assumption that is a non-negative integer, and is of importance outside combinatorics as well; it is known as the
This usage of the term permutation is closely associated with the term combination to mean a subset. A k-combination of a set S is a k-element subset of S: the elements of a combination are not ordered. Ordering the k-combinations of S in all possible ways produces the k-permutations of S. The number of k-combinations of an n-set, C(n,k), is therefore related to the number of k-permutations of n by:
These numbers are also known as binomial coefficients, usually denoted :
Permutations with repetition
Ordered arrangements of k elements of a set S, where repetition is allowed, are called
Permutations of multisets
If M is a finite multiset, then a multiset permutation is an ordered arrangement of elements of M in which each element appears a number of times equal exactly to its multiplicity in M. An anagram of a word having some repeated letters is an example of a multiset permutation.[d] If the multiplicities of the elements of M (taken in some order) are , , ..., and their sum (that is, the size of M) is n, then the number of multiset permutations of M is given by the
For example, the number of distinct anagrams of the word MISSISSIPPI is:[36]
- .
A k-permutation of a multiset M is a sequence of k elements of M in which each element appears a number of times less than or equal to its multiplicity in M (an element's repetition number).
Circular permutations
Permutations, when considered as arrangements, are sometimes referred to as linearly ordered arrangements. If, however, the objects are arranged in a circular manner this distinguished ordering is weakened: there is no "first element" in the arrangement, as any element can be considered as the start. An arrangement of distinct objects in a circular manner is called a circular permutation.
Two circular permutations are equivalent if one can be rotated into the other. The following four circular permutations on four letters are considered to be the same.
1 4 2 3 4 3 2 1 3 4 1 2 2 3 1 4
The circular arrangements are to be read counter-clockwise, so the following two are not equivalent since no rotation can bring one to the other.
1 1 4 3 3 4 2 2
There are (n – 1)! circular permutations of a set with n elements.
Properties
The number of permutations of n distinct objects is n!.
The number of n-permutations with k disjoint cycles is the signless
Cycle type
The cycles (including the fixed points) of a permutation of a set with n elements partition that set; so the lengths of these cycles form an integer partition of n, which is called the cycle type (or sometimes cycle structure or cycle shape) of . There is a "1" in the cycle type for every fixed point of , a "2" for every transposition, and so on. The cycle type of is
This may also be written in a more compact form as [112231]. More precisely, the general form is , where are the numbers of cycles of respective length. The number of permutations of a given cycle type is[39]
- .
The number of cycle types of a set with n elements equals the value of the partition function .
Polya's cycle index polynomial is a generating function which counts permutations by their cycle type.
Conjugating permutations
In general, composing permutations written in cycle notation follows no easily described pattern – the cycles of the composition can be different from those being composed. However the cycle type is preserved in the special case of conjugating a permutation by another permutation , which means forming the product . Here, is the conjugate of by and its cycle notation can be obtained by taking the cycle notation for and applying to all the entries in it.[40] It follows that two permutations are conjugate exactly when they have the same cycle type.
Order of a permutation
The order of a permutation is the smallest positive integer m so that . It is the least common multiple of the lengths of its cycles. For example, the order of is .
Parity of a permutation
Every permutation of a finite set can be expressed as the product of transpositions.[41] Although many such expressions for a given permutation may exist, either they all contain an even number of transpositions or they all contain an odd number of transpositions. Thus all permutations can be classified as
This result can be extended so as to assign a sign, written , to each permutation. if is even and if is odd. Then for two permutations and
It follows that
The sign of a permutation is equal to the determinant of its permutation matrix (below).
Matrix representation
A permutation matrix is an n × n matrix that has exactly one entry 1 in each column and in each row, and all other entries are 0. There are several ways to assign a permutation matrix to a permutation of {1, 2, ..., n}. One natural approach is to define to be the linear transformation of which permutes the standard basis by , and define to be its matrix. That is, has its jth column equal to the n × 1 column vector : its (i, j) entry is to 1 if i = σ(j), and 0 otherwise. Since composition of linear mappings is described by matrix multiplication, it follows that this construction is compatible with composition of permutations:
.
For example, the one-line permutations have product , and the corresponding matrices are:
It is also common in the literature to find the inverse convention, where a permutation σ is associated to the matrix whose (i, j) entry is 1 if j = σ(i) and is 0 otherwise. In this convention, permutation matrices multiply in the opposite order from permutations, that is, . In this correspondence, permutation matrices act on the right side of the standard row vectors : .
The Cayley table on the right shows these matrices for permutations of 3 elements.
Permutations of totally ordered sets
In some applications, the elements of the set being permuted will be compared with each other. This requires that the set S has a total order so that any two elements can be compared. The set {1, 2, ..., n} with the usual ≤ relation is the most frequently used set in these applications.
A number of properties of a permutation are directly related to the total ordering of S, considering the permutation written in one-line notation as a sequence .
Ascents, descents, runs, exceedances, records
An ascent of a permutation σ of n is any position i < n where the following value is bigger than the current one. That is, i is an ascent if . For example, the permutation 3452167 has ascents (at positions) 1, 2, 5, and 6.
Similarly, a descent is a position i < n with , so every i with is either an ascent or a descent.
An ascending run of a permutation is a nonempty increasing contiguous subsequence 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 obtained by omitting some of the values of the one-line notation. 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.[42]
The number of permutations of n with k ascents is (by definition) the Eulerian number ; this is also the number of permutations of n with k descents. Some authors however define the Eulerian number as the number of permutations with k ascending runs, which corresponds to k − 1 descents.[43]
An exceedance of a permutation σ1σ2...σn is an index j such that σj > j. If the inequality is not strict (that is, σj ≥ j), then j is called a weak exceedance. The number of n-permutations with k exceedances coincides with the number of n-permutations with k descents.[44]
A record or left-to-right maximum of a permutation σ is an element i such that σ(j) < σ(i) for all j < i.
Foata's transition lemma
Foata's fundamental bijection transforms a permutation with a given canonical cycle form into the permutation whose one-line notation has the same sequence of elements with parentheses removed.[25][45] For example:
Here the first element in each canonical cycle of becomes a record (left-to-right maximum) of . Given , one may find its records and insert parentheses to construct the inverse transformation . Underlining the records in the above example: , which allows the reconstruction of the cycles of .
The following table shows and for the six permutations of S = {1, 2, 3}, with the bold text on each side showing the notation used in the bijection: one-line notation for and canonical cycle notation for .
As a first corollary, the number of n-permutations with exactly k records is equal to the number of n-permutations with exactly k cycles: this last number is the signless
Inversions
An inversion of a permutation σ is a pair (i, j) of positions where the entries of a permutation are in the opposite order: and .[47] Thus a descent is an inversion at two adjacent positions. For example, σ = 23154 has (i, j) = (1, 3), (2, 3), and (4, 5), where (σ(i), σ(j)) = (2, 1), (3, 1), and (5, 4).
Sometimes an inversion is defined as the pair of values (σ(i), σ(j)); this makes no difference for the number of inversions, and the reverse pair (σ(j), σ(i)) is 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 (that is, transform it into the identity permutation), by successively applying (right-multiplication by)
The number of permutations of n with k inversions is expressed by a
The notation denotes the
Let such that and . In this case, say the weight of the inversion is . Kobayashi (2011) proved the enumeration formula
where denotes Bruhat order in the symmetric groups. This graded partial order often appears in the context of Coxeter groups.
Permutations in computing
Numbering permutations
One way to represent permutations of n things is by an integer N with 0 ≤ N < n!, provided convenient methods are given to convert between the number and the representation of a permutation as an ordered arrangement (sequence). This gives the most compact representation of arbitrary permutations, and in computing is particularly attractive when n is small enough that N can be held in a machine word; for 32-bit words this means n ≤ 12, and for 64-bit words this means n ≤ 20. The conversion can be done via the intermediate form of a sequence of numbers dn, dn−1, ..., d2, d1, where di is a non-negative integer less than i (one may omit d1, as it is always 0, but its presence makes the subsequent conversion to a permutation easier to describe). The first step then is to simply express N in the factorial number system, which is just a particular mixed radix representation, where, for numbers less than n!, the bases (place values or multiplication factors) for successive digits are (n − 1)!, (n − 2)!, ..., 2!, 1!. The second step interprets this sequence as a Lehmer code or (almost equivalently) as an inversion table.
σi i
|
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | Lehmer code |
---|---|---|---|---|---|---|---|---|---|---|
1 | × | × | × | × | × | • | d9 = 5 | |||
2 | × | × | • | d8 = 2 | ||||||
3 | × | × | × | × | × | • | d7 = 5 | |||
4 | • | d6 = 0 | ||||||||
5 | × | • | d5 = 1 | |||||||
6 | × | × | × | • | d4 = 3 | |||||
7 | × | × | • | d3 = 2 | ||||||
8 | • | d2 = 0 | ||||||||
9 | • | d1 = 0 | ||||||||
Inversion table | 3 | 6 | 1 | 2 | 4 | 0 | 2 | 0 | 0 |
In the Lehmer code for a permutation σ, the number dn represents the choice made for the first term σ1, the number dn−1 represents the choice made for the second term σ2 among the remaining n − 1 elements of the set, and so forth. More precisely, each dn+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 dn+1−i counts the inversions (i,j) involving i as smaller index (the number of values j for which i < j and σi > σj). The inversion table for σ is quite similar, but here dn+1−k counts the number of inversions (i,j) where k = σj occurs as the smaller of the two values appearing in inverted order.[49]
Both encodings can be visualized by an n by n Rothe diagram[50] (named after Heinrich August Rothe) in which dots at (i,σi) mark the entries of the permutation, and a cross at (i,σj) marks the inversion (i,j); by the definition of inversions a cross appears in any square that comes both before the dot (j,σj) in its column, and before the dot (i,σi) in its row. The Lehmer code lists the numbers of crosses in successive rows, while the inversion table lists the numbers of crosses in successive columns; it is just the Lehmer code for the inverse permutation, and vice versa.
To effectively convert a Lehmer code dn, dn−1, ..., d2, d1 into a permutation of an ordered set S, one can start with a list of the elements of S in increasing order, and for i increasing from 1 to n set σi to the element in the list that is preceded by dn+1−i other ones, and remove that element from the list. To convert an inversion table dn, dn−1, ..., d2, d1 into the corresponding permutation, one can traverse the numbers from d1 to dn while inserting the elements of S from largest to smallest into an initially empty sequence; at the step using the number d from the inversion table, the element from S inserted into the sequence at the point where it is preceded by d elements already present. Alternatively one could process the numbers from the inversion table and the elements of S both in the opposite order, starting with a row of n empty slots, and at each step place the element from S into the empty slot that is preceded by d other empty slots.
Converting successive natural numbers to the factorial number system produces those sequences in
Algorithms to generate permutations
In computing it may be required to generate permutations of a given sequence of values. The methods best adapted to do this depend on whether one wants some randomly chosen permutations, or all permutations, and in the latter case if a specific ordering is required. Another question is whether possible equality among entries in the given sequence is to be taken into account; if so, one should only generate distinct multiset permutations of the sequence.
An obvious way to generate permutations of n is to generate values for the
Random generation of permutations
For generating random permutations of a given sequence of n values, it makes no difference whether one applies a randomly selected permutation of n to the sequence, or chooses a random element from the set of distinct (multiset) permutations of the sequence. This is because, even though in case of repeated values there can be many distinct permutations of n that result in the same permuted sequence, the number of such permutations is the same for each possible result. Unlike for systematic generation, which becomes unfeasible for large n due to the growth of the number n!, there is no reason to assume that n will be small for random generation.
The basic idea to generate a random permutation is to generate at random one of the n! sequences of integers d1,d2,...,dn satisfying 0 ≤ di < i (since d1 is always zero it may be omitted) and to convert it to a permutation through a
The resulting algorithm for generating a random permutation of a[0], a[1], ..., a[n − 1]
can be described as follows in pseudocode:
for i from n downto 2 do di ← random element of { 0, ..., i − 1 } swap a[di] and a[i − 1]
This can be combined with the initialization of the array a[i] = i
as follows
for i from 0 to n−1 do di+1 ← random element of { 0, ..., i } a[i] ← a[di+1] a[di+1] ← i
If di+1 = i, the first assignment will copy an uninitialized value, but the second will overwrite it with the correct value i.
However, Fisher-Yates is not the fastest algorithm for generating a permutation, because Fisher-Yates is essentially a sequential algorithm and "divide and conquer" procedures can achieve the same result in parallel.[52]
Generation in lexicographic order
There are many ways to systematically generate all permutations of a given sequence.[53] One classic, simple, and flexible algorithm is based upon finding the next permutation in
The following algorithm generates the next permutation lexicographically after a given permutation. It changes the given permutation in-place.
- Find the largest index k such that a[k] < a[k + 1]. If no such index exists, the permutation is the last permutation.
- Find the largest index l greater than k such that a[k] < a[l].
- Swap the value of a[k] with that of a[l].
- Reverse the sequence from a[k + 1] up to and including the final element a[n].
For example, given the sequence [1, 2, 3, 4] (which is in increasing order), and given that the index is zero-based, the steps are as follows:
- Index k = 2, because 3 is placed at an index that satisfies condition of being the largest index that is still less than a[k + 1] which is 4.
- Index l = 3, because 4 is the only value in the sequence that is greater than 3 in order to satisfy the condition a[k] < a[l].
- The values of a[2] and a[3] are swapped to form the new sequence [1, 2, 4, 3].
- The sequence after k-index a[2] to the final element is reversed. Because only one value lies after this index (the 3), the sequence remains unchanged in this instance. Thus the lexicographic successor of the initial state is permuted: [1, 2, 4, 3].
Following this algorithm, the next lexicographic permutation will be [1, 3, 2, 4], and the 24th permutation will be [4, 3, 2, 1] at which point a[k] < a[k + 1] does not exist, indicating that this is the last permutation.
This method uses about 3 comparisons and 1.5 swaps per permutation, amortized over the whole sequence, not counting the initial sort.[55]
Generation with minimal changes
An alternative to the above algorithm, the Steinhaus–Johnson–Trotter algorithm, generates an ordering on all the permutations of a given sequence with the property that any two consecutive permutations in its output differ by swapping two adjacent values. This ordering on the permutations was known to 17th-century English bell ringers, among whom it was known as "plain changes". One advantage of this method is that the small amount of change from one permutation to the next allows the method to be implemented in constant time per permutation. The same can also easily generate the subset of even permutations, again in constant time per permutation, by skipping every other output permutation.[54]
An alternative to Steinhaus–Johnson–Trotter is Heap's algorithm,[56] said by Robert Sedgewick in 1977 to be the fastest algorithm of generating permutations in applications.[53]
The following figure shows the output of all three aforementioned algorithms for generating all permutations of length , and of six additional algorithms described in the literature.
- Lexicographic ordering;
- Steinhaus–Johnson–Trotter algorithm;
- Heap's algorithm;
- Ehrlich's star-transposition algorithm:[54] in each step, the first entry of the permutation is exchanged with a later entry;
- Zaks' prefix reversal algorithm:[58] in each step, a prefix of the current permutation is reversed to obtain the next permutation;
- Sawada-Williams' algorithm:[59] each permutation differs from the previous one either by a cyclic left-shift by one position, or an exchange of the first two entries;
- Corbett's algorithm:[60] each permutation differs from the previous one by a cyclic left-shift of some prefix by one position;
- Single-track ordering:[61] each column is a cyclic shift of the other columns;
- Single-track Gray code:[61] each column is a cyclic shift of the other columns, plus any two consecutive permutations differ only in one or two transpositions.
- Nested swaps generating algorithm in steps connected to the nested subgroups . Each permutation is obtained from the previous by a transposition multiplication to the left. Algorithm is connected to the Factorial_number_system of the index.
Generation of permutations in nested swap steps
Explicit sequence of swaps (transpositions, 2-cycles ), is described here, each swap applied (on the left) to the previous chain providing a new permutation, such that all the permutations can be retrieved, each only once.[62] This counting/generating procedure has an additional structure (call it nested), as it is given in steps: after completely retrieving , continue retrieving by cosets of in , by appropriately choosing the coset representatives to be described below. Note that, since each is sequentially generated, there is a last element . So, after generating by swaps, the next permutation in has to be for some . Then all swaps that generated are repeated, generating the whole coset , reaching the last permutation in that coset ; the next swap has to move the permutation to representative of another coset .
Continuing the same way, one gets coset representatives for the cosets of in ; the ordered set () is called the set of coset beginnings. Two of these representatives are in the same coset if and only if , that is, . Concluding, permutations are all representatives of distinct cosets if and only if for any , (no repeat condition). In particular, for all generated permutations to be distinct it is not necessary for the values to be distinct. In the process, one gets that and this provides the recursion procedure.
EXAMPLES: obviously, for one has ; to build there are only two possibilities for the coset beginnings satisfying the no repeat condition; the choice leads to . To continue generating one needs appropriate coset beginnings (satisfying the no repeat condition): there is a convenient choice: , leading to . Then, to build a convenient choice for the coset beginnings (satisfying the no repeat condition) is , leading to .
From examples above one can inductively go to higher in a similar way, choosing coset beginnings of in , as follows: for even choosing all coset beginnings equal to 1 and for odd choosing coset beginnings equal to . With such choices the "last" permutation is for odd and for even (). Using these explicit formulae one can easily compute the permutation of certain index in the counting/generation steps with minimum computation. For this, writing the index in factorial base is useful. For example, the permutation for index is: , yelding finally, .
Because multiplying by swap permutation takes short computing time and every new generated permutation requires only one such swap multiplication, this generation procedure is quite efficient. Moreover as there is a simple formula, having the last permutation in each can save even more time to go directly to a permutation with certain index in fewer steps than expected as it can be done in blocks of subgroups rather than swap by swap.
Applications
Permutations are used in the
See also
- Alternating permutation
- Convolution
- Cyclic order
- Even and odd permutations
- Josephus permutation
- Levi-Civita symbol
- List of permutation topics
- Major index
- Permutation category
- Permutation group
- Permutation pattern
- Permutation representation (symmetric group)
- Probability
- Rencontres numbers
- Sorting network
- Substitution cipher
- Superpattern
- Superpermutation
- Twelvefold way
- Weak order of permutations
Notes
- ^ 1 is frequently used to represent the identity element in a non-commutative group
- ^ The order is often implicitly understood. A set of integers is naturally written from smallest to largest; a set of letters is written in lexicographic order. For other sets, a natural order needs to be specified explicitly.
- ^ More precisely, variations without repetition. The term is still common in other languages and appears in modern English most often in translation.
- ^ The natural order in this example is the order of the letters in the original word.
- ^ In older texts circular permutation was sometimes used as a synonym for cyclic permutation, but this is no longer done. See Carmichael (1956, p. 7)
References
- ^ Webster (1969)
- ^ McCoy (1968, p. 152)
- ^ Nering (1970, p. 86)
- OCLC 7703465.
- S2CID 123537702.
- .
- ^ Stedman 1677, p. 4.
- ^ Stedman 1677, p. 5.
- ^ Stedman 1677, pp. 6–7.
- ^ Stedman 1677, p. 8.
- ^ Stedman 1677, pp. 13–18.
- ISSN 1233-7234.
- ^ Cash, David (2019). "CMSC 28400 Introduction to Cryptography Autumn 2019 - Notes #2: Permutations and Enigma" (PDF).
- ISBN 978-0840049421. Archivedfrom the original on February 5, 2020. Retrieved February 5, 2020.
It is customary to use lowercase Greek letters (especially π, σ, and τ) to stand for permutations.
- ^ Rotman 2002, p. 41
- ^ Bogart 1990, p. 487
- ^ Cameron 1994, p. 29, footnote 3.
- ^ Cauchy, A. L. (January 1815). "Mémoire Sur le Nombre des Valeurs qu'une Fonction peut acquérir, lorsqu'on y permute de toutes les manières possibles les quantités qu'elle renferme" [Memoir on the number of values which a function can acquire when one permutes within it, in all possible ways, the variables which it contains]. Journal de l'École polytechnique (in French). 10: 1–28. See p. 4.
- ISBN 9780486458687,
Cauchy used his permutation notation—in which the arrangements are written one below the other and both are enclosed in parentheses—for the first time in 1815.
- ^ Bogart 1990, p. 17
- ^ Gerstein 1987, p. 217
- ^ ISBN 978-3-540-39035-0.
- ^ Hall 1959, p. 54
- ^ Bona 2012, p.87 [The book has a typo/error here, as it gives (45) instead of (54).]
- ^ ISBN 978-1-107-01542-5.
- ISBN 978-3-642-17333-2.
- ^
Biggs, Norman L.; White, A. T. (1979). Permutation groups and combinatorial structures. Cambridge University Press. ISBN 978-0-521-22287-7.
- ^
Dixon, John D.; Mortimer, Brian (1996). Permutation Groups. Springer. ISBN 978-0-387-94599-6.
- ^
Cameron, Peter J. (1999). Permutation groups. Cambridge University Press. ISBN 978-0-521-65302-2.
- ^
Jerrum, M. (1986). "A compact representation of permutation groups". J. Algorithms. 7 (1): 60–78. S2CID 18896625.
- ^ "Combinations and Permutations". www.mathsisfun.com. Retrieved 2020-09-10.
- ^ Weisstein, Eric W. "Permutation". mathworld.wolfram.com. Retrieved 2020-09-10.
- ^ Uspensky 1937, p. 18
- ISBN 978-1-58488-290-9.
- ^ Brualdi 2010, p. 46, Theorem 2.4.2
- ^ Brualdi 2010, p. 47
- ^ Brualdi 2010, p. 39
- ^ Bona 2012, pp. 97–103.
- ^ Sagan, Bruce (2001), The Symmetric Group (2 ed.), Springer, p. 3
- ^ Humphreys 1996, p. 84.
- ^ Hall 1959, p. 60
- ^ Bóna 2004, p. 4f.
- ^ Bona 2012, pp. 4–5.
- ^ Bona 2012, p. 25.
- ^ a b Bona 2012, pp. 109–110.
- ^ Slocum, Jerry; Weisstein, Eric W. (1999). "15 – puzzle". MathWorld. Wolfram Research, Inc. Retrieved October 4, 2014.
- ^ Bóna 2004, p. 43.
- ^ Bóna 2004, pp. 43ff.
- ^ Knuth 1973, p. 12.
- ^ H. A. Rothe, Sammlung combinatorisch-analytischer Abhandlungen 2 (Leipzig, 1800), 263–305. Cited in Knuth 1973, p. 14
- OCLC 14222135.
- ^ Bacher, A.; Bodini, O.; Hwang, H.K.; Tsai, T.H. (2017). "Generating Random Permutations by Coin Tossing: Classical Algorithms, New Analysis, and Modern Implementation" (ACM Trans. Algorithms 13(2): 24:1–24:43 ed.). pp. 24–43.
- ^ (PDF) from the original on 2008-02-21.
- ^ a b c Knuth 2005, pp. 1–26.
- ^ "std::next_permutation". cppreference.com. 4 December 2017. Retrieved 31 March 2018.
- .
- ^ Mütze, Torsten; Sawada, Joe; Williams, Aaron. "Generate permutations". Combinatorial Object Server. Retrieved May 29, 2019.
- S2CID 30234652.
- .
- .
- ^ ISBN 978-3-642-14763-0.
- ^ Popp, O.T. (2002). Quickly Handling Big Permutations. priv. comm.
- ^ "3GPP TS 36.212".
- .
Bibliography
- Bogart, Kenneth P. (1990), Introductory Combinatorics (2nd ed.), Harcourt Brace Jovanovich, ISBN 978-0-15-541576-8
- ISBN 978-1-58488-434-7
- Bona, Miklos (2012), Combinatorics of Permutations (2nd ed.), CRC Press, ISBN 978-1-4398-5051-0
- Brualdi, Richard A. (2010), Introductory Combinatorics (5th ed.), Prentice-Hall, ISBN 978-0-13-602040-0
- Cameron, Peter J. (1994), Combinatorics: Topics, Techniques, Algorithms, Cambridge University Press, ISBN 978-0-521-45761-3
- Carmichael, Robert D. (1956) [1937], Introduction to the theory of Groups of Finite Order, Dover, ISBN 978-0-486-60300-1
- Fraleigh, John B. (1976), A First Course In Abstract Algebra (2nd ed.), Reading: ISBN 0-201-01984-1
- Gerstein, Larry J. (1987), Discrete Mathematics and Algebraic Structures, W.H. Freeman and Co., ISBN 978-0-7167-1804-8
- Hall, Marshall Jr. (1959), The Theory of Groups, MacMillan
- Humphreys, J. F. (1996), A course in group theory, Oxford University Press, ISBN 978-0-19-853459-4
- Knuth, Donald (1973), Sorting and Searching, The Art of Computer Programming, vol. 3 This book mentions the Lehmer code (without using that name) as a variant C1,...,Cn of inversion tables in exercise 5.1.1–7 (p. 19), together with two other variants.
- ISBN 978-0-201-85393-3Fascicle 2, first printing.
- McCoy, Neal H. (1968), Introduction To Modern Algebra, Revised Edition, Boston: LCCN 68015225
- Nering, Evar D. (1970), Linear Algebra and Matrix Theory (2nd ed.), New York: LCCN 76091646
- Rotman, Joseph J. (2002), Advanced Modern Algebra, Prentice-Hall, ISBN 978-0-13-087868-7
- Stedman, Fabian (1677), Campanalogia, London The publisher is given as "W.S." who may have been William Smith, possibly acting as agent for the Society of College Youths, to which society the "Dedicatory" is addressed. In quotations the original long "S" has been replaced by a modern short "s".
- Uspensky, James (1937), Introduction to Mathematical Probability, McGraw-Hill
- Webster's Seventh New Collegiate Dictionary, Springfield: G. & C. Merriam Company, 1969
Further reading
- Biggs, Norman L. (2002), Discrete Mathematics (2nd ed.), Oxford University Press, ISBN 978-0-19-850717-8
- Foata, Dominique; Schutzenberger, Marcel-Paul (1970), Théorie Géométrique des Polynômes Eulériens, Lecture Notes in Mathematics, vol. 138, Berlin, Heidelberg: Springer-Verlag, ISBN 978-3-540-04927-2. The link is to a freely available retyped (LaTeX'ed) and revised version of the text originally published by Springer-Verlag.
- Knuth, Donald (1998), Sorting and Searching, The Art of Computer Programming, vol. 3 (Second ed.), Addison–Wesley, ISBN 978-0-201-89685-5. Section 5.1: Combinatorial Properties of Permutations, pp. 11–72.
- Sedgewick, Robert (1977). "Permutation generation methods". ACM Computing Surveys. 9 (2): 137–164. S2CID 12139332.
- Masato, Kobayashi (2011). "Enumeration of bigrassmannian permutations below a permutation in Bruhat order". Order. 1: 131–137.
External links
- "Permutation", Encyclopedia of Mathematics, EMS Press, 2001 [1994]