Superpermutation¶
A string over n symbols that contains every permutation of those symbols as a contiguous substring.
Core Idea¶
A superpermutation is a covering word. Fix n symbols and the n! permutations of length n; one host string qualifies if each target occurs as an unbroken substring. Suffix–prefix overlap lets neighboring targets share characters, often shortening the host far below naive concatenation.
Existence, construction, and optimality are different claims. Any concatenation is valid, a clever construction supplies an upper bound, and a lower-bound argument is needed to prove minimum length. Known small cases therefore should not be generalized into an unsupported formula.
Scope of Application¶
- Combinatorics on words. Studies overlap among target permutations.
- Optimization. Seeks minimum host length.
- Graph formulations. Represents suffix–prefix transitions among permutations.
- Computation. Searches constructions and certifies coverage for small n.
Clarity¶
State n, alphabet, whether the host is linear or cyclic, the exact coverage test, string length, and whether minimality is proved or only conjectured. Provide machine-checkable occurrence positions for large examples. Inclusion test: Include strings over an n-symbol alphabet for which every length-n permutation occurs contiguously at least once. Exclusion test: Exclude strings covering combinations only, subsequences with gaps, universal cycles interpreted cyclically without linearization, and shortest-common-supersequence problems over a different target family. Nearest boundary: A concatenation of all permutations is a valid but generally trivial superpermutation; it is a near-miss only for claims of optimality, not validity. Exit condition: The object exits when one permutation lacks a contiguous occurrence or symbols outside the defined alphabet alter the problem. Common misclassifications: It is not coverage by noncontiguous subsequences. It is not a string containing every combination. It is not necessarily a shortest superpermutation. It is not automatically a cyclic universal cycle. Nearest named distinctions: Supersequence: May allow targets as noncontiguous subsequences. De Bruijn sequence: Covers all fixed-length words, usually cyclically. Permutation concatenation: A valid construction, not the definition of minimality. Universal cycle: Uses cyclic windows and may target another object family.
Manages Complexity¶
The definition compresses factorially many targets into one sequence. Separating coverage from minimality prevents a computational construction from being mistaken for a proof of optimum.
Abstract Reasoning¶
- Enumerate the n! target permutations.
- Choose an ordering or overlap graph.
- Merge compatible suffixes and prefixes.
- Scan every length-n host window.
- Certify complete coverage.
- Pair upper constructions with valid lower bounds before claiming optimality.
Knowledge Transfer¶
The overlap-covering framework transfers to shortest common superstrings and universal sequence design when target objects and occurrence rules are redefined. Superpermutation length bounds do not transfer to combinations, subsequences, or cyclic coverage unchanged.
Relationships to Other Abstractions¶
Current abstraction Superpermutation Domain-specific
Parents (1) — more general patterns this builds on
-
Superpermutation presupposes Permutation Prime
Superpermutation presupposes Permutation because the string is defined by containing every permutation of its symbol set as a substring.
Hierarchy paths (3) — routes to 1 parentless root
- Superpermutation → Permutation → Bijectivity → Function (Mapping)
- Superpermutation → Permutation → Bijectivity → Injectivity → Function (Mapping)
- Superpermutation → Permutation → Bijectivity → Surjectivity → Function (Mapping)
Neighborhood in Abstraction Space¶
Superpermutation sits in a crowded region of the domain-specific corpus (26th percentile for distinctiveness): several abstractions share nearly its structure, so a description that fits it tends to fit its neighbors too.
Family — Matrices, Measures & Numeric Structures (30 abstractions)
Nearest neighbors
- Permutation Code — 0.92
- Dyck language — 0.90
- String kernel — 0.89
- Regular Expression — 0.89
- Group code — 0.88
Computed from structural-signature embeddings · 2026-10-08