Interesting problem! It’s a variant of the Shortest Superstring Problem, which is known to be NP-hard. I bet this variant is NP-hard as well. Obviously that do

Interesting problem! It’s a variant of the Shortest Superstring Problem, which is known to be NP-hard. I bet this variant is NP-hard as well. Obviously that doesn’t mean we can’t find nice algorithms that work well in particular cases, but I bet it’s hard to prove that a solution is the best possible. What makes the minimal superpermutation problem different is that we’re trying to pack together the set of ALL permutations of some number of symbols, so the set of strings has a lot of known symmetry and structure we can take advantage of. In this case I hope it will be possible to find a general solution that we can prove is the best possible.