Problem dossier · Combinatorics
Superpermutation problem
What is the shortest string over n symbols containing every permutation of them as a consecutive substring? Known exactly only for n ≤ 5.
§1
Status
Open for n ≥ 6: the n = 6 answer lies between 867 and 872 (lower bound via the Haruhi/4chan argument, upper via Egan's construction).
Think you can crack this one? Read the playbook before you announce →
§2
The Angle of Attack
TSP-style and evolutionary search for shorter n = 6 strings; probe the structure of Egan's constructions for improvements at n = 7–8.
Tags: permutations · strings · tsp · search
§3
The Lab
No instruments built yet. When this problem gets tackled, its interactive instruments — explorers, searches, verifiers running in the browser — live here. See the Collatz dossier for what a fully tackled problem looks like.
§4
The Log
Empty. Work on this problem gets logged here as dated entries — constructions tried, code run, dead ends included. Dead ends are results.
§5
Related Problems
More open problems in Combinatorics and adjacent territory.
- 1/3–2/3 conjecture — Combinatorics
- Dedekind numbers — Combinatorics
- Sunflower conjecture — Combinatorics
- Van der Waerden numbers — Combinatorics
- Minimal superpermutations — extended search — Algorithms & Simulation
- Heuristics vs. exact methods on NP-hard problems — Algorithms & Simulation