abyiber.com
Back to Blog

Permutation Groups: Rearrangements, Cycles, and Shuffles

How the symmetric group S_n captures every possible rearrangement, and why cycle notation connects to sorting networks, shuffle algorithms, and puzzle solvers.

2025-06-17
Share
Abstract Algebrapermutation-groupssymmetric-groupmath-for-cs

Terminology

Term Definition
Permutation A bijection from a finite set to itself, rearranging its elements
Symmetric group $S_n$ The group of all permutations of $\{1, 2, \ldots, n\}$ under composition, with $|S_n| = n!$
Cycle notation Writing a permutation as a product of disjoint cycles, e.g., $(1\;3\;2)$ means $1 \to 3 \to 2 \to 1$
Transposition A cycle of length 2 that swaps exactly two elements, e.g., $(1\;3)$
Even permutation A permutation expressible as a product of an even number of transpositions
Odd permutation A permutation expressible as a product of an odd number of transpositions
Sign (parity) $\text{sgn}(\sigma) = +1$ if $\sigma$ is even, $-1$ if odd
Inversion A pair $(i, j)$ where $i < j$ but $\sigma(i) > \sigma(j)$. The number of inversions determines parity.

What & Why

A permutation is simply a rearrangement. The symmetric group S_n is the collection of all possible rearrangements of n objects, and it is one of the most important groups in mathematics. Cayley's theorem tells us that every finite group is isomorphic to a subgroup of some S_n, making permutation groups the "universal" finite groups.

For computer scientists, permutations are everywhere:

  • Sorting is the problem of transforming an arbitrary permutation into the identity permutation. The minimum number of swaps needed equals the number of elements minus the number of cycles.
  • Shuffle algorithms (like Fisher-Yates) generate uniformly random permutations. Correctness requires that every permutation in S_n is equally likely.
  • Puzzle solvers for the Rubik's Cube, 15-puzzle, and similar games model states as permutations and moves as group elements.
  • Sorting networks use fixed sequences of comparators (transpositions) to sort any input, and the theory of even/odd permutations determines which states are reachable.

The group operation is composition: applying one rearrangement after another. The identity is the "do nothing" permutation, and every permutation has an inverse (the rearrangement that undoes it).

How It Works

Two-Line and Cycle Notation

A permutation $\sigma$ on $\{1,2,3,4,5\}$ can be written in two-line notation showing where each element maps:

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

This means $1 \to 3$, $2 \to 5$, $3 \to 1$, $4 \to 4$, $5 \to 2$. In cycle notation, we follow the chains:

$\sigma = (1\;3)(2\;5)(4) = (1\;3)(2\;5)$

Fixed points (like 4) are usually omitted. Disjoint cycles commute, so the order does not matter.

Cycle diagram for sigma = (1 3)(2 5) 1 3 2 5 4 is a fixed point (not shown)

Transpositions and Parity

Every permutation can be decomposed into transpositions (swaps of two elements). A $k$-cycle $(a_1\;a_2\;\ldots\;a_k)$ decomposes into $k - 1$ transpositions:

$(a_1\;a_2\;\ldots\;a_k) = (a_1\;a_k)(a_1\;a_{k-1})\cdots(a_1\;a_2)$

The parity (even or odd) of a permutation is well-defined: no matter how you decompose it, the number of transpositions is always even or always odd. The sign function $\text{sgn}(\sigma)$ equals $(-1)^{\text{number of inversions}}$.

Parity has a direct CS consequence: the 15-puzzle is solvable from a given starting position if and only if the permutation of tiles is even. Half of all starting configurations are unreachable.

Composition

Composing permutations means applying one after the other. If $\sigma = (1\;3)$ and $\tau = (1\;2\;3)$, then $\tau \circ \sigma$ means "first apply $\sigma$, then apply $\tau$":

$\tau \circ \sigma: 1 \xrightarrow{\sigma} 3 \xrightarrow{\tau} 1, \quad 2 \xrightarrow{\sigma} 2 \xrightarrow{\tau} 3, \quad 3 \xrightarrow{\sigma} 1 \xrightarrow{\tau} 2$

So $\tau \circ \sigma = (2\;3)$. Note that permutation composition is generally not commutative: $\sigma \circ \tau \neq \tau \circ \sigma$.

