thumb|The distribution of permutations in a 3-symbol superpermutation In combinatorial mathematics, a superpermutation on n symbols is a string that contains each permutation of n symbols as a substring. While trivial superpermutations can simply be made up of every permutation concatenated together, superpermutations can also be shorter (except for the trivial case of n = 1) because overlap is allowed. For instance, in the case of n = 2, the superpermutation 1221 contains all possible permutations (12 and 21), but the shorter string 121 also contains both permutations.
Article · 中文
在组合数学中，n 个符号的超排列（Superpermutation）是一个字符串，使得n 个符号的所有排列均为它的子串。这些子串可以互相重叠。对于任意一个指定的 n，超排列的长度存在一个最小值，最短的超排列称为最小超排列。 在 1≤ n ≤5 时，n 个符号的最小超排列的长度是1! +2! +...+ n!，分别是1、3、9、33和153（OEIS數列），与之对应的字符串分别是1、121、123121321、123412314231243121342132413214321，以及： 123451234152341253412354123145231425314235142315423124531243512431524312543121345213425134215342135421324513241532413524132541321453214352143251432154321
Abstract from DBpedia / Wikipedia · CC BY-SA