Searching for palindromic superpermutations

A superpermutation is a string of numbers that contains every permutation of those numbers. For example, ‘123121321’ contains all six permutations of three numbers:

One way to construct a superpermutation is to concatenate all N! permutations together but this is wasteful. We’d end up with a string of length 18 instead of 9:

The trick is to try and overlap permutations as much as possible. Most of the time, when we add a character this also add a permutation, but not always. A ‘greedy’ algorithm works fairly well to find short strings, but they might not be optimal.

So the question is: how short can these strings be?

Many people are trying to figure that out, either constructively, by exhaustive search for the shortest string, or non-constructively, by proof of its exact length. Ideally, we’d come up with an efficient process to build the shortest possible string.

I’m certainly no mathematician so I won’t tackle a proof, but I do know some things about writing efficient search algorithms. In this article I’ll explain my recent attempt to find minimal superpermutations - in this case, those that happen to be palindromes.

Along the way I wrote some C and Rust code. I’ll focus on the high-level approach in this article and save a detailed walk-through of the code for the next.

In general, minimal superpermutations need not be palindromes. It so happens for N=1 to 4 they are, but no one has proved whether or not this is always true. In fact, for N=5 there are eight shortest strings tied at 153 characters - one of which is a palindrome.

I decided to limit my search to palindromes because I think there’s fair chance the shortest superpermutation is a palindrome and this lets us reduce the search space, making the problem more tractable. Otherwise, the search might never finish.

Actually, I wholly expect the search not to finish anyway - even with this limitation. I’m going to run it for a month or two on the N=6 problem to see how far it gets, but I have low expectations. The combinatorial abyss is vast and unforgiving.

There’s one more assumption I’m going to make about minimal superpermutations. That is: they do not contain the same permutation more than once. In other words, each and every permutation appears exactly once in the string, with no repetition.

Again, there’s no proof of this, but there’s mounting evidence this is the case. For the N=6 problem, more than ten thousand strings have been found with the shortest known length of 872. As far as I’m aware none of these repeat a permutation.

With this assumption in place, we can prune strings from our search that contain repetition - reducing the search space. This improves our chances of success.

At a high level, the algorithm works by searching for the shortest string that contains exactly half the permutations. This string must also have the special property that its reversal contains precisely the other half of the permutations (the ones it’s missing).

When this string is glued together with its reversal, it forms a palindrome that is a superpermutation - a string that contains all N! permutations.

For example, ‘12312’ contains 123, 231 and 312 which are three of the six permutations for N=3. Its reversal ‘21321’ contains 213, 132 and 321 which are precisely the other three permutations it’s missing so it has the property we want.

That means we can glue ‘12312’ and ‘21321’ together to obtain ‘123121321’ which now contains all N! permutations - making a (palindromic) superpermutation.

The search is depth first, starting from the 12...N permutation. This can be thought of as the root node of a search tree. At each step, we ‘expand’ one string by adding a single character to the end of it. This adds a child node to the search tree.

From Wikipedia: “A depth-first search explores as far as possible along each branch before backtracking.” When we translate that definition to this problem, it means we should expand longer and longer strings before backtracking to expand shorter ones:

                1234                /  \             12341  (not expanded yet)             /          123412          /      1234121       /     ...

There’s still the question of when to backtrack. This is where our ‘No repeats’ assumption comes into play. When a string is expanded, we check:

1. Is the tail of the string a permutation?
2. If so, have we seen it before?

If the answer is yes we backtrack. There’s no point expanding the string further since we’re not interested in superpermutations that contain repetition.

However, we can go one step further! We know we’re going to glue this string to its reversal. That means all permutations seen so far will be seen again - but in reverse. Our assumption is each permutation appears once in the entirety of the string.

That means we can check the tail of the string a second time. If we’ve seen its reversal before we can backtrack as well. This pre-empts the repetition that would occur when the string is glued later. This lets us eliminate even more strings!

Here’s what the code might look like:

if permutations_seen[tail_of_string] {  return; // backtrack}tail_of_string.reverse();if permutations_seen[tail_of_string] {  return; // backtrack}

I think of this as the magic of this approach. It’s this combination of ideas that initially motivated me to try writing the search algorithm. Whether or not it makes a significant dent in the problem remains to be seen but it’s worth a shot.

Finally, there’s one last piece we need to supercharge the search algorithm.

The search incorporates a clever technique devised by Benjamin Chaffin. The basic idea is to break the problem into a sequence of subproblems. We can then use the solution to the first subproblem to speed up solving the second, and so on.

Each subproblem is stated in terms of ‘wasted’ characters. A wasted character is one that doesn’t add a new permutation itself but instead, prepares the string so the next character can add a permutation. Sometimes more than one in a row is needed.

For example, when ‘1’ is appended to ‘12312’ we get ‘123121’. The ‘1’ character is deemed wasted because it doesn’t add a new permutation to the string. It does however prepare the string for a subsequent ‘3’ which adds the 213 permutation.

Now that we understand wasted characters, subproblems are defined as:

How many permutations can fit into a string that has W wasted characters?

The algorithm starts by solving the W=0 case by depth-first search. It enumerates all strings that do not waste any characters and counts how many permutations appear in them. The maximal count of permutations is the solution of the subproblem.

The algorithm proceeds to solve the W=1 subproblem, using the solution of W=0 to speed up the search. This works by pruning strings that can’t possibly produce a maximal count of permutations because they’ve already wasted too many characters.

For example, when solving W=1, if we’ve seen ‘12312132’ which contains five permutations, there’s no point expanding ‘1232’ because we know from W=0 this string is doomed to failure. It can’t possible beat the string with five permutations.

We then proceed to solve W=2, W=3 and so on. At each step we refer back to all previous solutions to prune the search. The code looks something like this:

let surplus_waste = W - current_waste;let max_perms = subproblem_solutions[surplus_waste];let best_perms = current_perms + max_perms;if best_perms <= *best_seen_so_far {  return; // prune this string}

A (contrived) analogy is to imagine climbing a ladder. The search algorithm is working on one of the rungs and is supported by preceding rungs to get its job done.

The addition of Chaffin’s method has a dramatic impact on the effectiveness of the search. For N=5, the search completes almost instantly. Without this code, it grinds to a halt. It would likely take a very long time to finish the search.

In part two I’ll walk through the code and go into much more detail about how the algorithm actually works. I haven’t written part two yet so check back in a couple of weeks. I’ll also announce its publication on Twitter.

If you can’t wait, the latest iteration of my (scrappy) code is here.