wtf thus Superpermutations
- User
wtf thus Superpermutations
Assistant
"WTF is a Superpermutation?" — Great question! Let's break it down in a fun and clear way. 🚀
🔁 What is a Superpermutation?
A superpermutation on n symbols is the shortest possible string that contains every permutation of those n symbols at least once as a substring.
🧠 Example to Understand:
Let’s take
n = 2. The symbols are, say,1and2.The permutations of
[1, 2]are:1221
So a superpermutation for
n=2would be:
👉121or212Why?
- In
121, you can find:12(positions 1–2)21(positions 2–3)
Same with
212.That’s the shortest string that includes all permutations of two elements.
📈 How Big Do Superpermutations Get?
This is where things get weirdly intense.
Naive Approach:
You might think: “Just concatenate all permutations.” But that’s way longer than necessary, since many permutations share overlapping parts.
For example, in
12312, maybe123and231overlap nicely.So mathematicians have been trying to find the shortest such string for each
n.
📐 Known Results:
Here's what we know so far:
n Number of Permutations Length of Minimal Superpermutation 1 1 1 2 2 3 3 6 9 4 24 33 5 120 153 6 720 873 7 5040 5901 These lengths were discovered through a mix of math, programming, and crowd-sourced efforts!
🧵 History & Fun Facts:
-
For years, people thought there was a formula:
And this worked for
n = 1to5. -
But for
n = 6, researchers found a shorter superpermutation than what the formula predicted — breaking the pattern! -
The problem became popular after a 4chan post by an anonymous user gave a correct lower bound proof — which later got picked up by mathematicians!
-
It even caught the attention of Greg Egan, a sci-fi author and amateur mathematician, who contributed new upper bounds.
🤯 Why Is This Important?
- It's a fascinating combinatorics puzzle.
- Has applications in string algorithms, coding theory, and DNA sequencing.
- Shows how sometimes the simplest questions hide mind-bending complexity.
🧩 TL;DR:
A superpermutation is the shortest string that contains every possible rearrangement (permutation) of
nitems at least once. It's surprisingly complex, and solving for largernis still an open problem in math!
Want me to show you how to build one manually for small
n? Or code a generator? 😎
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.