Generating Permutations

Introduction

A permutation of a set is an arrangement of its elements in a specific order. For a set of n distinct elements, there are n! (n factorial) permutations. Generating all permutations is a fundamental task in combinatorics, with applications ranging from brute-force search and optimization to cryptography and statistical analysis.

The challenge in generating permutations is to enumerate all n! arrangements systematically, without repetition and without omission. Several algorithms exist, each with different properties regarding the order in which permutations are generated, the number of element swaps required, and the ease of implementation.

For small n (up to about 10-12), exhaustive enumeration of all permutations is practical. Beyond that, n! grows so rapidly that full enumeration becomes infeasible -- 20! exceeds 2.4 quintillion. In such cases, random sampling or structured search methods must be used instead.

Recursive Approach

The simplest method for generating permutations uses recursion. The idea is to fix one element at each position and recursively permute the remaining elements. This approach directly mirrors the combinatorial definition: choose the first element (n choices), then permute the remaining n-1 elements.

Pseudocode

procedure Permute(arr, start, end): if start == end: output arr return for i from start to end: swap(arr[start], arr[i]) Permute(arr, start + 1, end) swap(arr[start], arr[i]) // backtrack

At each level of recursion, the algorithm tries each unused element in the first available position, generates all permutations of the remaining elements, and then restores the original order (backtracks) before trying the next element. This produces all n! permutations, though not necessarily in lexicographic order.

The recursive approach generates each permutation with O(n) swaps in total across all recursive calls. The backtracking step ensures the array is restored to its original state at each level, maintaining correctness.

Heap's Algorithm

Heap's algorithm, developed by B. R. Heap in 1963, is an elegant method that generates all permutations with the minimum number of swaps. Each successive permutation differs from the previous one by exactly one swap of two elements, making it extremely efficient.

Pseudocode

procedure HeapPermute(arr, n): if n == 1: output arr return for i from 0 to n-1: HeapPermute(arr, n - 1) if n is even: swap(arr[i], arr[n-1]) else: swap(arr[0], arr[n-1])

How It Works

The key insight is the swap rule: when n is even, swap the i-th element with the last element; when n is odd, always swap the first element with the last. This simple rule ensures that every permutation is generated exactly once with just one swap between consecutive outputs.

Lexicographic Order

Generating permutations in lexicographic (dictionary) order is useful when a specific ordering is required. The algorithm to find the next permutation in lexicographic order was described by Naryana Pandita in 14th-century India and later rediscovered by several mathematicians.

Next Permutation Algorithm

procedure NextPermutation(arr): // Step 1: Find largest index i such that arr[i] < arr[i+1] i = n - 2 while i >= 0 and arr[i] >= arr[i+1]: i = i - 1 if i < 0: return false // last permutation reached // Step 2: Find largest index j > i such that arr[i] < arr[j] j = n - 1 while arr[j] <= arr[i]: j = j - 1 // Step 3: Swap arr[i] and arr[j] swap(arr[i], arr[j]) // Step 4: Reverse the suffix starting at arr[i+1] reverse(arr, i + 1, n - 1) return true

This algorithm runs in O(n) per permutation in the worst case and O(1) amortized, since most permutations require only a small number of operations to compute the next one.

Worked Example

Generate all permutations of {1, 2, 3} using Heap's algorithm:

Call HeapPermute([1,2,3], 3): n=3, i=0: HeapPermute([1,2,3], 2) n=2, i=0: HeapPermute([1,2,3], 1) -> output [1,2,3] swap(arr[0], arr[1]) -> [2,1,3] n=2, i=1: HeapPermute([2,1,3], 1) -> output [2,1,3] swap(arr[0], arr[1]) -> [1,2,3] swap(arr[0], arr[2]) -> [3,2,1] n=3, i=1: HeapPermute([3,2,1], 2) n=2, i=0: HeapPermute([3,2,1], 1) -> output [3,2,1] swap(arr[0], arr[1]) -> [2,3,1] n=2, i=1: HeapPermute([2,3,1], 1) -> output [2,3,1] swap(arr[0], arr[1]) -> [3,2,1] swap(arr[0], arr[2]) -> [1,2,3] n=3, i=2: HeapPermute([1,2,3], 2) n=2, i=0: HeapPermute([1,2,3], 1) -> output [1,3,2] swap(arr[0], arr[1]) -> [3,1,2] n=2, i=1: HeapPermute([3,1,2], 1) -> output [3,1,2]All 6 permutations: [1,2,3], [2,1,3], [3,2,1], [2,3,1], [1,3,2], [3,1,2]

In lexicographic order, the same set produces: [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1].

Complexity Analysis

All algorithms produce exactly n! permutations. The key difference is the cost per transition. Heap's algorithm achieves the theoretical minimum of one swap per permutation. The lexicographic approach requires O(n) operations in the worst case for a single next-permutation call, but the amortized cost is O(1) since most transitions affect only the last few elements.

Steinhaus-Johnson-Trotter Algorithm

The Steinhaus-Johnson-Trotter (SJT) algorithm generates permutations such that each successive permutation differs by a single adjacent transposition (a swap of two neighboring elements). This is a stronger minimal-change property than Heap's algorithm, where the swapped elements may be non-adjacent.

procedure SJT(n): assign direction LEFT to all elements output initial permutation while a mobile element exists: find largest mobile element m swap m with the neighbor it points to reverse direction of all elements larger than m output current permutation// An element is "mobile" if it is larger than the neighbor// it is currently pointing toward.

The SJT algorithm is useful in applications where the cost of a swap depends on the distance between swapped elements, since adjacent transpositions are the cheapest possible changes.

k-Permutations

A k-permutation of n elements is an ordered selection of k elements from a set of n. The number of k-permutations is P(n, k) = n! / (n-k)!. When k = n, this reduces to the standard permutation count.

procedure KPermutations(arr, k, start): if start == k: output arr[0..k-1] return for i from start to n-1: swap(arr[start], arr[i]) KPermutations(arr, k, start + 1) swap(arr[start], arr[i])

k-permutations arise naturally in problems like ranking, tournament scheduling, and password generation where order matters but not all elements are selected.

Applications

• Brute-Force Search: Many optimization problems (traveling salesman, assignment problem) can be solved exactly by evaluating all permutations of the input.
• Cryptanalysis: Analyzing substitution ciphers requires examining permutations of the alphabet to find the decryption key.
• Testing: Generating all permutations of test inputs helps verify that algorithms produce correct results regardless of input order.
• Combinatorial Design: Constructing Latin squares, balanced tournament schedules, and experimental designs relies on systematic permutation generation.
• Music and Art: Permutations of notes, colors, or motifs can generate variations in composition and design.

References

• Heap, B. R. "Permutations by Interchanges." The Computer Journal, vol. 6, no. 3, 1963, pp. 293-298.
• Knuth, D. E. "The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1." Addison-Wesley, 2011.
• Sedgewick, R. "Permutation Generation Methods." ACM Computing Surveys, vol. 9, no. 2, 1977, pp. 137-164.
• Steinhaus, H. "One Hundred Problems in Elementary Mathematics." Basic Books, 1964.
• Johnson, S. M. "Generation of Permutations by Adjacent Transposition." Mathematics of Computation, vol. 17, 1963, pp. 282-285.