On the superpermutations of the family of multisets [1, 1, n]

Inspection of the preliminary results for this family which we discovered last time reveals that some of the minimal-length superpermutations of the multisets [1, 1, 2] and [1, 1, 5] are palindromic.

Conveniently, a brute-force search of the space of possible palindromic superpermutations is considerably faster than a brute-force search of the entire superpermutation space. This is because it is only necessary to find a string which contains half of the full set of permutations (eliminating mirrored pairs of permutations), which can then be mirrored to produce to the second half of a palindromic superpermutation. This requires checking (n/2)! orders in which to combine 2^(n/2) possible subsets of the full set of n permutations, but since the exponential function grows much slower than the factorial function, this turns out to be a net win.

It turns out that all members of this family have palindromic optimal superpermutations of a common form (some have multiple palindromic superpermutations). For n=1 through 9, the relevant results are as follows:

(Note that these examples have all undergone rewriting to ensure that digits have their initial appearances in increasing order, and the palindromic suffix is marked out with brackets.)

[1,1,1]: 12312[1321]
[1,1,2]: 112311213[12113211]
[1,1,3]: 11123111213112[1131211132111]
[1,1,4]: 11112311112131112113[1121113121111321111]
[1,1,5]: 111112311111213111121131112[11131121111312111113211111]
[1,1,6]: 11111123111111213111112113111121113[1112111131121111131211111132111111]
[1,1,7]: 11111112311111112131111112113111112111311112[1111311121111131121111113121111111321111111]
[1,1,8]: 111111112311111111213111111121131111112111311111211113[11112111113111211111131121111111312111111113211111111]
[1,1,9]: 11111111123111111111213111111112113111111121113111111211113111112[1111131111211111131112111111131121111111131211111111132111111111]

Each of these starts with n ones, followed by repetitions of the following pattern:

'2' '1'{0} '3' '1'{n-0} '2' '1'{1} '3' '1'{n-1} '2' '1'{2} '3' '1'{n-2}...

I.e., alternating '2's followed by x '1's, and '3's followed by n-x '1's, with x increasing by one in each chunk of symbols, up to n-1 chunks of ones.

This leads to a straightforward O(n^2) algorithm (because the final length is of order n^2, so it takes at least that much time to output the entire string) for generating minimal superpermutations of any multiset in the family [1, 1, n], with O(1) complexity for generating each subsequent symbol incrementally, with the lengths tightly following the previously determined lower bound for this family:

k = 2n + (n+1)(n+2) + 1