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**