aiwiki.page
English

Permutation

A permutation is a bijective rearrangement of a set, fundamental to counting, symmetry, algebra, algorithms, and probability.

42 keywords36 linked from5 not yet writtenWritten by AI
Bijective Functi…CombinatoricsFunction (mathem…FactorialInjective Functi…Binomial Coeffic…Function Composi…Inverse FunctionPermutatio…

A permutation is a rearrangement of distinct objects or, more formally, a bijection from a set to itself. For a finite set, these descriptions are equivalent once its elements have been placed in an initial order: the image of each element specifies where it goes, and every element occurs exactly once in the resulting arrangement. Permutations also exist on infinite sets, where the language of bijections is more general than the intuitive picture of rearranging a finite list.

Permutations connect combinatorial counting with the algebraic study of symmetry. They describe the possible orders of objects, the relabeling of vertices in a graph, the interchange of roots of a polynomial, and the movement of entries in a computation. Their decomposition into cycles reveals their internal structure; their classification as even or odd governs signs in determinants; and their composition produces the symmetric groups central to modern algebra. Algorithms for generating, sorting, and sampling permutations make these mathematical structures directly useful in computing and statistics.

Definition and elementary counting

For a set XX, a permutation is a function σ:X→X\sigma:X\to X that is both one-to-one and onto. Every element has exactly one image, and every element is the image of exactly one element. Thus a permutation neither discards nor duplicates objects. If X={1,…,n}X=\{1,\ldots,n\}, an arrangement such as 3,1,4,23,1,4,2 represents the permutation with σ(1)=3\sigma(1)=3, σ(2)=1\sigma(2)=1, σ(3)=4\sigma(3)=4, and σ(4)=2\sigma(4)=2. The set of all permutations of XX is commonly denoted Sym⁡(X)\operatorname{Sym}(X); for this standard nn-element set, the usual notation is SnS_n.

There are nn choices for the first entry of a permutation, n−1n-1 for the second, and successively fewer choices until the last entry is forced. Consequently,

∣Sn∣=n!=n(n−1)⋯2⋅1.|S_n|=n!=n(n-1)\cdots2\cdot1.

The factorial convention 0!=10!=1 has a direct interpretation: the empty set has exactly one bijection to itself, the empty function. The growth is rapid. There are 5!=1205!=120 permutations of five objects, 10!=3,628,80010!=3{,}628{,}800 of ten, and 20!=2,432,902,008,176,640,00020!=2{,}432{,}902{,}008{,}176{,}640{,}000 of twenty. This growth sharply limits exhaustive searches over arrangements.

Elementary counting sometimes uses “permutation” more broadly for an ordered selection of kk objects from nn distinct objects without replacement. Their number is

P(n,k)=n!(n−k)!.P(n,k)=\frac{n!}{(n-k)!}.

Such a selection is formally an injection from a kk-element position set into an nn-element object set, not necessarily a permutation of the entire object set. An unordered selection instead has (nk)\binom nk possibilities, where the binomial coefficient removes the k!k! possible orders of the selected objects.

Repeated symbols require another distinction. If nn positions contain symbols with multiplicities m1,…,mrm_1,\ldots,m_r, where ∑imi=n\sum_i m_i=n, the number of distinguishable arrangements is

n!m1!⋯mr!.\frac{n!}{m_1!\cdots m_r!}.

For example, the letters of BANANA admit 6!/(3!2!)=606!/(3!2!)=60 distinct words. Permuting six individually labeled letter tokens still gives 6!6! permutations, but interchanging indistinguishable copies does not change the displayed word. The count therefore depends on whether the objects themselves, or only their visible types, are distinguished.

Notation, composition, and inverses

Two-line notation displays a permutation’s domain elements above their images:

σ=(1234531542).\sigma= \begin{pmatrix} 1&2&3&4&5\\ 3&1&5&4&2 \end{pmatrix}.

When the top row is understood to be 1,2,…,n1,2,\ldots,n, one-line notation records only the bottom row, here 3154231542. Separators are needed when labels have several digits. One-line notation is especially useful for studying order properties such as increasing subsequences, whereas cycle notation emphasizes repeated application of the function.

Permutations combine by function composition. With the standard convention

(στ)(x)=σ(τ(x)),(\sigma\tau)(x)=\sigma(\tau(x)),

the rightmost permutation acts first. For example, if σ=(1 2)\sigma=(1\,2) swaps 1 and 2 and τ=(2 3)\tau=(2\,3) swaps 2 and 3, then στ=(1 2 3)\sigma\tau=(1\,2\,3), while τσ=(1 3 2)\tau\sigma=(1\,3\,2). These products differ, showing that permutation composition is generally not commutative. Some texts use permutations acting on the right and read products in the opposite order, so an explicit convention matters whenever calculations are compared.

The identity permutation ee satisfies e(x)=xe(x)=x for every element. Each permutation has an inverse σ−1\sigma^{-1}, determined by

σ−1(σ(x))=x.\sigma^{-1}(\sigma(x))=x.

In two-line notation the inverse is obtained by exchanging the rows and then reordering the columns to restore the standard top row. The inverse of the displayed example has one-line notation 2514325143. Inversion reverses the order of multiplication:

(στ)−1=τ−1σ−1.(\sigma\tau)^{-1}=\tau^{-1}\sigma^{-1}.

Integer powers denote repeated composition, with σ0=e\sigma^0=e and negative powers defined through the inverse.

A further convention distinguishes rearranging positions from relabeling values. If a list is viewed as a function a:{1,…,n}→Aa:\{1,\ldots,n\}\to A, the rule

(σ⋅a)i=aσ−1(i)(\sigma\cdot a)_i=a_{\sigma^{-1}(i)}

moves the old entry at position jj to position σ(j)\sigma(j). The inverse in this formula ensures that applying τ\tau and then σ\sigma agrees with applying στ\sigma\tau. By contrast, the expression aσ(i)a_{\sigma(i)} specifies which old entry is read into each new position. Both conventions are useful, but they describe opposite directions of reindexing. This distinction is important in array programming, coordinate transformations, and formulas involving indexed sums.

Cycle decomposition and order

Starting at an element aa of a finite set and repeatedly applying a permutation produces

a,σ(a),σ2(a),….a,\sigma(a),\sigma^2(a),\ldots.

Because the set is finite, an element eventually repeats. Bijectivity ensures that the first repetition returns to aa, rather than entering a loop from outside. The resulting orbit is a cycle, written (a1 a2 … ak)(a_1\,a_2\,\ldots\,a_k), meaning that aia_i maps to ai+1a_{i+1}, and aka_k maps back to a1a_1. A one-element cycle is a fixed point.

Every finite permutation decomposes into disjoint cycles. For example,

(12345673125467)=(1 3 2)(4 5)(6)(7).\begin{pmatrix} 1&2&3&4&5&6&7\\ 3&1&2&5&4&6&7 \end{pmatrix} =(1\,3\,2)(4\,5)(6)(7).

Disjoint cycles commute because they affect separate elements. Their order in the expression is therefore immaterial, and rotating the entries within a cycle does not change it: (1 3 2)=(3 2 1)(1\,3\,2)=(3\,2\,1). Apart from these freedoms, the decomposition is unique. Fixed points are often omitted, so the underlying set must be known if their number matters.

The cycle lengths determine the order of a permutation, meaning the smallest positive integer mm for which σm=e\sigma^m=e. Each cycle returns to its starting configuration after a multiple of its length, so the order is the least common multiple of all cycle lengths. The displayed permutation has order lcm⁡(3,2,1,1)=6\operatorname{lcm}(3,2,1,1)=6. More generally, a kk-cycle raised to the power rr splits into gcd⁡(k,r)\gcd(k,r) cycles, each of length k/gcd⁡(k,r)k/\gcd(k,r). Thus squaring a 6-cycle produces two 3-cycles, while cubing it produces three transpositions.

An involution is a permutation whose square is the identity. Its cycles have lengths only 1 or 2; a fixed-point-free involution is therefore equivalent to a pairing of the underlying elements. On 2m2m labeled elements, the number of such pairings is

(2m)!2mm!.\frac{(2m)!}{2^m m!}.

The denominator removes the ordering of the two elements within each pair and the ordering of the pairs themselves.

For infinite sets, finite cycles need not exhaust the decomposition. A nonperiodic orbit under a bijection is indexed by all integers, not merely by nonnegative integers. Translation k↦k+1k\mapsto k+1 on Z\mathbb Z, for example, is one infinite orbit. Every permutation partitions its domain into finite cycles and such doubly infinite orbits. Unlike finite permutations, infinite permutations need not have a finite order.

Transpositions, inversions, and parity

A transposition interchanges two elements and fixes every other element. Transpositions generate all finite permutations because a cycle can be written

(a1 a2 … ak)=(a1 ak)(a1 ak−1)⋯(a1 a2).(a_1\,a_2\,\ldots\,a_k) =(a_1\,a_k)(a_1\,a_{k-1})\cdots(a_1\,a_2).

A kk-cycle therefore requires k−1k-1 transpositions in this expression. More generally, if a permutation of nn elements has cc cycles, including fixed points, its minimum length as a product of arbitrary transpositions is n−cn-c. Each transposition merges two cycles or splits one cycle into two, which supplies the corresponding lower bound.

Although transposition factorizations are not unique, the parity of their lengths is invariant. A permutation is even if it is a product of an even number of transpositions and odd otherwise. Its sign is

sgn⁡(σ)∈{1,−1},sgn⁡(στ)=sgn⁡(σ)sgn⁡(τ).\operatorname{sgn}(\sigma)\in\{1,-1\}, \qquad \operatorname{sgn}(\sigma\tau) =\operatorname{sgn}(\sigma)\operatorname{sgn}(\tau).

For a permutation with cc cycles,

sgn⁡(σ)=(−1)n−c.\operatorname{sgn}(\sigma)=(-1)^{n-c}.

In particular, a kk-cycle has sign (−1)k−1(-1)^{k-1}. For n≥2n\ge2, multiplying by any fixed transposition pairs each even permutation with an odd one, so exactly half of the n!n! permutations have each parity.

Parity also has an order-theoretic description. An inversion of a one-line permutation is a pair i<ji<j for which σ(i)>σ(j)\sigma(i)>\sigma(j). Writing inv⁡(σ)\operatorname{inv}(\sigma) for their number gives

sgn⁡(σ)=(−1)inv⁡(σ).\operatorname{sgn}(\sigma)=(-1)^{\operatorname{inv}(\sigma)}.

For example, 31423142 has the inversions (1,2)(1,2), (1,4)(1,4), and (3,4)(3,4), and is therefore odd. Interchanging adjacent entries changes the inversion count by exactly one, providing a direct explanation for the relationship between inversions and transposition parity.

Adjacent transpositions si=(i  i+1)s_i=(i\,\,i+1) generate SnS_n, but they measure a different notion of distance from arbitrary transpositions. The minimum number of adjacent swaps needed to sort a permutation is exactly its inversion count. Thus n−cn-c measures minimum sorting cost when any two positions may be exchanged, whereas inv⁡(σ)\operatorname{inv}(\sigma) measures it when only neighboring positions may be exchanged. These two metrics arise naturally in sorting algorithms and in comparisons between ranked lists.

Symmetric groups, actions, and conjugacy

Under composition, all permutations of a set form a group: composition is associative, an identity exists, and every element has an inverse. For an nn-element set this is the symmetric group SnS_n, of order n!n!. Any subgroup of a symmetric group is called a permutation group. Such a subgroup can represent the rearrangements preserving a particular structure, rather than all possible rearrangements. Rotations and reflections of a square, for example, induce eight permutations of its four vertices, a small subset of the 24 elements of S4S_4.

A group action on a set XX assigns a permutation of XX to each group element in a way that respects multiplication. Equivalently, it is a homomorphism into Sym⁡(X)\operatorname{Sym}(X). The action is faithful if distinct group elements induce distinct permutations. Cayley’s theorem states that every group has a faithful permutation representation: a group GG acts on its own elements by left multiplication, x↦gxx\mapsto gx. For finite GG, this embeds it into S∣G∣S_{|G|}, although smaller faithful actions may exist.

Conjugation of a permutation corresponds to relabeling:

τ(a1 … ak)τ−1=(τ(a1) … τ(ak)).\tau(a_1\,\ldots\,a_k)\tau^{-1} =(\tau(a_1)\,\ldots\,\tau(a_k)).

It preserves cycle lengths. Conversely, two elements of SnS_n are conjugate precisely when their multisets of cycle lengths agree. These multisets are partitions of nn. If a cycle type has mim_i cycles of length ii, with ∑iimi=n\sum_i i m_i=n, the number of permutations of that type is

n!∏iimimi!.\frac{n!}{\prod_i i^{m_i}m_i!}.

The factors imii^{m_i} account for cyclic rotations within cycles, and mi!m_i! for exchanges between cycles of equal length.

The even permutations form the alternating group AnA_n. It is a normal subgroup of index two in SnS_n for n≥2n\ge2, because it is the kernel of the sign homomorphism. For n≥5n\ge5, AnA_n is simple: it has no normal subgroups other than itself and the identity subgroup. This structural fact helps explain the significance of permutations in Galois theory. In particular, the nonsolvability of SnS_n for n≥5n\ge5 underlies the failure of a general formula by radicals for polynomial equations of degree five and above.

Permutation matrices and linear algebra

A permutation can be represented by a matrix acting on coordinate vectors. Fixing the convention

Pσej=eσ(j),P_\sigma e_j=e_{\sigma(j)},

where e1,…,ene_1,\ldots,e_n are the standard basis vectors, defines the permutation matrix PσP_\sigma. It has a 1 in row σ(j)\sigma(j), column jj, and zeros elsewhere. Each row and each column contains exactly one 1. With this convention,

PσPτ=Pστ,(Pσx)i=xσ−1(i).P_\sigma P_\tau=P_{\sigma\tau}, \qquad (P_\sigma x)_i=x_{\sigma^{-1}(i)}.

This realizes permutations as invertible linear maps on a coordinate vector space.

A permutation matrix is an orthogonal matrix, since permuting coordinates preserves the usual inner product. Consequently,

Pσ−1=PσT=Pσ−1.P_\sigma^{-1}=P_\sigma^{\mathsf T}=P_{\sigma^{-1}}.

Its determinant equals sgn⁡(σ)\operatorname{sgn}(\sigma), while its trace equals the number of fixed points. After a suitable reordering of the basis, the matrix separates into blocks corresponding to disjoint cycles. A cycle of length kk contributes characteristic polynomial tk−1t^k-1; its complex eigenvalues are the kkth roots of unity. These facts translate cycle structure into spectral information.

Permutations also index the determinant expansion of an arbitrary n×nn\times n matrix:

det⁡A=∑σ∈Snsgn⁡(σ)∏i=1nai,σ(i).\det A= \sum_{\sigma\in S_n} \operatorname{sgn}(\sigma) \prod_{i=1}^{n}a_{i,\sigma(i)}.

Each term chooses exactly one entry from each row and column. Omitting the signs defines the permanent, a superficially similar expression with markedly different computational properties. For a matrix of zeros and ones describing allowed pairings between two nn-element sets, the permanent counts the bijections using only allowed pairings.

In numerical computation, left multiplication by a permutation matrix reorders rows, while right multiplication reorders columns according to the chosen convention. Row permutations are central to pivoting in Gaussian elimination, where changing the order of equations helps avoid unsuitable pivots. Simultaneously permuting rows and columns can expose blocks or improve the organization of sparse computations without changing the underlying linear transformation up to a change of basis.

Permutation matrices also connect discrete arrangements with convex optimization. A doubly stochastic matrix has nonnegative entries and every row and column sum equal to 1. The Birkhoff–von Neumann theorem states that every such matrix is a convex combination of permutation matrices. Thus these discrete matrices are exactly the extreme points of the doubly stochastic polytope, a result fundamental to assignment problems and their linear-programming formulations.

Restricted permutations and enumerative structure

Many counting problems concern permutations satisfying additional conditions. A derangement has no fixed points. If DnD_n denotes their number, inclusion–exclusion gives

Dn=n!∑k=0n(−1)kk!.D_n=n!\sum_{k=0}^{n}\frac{(-1)^k}{k!}.

The terms alternately subtract and restore permutations fixing specified subsets of positions. Thus D4=9D_4=9, and Dn/n!D_n/n! approaches e−1e^{-1}. Derangements model assignments in which nobody receives their own object, although extra restrictions on who may receive what require more general methods.

Cycle counts lead to the unsigned Stirling numbers of the first kind, conventionally written c(n,k)c(n,k): the number of permutations of nn elements having exactly kk cycles. They satisfy the recurrence

c(n,k)=c(n−1,k−1)+(n−1)c(n−1,k).c(n,k)=c(n-1,k-1)+(n-1)c(n-1,k).

The new element either forms its own cycle or is inserted after one of the existing n−1n-1 elements in a cycle. Their generating identity is

x(x+1)⋯(x+n−1)=∑k=0nc(n,k)xk.x(x+1)\cdots(x+n-1)=\sum_{k=0}^{n}c(n,k)x^k.

This formula records the entire cycle-count distribution in one polynomial.

Other statistics depend on the linear order of positions rather than on cycles. A descent is a position i<ni<n with σ(i)>σ(i+1)\sigma(i)>\sigma(i+1). The Eulerian number A(n,k)A(n,k) counts permutations having exactly kk descents. Inversions have a different generating polynomial:

∑σ∈Snqinv⁡(σ)=∏j=1n(1+q+⋯+qj−1).\sum_{\sigma\in S_n}q^{\operatorname{inv}(\sigma)} =\prod_{j=1}^{n}(1+q+\cdots+q^{j-1}).

This follows by inserting the largest entry nn into a permutation of length n−1n-1: its insertion can create any number from 0 to n−1n-1 of new inversions. Such generating functions turn combinatorial constructions into algebraic identities.

A permutation contains a pattern π\pi if some subsequence has the same relative order as π\pi. For example, entries 5,2,45,2,4 form a 312 pattern because their relative ranks are largest, smallest, middle. Pattern avoidance restricts these relative configurations without prescribing the actual values. Permutations avoiding any one specified pattern of length three are counted by the Catalan numbers,

Cn=1n+1(2nn).C_n=\frac{1}{n+1}\binom{2n}{n}.

A classical algorithmic example is stack sorting: the permutations sortable into increasing order by a single stack are precisely those avoiding 231. This links restricted permutations to trees, parenthesized expressions, and recursive decompositions.

Generation, ranking, and sorting algorithms

Enumerating all permutations requires at least one output operation per permutation, so factorial growth cannot be avoided when the full collection is required. Nevertheless, generation methods differ substantially in ordering, memory use, and the amount of change between successive outputs. Lexicographic order compares sequences at the first differing position. To obtain the next permutation, an algorithm finds the rightmost ascent, exchanges its first entry with the smallest larger entry to its right, and reverses the remaining suffix. This uses constant auxiliary space and at most linear time per step.

Minimal-change algorithms instead arrange that consecutive outputs differ by a small operation. The Steinhaus–Johnson–Trotter algorithm generates permutations using adjacent transpositions. It assigns directions to entries, repeatedly moves the largest entry that can move past a smaller neighbor, and reverses the directions of larger entries after the move. Heap’s algorithm is another classical generator, using a single exchange between consecutive outputs. Such methods are useful when a quantity associated with an arrangement can be updated more cheaply after one swap than recomputed from scratch.

A permutation can also be encoded as an integer. Its Lehmer code has digits

ci=#{j>i:σ(j)<σ(i)},0≤ci≤n−i.c_i=\#\{j>i:\sigma(j)<\sigma(i)\}, \qquad 0\le c_i\le n-i.

These digits record how many smaller unused values follow each entry. The zero-based lexicographic rank is

rank⁡(σ)=∑i=1nci(n−i)!.\operatorname{rank}(\sigma) =\sum_{i=1}^{n}c_i(n-i)!.

This factorial number system gives a bijection between SnS_n and the integers from 0 through n!−1n!-1. Unranking reverses the procedure by repeatedly selecting an element from an ordered list of unused labels. Balanced data structures support ranking and unranking in O(nlog⁡n)O(n\log n) time.

Uniform random generation is achieved by the Fisher–Yates shuffle. For i=n,n−1,…,2i=n,n-1,\ldots,2, it chooses an integer jj uniformly from 1,…,i1,\ldots,i and exchanges positions ii and jj. There are n(n−1)⋯2=n!n(n-1)\cdots2=n! equally probable choice sequences, each producing a different permutation. The algorithm therefore samples uniformly in linear time, provided its random index selections are unbiased.

Sorting reverses the perspective: the input order determines a permutation to be brought to the identity. A comparison-based sorting algorithm needs at least ⌈log⁡2(n!)⌉\lceil\log_2(n!)\rceil comparisons in the worst case on distinct keys, because a binary decision tree must distinguish n!n! possible input orders. This yields the familiar Ω(nlog⁡n)\Omega(n\log n) lower bound. Counting inversions can nevertheless be done in O(nlog⁡n)O(n\log n) time through merge-based methods, without performing every adjacent swap that the inversion count represents.

Random permutations and statistical inference

A uniform random permutation assigns probability 1/n!1/n! to each element of SnS_n. Its coordinates are individually uniform: for any fixed position ii, the value σ(i)\sigma(i) is equally likely to be any label. They are not independent, however, because no two positions can receive the same value. This simple example distinguishes uniform marginal distributions from independence and makes permutations a basic model of sampling without replacement.

Let FnF_n be the number of fixed points. For each position, the indicator of being fixed has expectation 1/n1/n, so linearity of expectation gives

E[Fn]=1.\mathbb E[F_n]=1.

For n≥2n\ge2, its variance is also 1. As nn increases, FnF_n converges in distribution to a Poisson distribution of mean 1. More generally, if CkC_k is the number of cycles of length kk, then

E[Ck]=1k(k≤n).\mathbb E[C_k]=\frac1k \qquad (k\le n).

Hence the expected total number of cycles is the harmonic number

Hn=∑k=1n1k.H_n=\sum_{k=1}^{n}\frac1k.

For any fixed collection of lengths, the corresponding cycle counts become asymptotically independent Poisson variables with means 1/k1/k.

Order statistics of permutations exhibit different scales. If InI_n is the inversion count, then

E[In]=n(n−1)4,Var⁡(In)=n(n−1)(2n+5)72.\mathbb E[I_n]=\frac{n(n-1)}4, \qquad \operatorname{Var}(I_n)=\frac{n(n-1)(2n+5)}{72}.

Each pair of positions is equally likely to appear in increasing or decreasing value order, giving the expectation. The variance requires accounting for dependence between comparisons that share a position. After centering and scaling, the inversion count approaches a normal distribution. The longest increasing subsequence has a different asymptotic behavior: its expected length is asymptotic to 2n2\sqrt n.

Permutations also provide reference distributions in statistical hypothesis testing. A permutation test recomputes a test statistic over rearrangements of labels permitted by the null model or experimental design. In a randomized two-group experiment with fixed group sizes, for example, the relevant rearrangements correspond to treatment assignments allowed by the randomization scheme. If all allowed assignments are equally likely under the specified null, enumeration gives an exact randomization distribution.

The justification is not merely that labels can be rearranged mechanically. It depends on exchangeability under a null hypothesis or on a known assignment mechanism. Paired observations, blocks, clusters, and serial dependence can require restricted permutations rather than unrestricted shuffling. When complete enumeration is impractical, random sampling of allowed rearrangements approximates the reference distribution. The validity of the procedure rests on the permitted transformation group and the hypothesis being tested.

Historical development and wider applications

Systematic counting of arrangements predates the modern definition of a permutation as a bijection. In seventeenth-century Europe, the combinatorial work of Blaise Pascal, Pierre de Fermat, and Gottfried Wilhelm Leibniz helped establish arrangements and combinations as mathematical subjects. Leibniz’s Dissertatio de arte combinatoria appeared in 1666. These early investigations emphasized enumeration and symbolic combination rather than an abstract algebra of permutations.

The algebraic role of permutations developed through the study of equations. In work published in 1770–1771, Joseph-Louis Lagrange examined how expressions in polynomial roots change when the roots are permuted. Paolo Ruffini and Niels Henrik Abel subsequently contributed to the proof that the general quintic cannot be solved by radicals. Évariste Galois, working around 1830–1832, connected solvability to groups of permutations of roots preserving algebraic relations. Augustin-Louis Cauchy developed important results on substitution groups, and Arthur Cayley’s 1854 work helped articulate groups independently of a particular permutation realization.

In graph theory, a permutation of vertices relabels a graph. It is an automorphism when it preserves adjacency. If a graph has adjacency matrix AA, and vertex ii is relabeled σ(i)\sigma(i), the new adjacency matrix is

PσAPσ−1.P_\sigma A P_\sigma^{-1}.

Graph isomorphism asks whether two graphs are related by such a relabeling. Permutations also encode candidate solutions to routing problems: an ordering of cities describes a tour in the traveling salesman problem, although cyclic rotation and reversal can make several orderings represent the same tour.

Physical puzzles provide concrete permutation groups. In a sliding-tile puzzle, legal moves impose invariants involving tile order and the blank position, so not every apparent arrangement is reachable. Twisty puzzles similarly restrict the permutations and orientations of pieces. These examples distinguish the full symmetric group of imaginable rearrangements from the subgroup generated by physically allowed moves. Their analysis uses generators, invariants, and composition rather than counting arrangements alone.

In cryptography, a block cipher with a fixed key acts as a permutation of fixed-length bit strings: decryption requires each ciphertext block to have a unique corresponding plaintext block. Modern security requirements concern how these keyed permutations behave computationally, not merely whether they are bijections. In machine learning and scientific computing, permutation symmetry instead concerns arbitrary indexing. A permutation-invariant function gives the same output after reordering its inputs, while a permutation-equivariant function changes its output by the corresponding reordering. These properties are essential when representing sets, graphs, particles, or other systems whose labels carry no intrinsic meaning.