ExtendedSource checked

Heap's Algorithm

Generates permutations by recursively swapping elements.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Procedural Generation
Difficulty: Intermediate
Family: Permutation generation
Tier: Extended
Status: Verified
Review: Source Checked
Sources: 2
Formulas: 0
Relationships: 2
Code example: Not ready
Visualization: Not ready
Aliases: Heap permutation generation, Heap's permutation algorithm

Overview

Heap's Algorithm enumerates all permutations of a list using a recursive swap pattern that changes one or two positions between generated permutations.

Core Concepts

permutation generationrecursionswap-based enumeration

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(n!) generated permutations

Average

O(n!) generated permutations

Worst

O(n!) generated permutations

Space

O(n) recursion depth plus output storage if materialized

When to Use

Use when all permutations of a small collection must be enumerated.

When Not to Use

Avoid when random shuffling or sampling a few permutations is enough.

What It Does

Recursively generates permutations of the first n elements.
Uses parity-dependent swaps to visit all permutations.
Produces every ordering exactly once.

Use Cases

Combinatorial testing
Permutation enumeration
Teaching recursive generation

Inputs

A finite sequence of n items.

Outputs

Every permutation of the sequence, generated by recursive swaps.

Pseudocode

1.Generate permutations of n - 1 elements.
2.Swap according to parity.
3.Repeat until all n positions have been used.

Canonical Example

Input: [A, B, C]
Output: All six permutations of A, B, and C.
Explanation: The recursive swap pattern enumerates each possible ordering once.

Implementation Notes

The recursive version swaps with the last element depending on parity of the subproblem size.

Common Pitfalls

The number of outputs is factorial, so small input growth quickly dominates runtime.

Interactive Mechanism Walkthrough

Spatial Primitive & Sweep-Line Canvas

Show recursive swap positions and the stream of generated permutations.

Step 1 of 3: Generate permutations of n - 1 elements.

permutation-swaps

Notes

Heap's Algorithm is a deterministic permutation generator; procedural-generation is the closest current Atlas category because no combinatorial-generation category exists.