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.
Structural Signature¶
Sig role-phrases:
- Alphabet of n symbols — Defines the symbols used and the permutation set. It is parameter space. Counterfactual: Adding or omitting symbols changes the required family.
- Permutation family — Supplies all n! target words of length n. It is coverage requirement. Counterfactual: Missing even one target invalidates superpermutation status.
- Host string — Provides one contiguous sequence in which targets occur. It is covering object. Counterfactual: A set of separate strings is not one superpermutation.
- Substring windows — Witness exact contiguous occurrence of each permutation. It is verification mechanism. Counterfactual: Subsequence occurrence with gaps is insufficient.
- Overlap — Shares suffixes and prefixes among target occurrences. It is compression mechanism. Counterfactual: Concatenation remains valid but often nonminimal.
- Length objective — Orders valid host strings for minimization. It is optimization layer. Counterfactual: Validity does not imply shortest possible length.
What It Is Not¶
- 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.
- Closest near-miss. A concatenation of all permutations is a valid but generally trivial superpermutation; it is a near-miss only for claims of optimality, not validity.
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.
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.
Examples¶
Canonical¶
For symbols 1 and 2, the string 121 contains both required permutation substrings 12 and 21 by a one-symbol overlap.
Mapped back: alphabet → {1,2}; targets → 12 and 21; host → 121; overlap → 1 symbol.
Applied / In Practice¶
Writing all n! permutations end to end always covers the target family but does not exploit prefix–suffix overlap and need not minimize length.
Mapped back: construction → concatenation; coverage → complete; optimality → not established.
Structural Tensions¶
T1 — Coverage Certainty versus Length Compression. Easy concatenation proves existence, while aggressive overlap makes verification and optimization harder.
Diagnostic: Are all target windows certified after compression?
T2 — Construction Record versus Optimality Proof. A short string supplies an upper bound; proving no shorter string exists requires a lower bound.
Diagnostic: Is the result a candidate, bound, or exact minimum?
Structural–Framed Character¶
Coverage and overlap are structural; factorial target families and minimum-length results supply the combinatorial frame.
Structural Core vs. Domain Accent¶
Its core is one word covering many target words. Permutation combinatorics adds n!, relabeling symmetry, overlap graphs, bounds, and exceptional small cases.
Instantiates / Related Primes¶
This entry presupposes Permutation.
-
Approved root. This permutation-covering word has no frozen parent edge.
-
Related — shortest common superstring, universal cycle, permutation, and De Bruijn sequence. They share covering or overlap ideas but use different target and occurrence rules.
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.Every reviewed Superpermutation instance depends on the parent role: the string is defined by containing every permutation of its symbol set as a substring. Removing that role makes the frozen child identity undefined or changes it into a different abstraction. Permutation can occur without Superpermutation, so the relation is dependency rather than subsumption.
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
Not to Be Confused With¶
- Supersequence. Tell: May allow targets as noncontiguous subsequences.
- De Bruijn sequence. Tell: Covers all fixed-length words, usually cyclically.
- Permutation concatenation. Tell: A valid construction, not the definition of minimality.
- Universal cycle. Tell: Uses cyclic windows and may target another object family.
References¶
- Frozen Wikipedia discovery revision: https://en.wikipedia.org/wiki/Superpermutation (revision 1356580025).
- Preserved source candidate: https://oeis.org/A180632/a180632.pdf
- Preserved source candidate: http://www.njohnston.ca/publications/non-uniqueness-of-minimal-superpermutations/
- Preserved source candidate: http://www.gregegan.net/SCIENCE/Superpermutations/Superpermutations.html
- Preserved source candidate: https://warosu.org/sci/thread/S3751105#p3751197
- Preserved source candidate: https://www.quantamagazine.org/sci-fi-writer-greg-egan-and-anonymous-math-whiz-advance-permutation-problem-20181105/
- Preserved source candidate: https://www.theverge.com/2018/10/24/18019464/4chan-anon-anime-haruhi-math-mystery
- Preserved source candidate: https://www.iflscience.com/an-anonymous-online-anime-fan-just-solved-a-problem-thats-been-eluding-mathematicians-for-decades-50364
- Preserved source candidate: http://www.njohnston.ca/2013/04/the-minimal-superpermutation-problem/
The frozen Wikipedia revision is discovery provenance. The retained source set was reviewed for identity, formal or operational relation, and scope. The encyclopedia's structural synthesis is bounded to those claims; a thin authority surface is recorded as a nonblocking source-strengthening repair rather than concealed.