https://mzh.moegirl.org.cn/zh/%E5%87%89%E5%AE%AB%E6%98%A5%E6%97%A5%E9%97%AE%E9%A2%98中給出了這個問題的一些介紹，實質上是要找一段數(shù)字串，使1到n的所有排列都能在這個數(shù)字串中找到（必須是數(shù)字串中連續(xù)的n個數(shù)組成的排列），并稱這組數(shù)字串為n（個元素）的超排列，并得出超排列的中數(shù)字個數(shù)的最小值。雖然這個問題直今仍無答案，但

先把(n-1)的超排列按照出現(xiàn)順序依次列出所有1到(n-1)的排列（拆），并分別復制一份排列，再在兩個相同的排列間插入n最后連接起來，并去掉重疊部分（一開始怎么拆現(xiàn)在就怎么拼）。

此時n的超排列比n-1的超排列多了幾個數(shù)呢？

稍微想一下就行。

………

……

…

公布答案:n!

這個過程相當于原本拆開產生的數(shù)又在拼接時去除，數(shù)的個數(shù)不變。而在兩者之間，復制出了(n-1)!個1到(n-1)的排列，每個排列有(n-1)個數(shù)此外還有添加的(n-1)個數(shù)字n，所以多出數(shù)字的總個數(shù)就是：

容易看出n=1時最短（數(shù)字個數(shù)最少）超排列長度（數(shù)字個數(shù)）是1。根據(jù)我在研二時研究出的遞歸法易得，n的這種超排列長度為

（還有一種構造這種超排列的方法就是，先列出一種排列，再把它的前m個數(shù)字先倒序再排在后面，出現(xiàn)一個新的排列，其中m要盡量小，一直排下去，直到所有排列都出現(xiàn)為止，這種構造法在m=1,2時和之后證明最短超排列長度下限的2-環(huán)是一樣的）

根據(jù)上面的鏈接，得知最短超排列長度存在上限和下限，上限是

下面是上限超排列的構造方法，JavaScript代碼如下

http://www.gregegan.net/SCIENCE/Superpermutations/SuperPermutations.c

最短超排列長度下限：

它們的證明過程都在最上面的鏈接的網頁的鏈接中。

它們是如何被證出的？

讓二年級的我來解釋一下上面的過程。

首先要知道超排列中的一些術語：

1-邊：把某個排列的第一個數(shù)Ctrl+C&Ctrl+V到最后面。

2-邊：把某個排列的前二個數(shù)Ctrl+C&交換位置（倒序）&Ctrl+V到最后面。

1-環(huán)：對于n的超排列的某個排列，連續(xù)作(n-1)次1-邊，這n個排列是1到n的一個環(huán)排列。

2-環(huán)：對于n的超排列的某個排列，連續(xù)作(n-2)（以上）次1-環(huán)和2-邊。

從一個排列開始，在最后一個數(shù)的后面加各種各樣的“邊”（不一定是1-邊或2-邊），每次加“邊”后，最后n（n的超排列）個數(shù)是一個新的排列，在中間沒有排列（如果有就把“邊”拆分）。我們要找到總長度最短的“邊”，對應的就是最短超排列。

好，我們的準備工作已經全部完成了，接下來證明。。。