Skip to content
TheChatArchiveThe Chat Archive
Qwenqwen3-235b-a22b-no-thinking· Alibaba (Qwen)Hugging Face LMArena Human Preference 140K

wtf thus Superpermutations

From a Chatbot Arena battleThe same person sent this prompt to two anonymous models at once. Compare it with o4-mini-2025-04-16’s answer.
  1. User

    wtf thus Superpermutations

  2. Qwen 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, 1 and 2.

    The permutations of [1, 2] are:

    • 12
    • 21

    So a superpermutation for n=2 would be:
    👉 121 or 212

    Why?

    • 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, maybe 123 and 231 overlap nicely.

    So mathematicians have been trying to find the shortest such string for each n.


    📐 Known Results:

    Here's what we know so far:

    nNumber of PermutationsLength of Minimal Superpermutation
    111
    223
    369
    42433
    5120153
    6720873
    750405901

    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:

      n!+(n−1)!+(n−2)!+⋯+1!n! + (n-1)! + (n-2)! + \dots + 1!

      And this worked for n = 1 to 5.

    • 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 n items at least once. It's surprisingly complex, and solving for larger n is still an open problem in math!


    Want me to show you how to build one manually for small n? Or code a generator? 😎

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.