Complexity Analysis

Operation Time Space Notes
Compose two permutations $O(n)$ $O(n)$ Apply one array lookup per element
Invert a permutation $O(n)$ $O(n)$ Reverse the mapping
Decompose into cycles $O(n)$ $O(n)$ Follow chains with a visited array
Count inversions $O(n \log n)$ $O(n)$ Modified merge sort
Compute parity from cycles $O(n)$ $O(n)$ Parity = $(-1)^{n - \text{number of cycles}}$
Min swaps to sort $O(n)$ $O(n)$ $n - \text{(number of cycles)}$

The minimum number of adjacent swaps (transpositions of neighbors) to sort a permutation equals its inversion count. The minimum number of arbitrary swaps equals $n$ minus the number of cycles in the cycle decomposition.

Implementation

ALGORITHM CycleDecomposition(perm)
INPUT:  perm: array of size n representing a permutation (0-indexed)
OUTPUT: list of cycles, each cycle is a list of elements

BEGIN
  n := LENGTH(perm)
  visited := array of n booleans, all FALSE
  cycles := empty list

  FOR i FROM 0 TO n - 1 DO
    IF NOT visited[i] THEN
      cycle := empty list
      j := i
      WHILE NOT visited[j] DO
        visited[j] := TRUE
        APPEND j TO cycle
        j := perm[j]
      END WHILE
      IF LENGTH(cycle) > 1 THEN
        APPEND cycle TO cycles
      END IF
    END IF
  END FOR

  RETURN cycles
END

ALGORITHM MinSwapsToSort(perm)
INPUT:  perm: array of size n representing a permutation
OUTPUT: minimum number of swaps to transform perm into the identity

BEGIN
  cycles := CycleDecomposition(perm)
  num_cycles := LENGTH(cycles) + count of fixed points
  RETURN n - num_cycles
END

ALGORITHM FisherYatesShuffle(arr)
INPUT:  arr: array of n elements
OUTPUT: arr rearranged into a uniformly random permutation

BEGIN
  n := LENGTH(arr)
  FOR i FROM n - 1 DOWNTO 1 DO
    j := RANDOM_INTEGER(0, i)    // inclusive on both ends
    SWAP arr[i] AND arr[j]
  END FOR
  RETURN arr
END

Fisher-Yates produces each of the $n!$ permutations with equal probability $1/n!$, which is provable by induction on the number of swap steps.

Real-World Applications

  • Sorting theory: every sorting algorithm transforms an input permutation into the identity. The cycle structure determines the minimum number of swaps, and inversion count determines the minimum number of adjacent swaps (bubble sort's metric).
  • Shuffle algorithms: Fisher-Yates (Knuth shuffle) generates uniformly random permutations in $O(n)$ time. Incorrect implementations that pick from the full range at each step produce biased distributions.
  • Rubik's Cube solvers: the Rubik's Cube group is a subgroup of $S_{48}$ (48 colored facelets). Group-theoretic algorithms like Kociemba's two-phase algorithm exploit the subgroup structure to find near-optimal solutions.
  • 15-puzzle solvability: the puzzle is solvable if and only if the tile permutation is even. This is a direct application of permutation parity.
  • Sorting networks: a sorting network is a fixed sequence of comparators. The 0-1 principle (if a network sorts all binary sequences, it sorts everything) connects to the structure of $S_n$.
  • Determinant computation: the determinant of a matrix is defined as a sum over all permutations in $S_n$, weighted by their signs. Efficient algorithms avoid enumerating all $n!$ permutations.

Key Takeaways

  • The symmetric group $S_n$ contains all $n!$ permutations of $n$ elements and is the "universal" finite group (Cayley's theorem)
  • Cycle notation compactly represents permutations and reveals structure: the number of cycles determines the minimum swaps to sort
  • Every permutation decomposes into transpositions, and the parity (even/odd) is an invariant that determines reachability in puzzles and games
  • Fisher-Yates shuffle generates uniformly random permutations in $O(n)$ by leveraging the group structure
  • Counting inversions ($O(n \log n)$ via merge sort) measures how "far" a permutation is from sorted, connecting group theory to sorting complexity