I’m one of the people who has worked on this problem, and is quoted in the article. Anyone who is seriously interested in this problem may join the group[0] where most of the interested people hang out.
We’re making progress pretty rapidly at the moment. The lower bound has recently been improved (by one), and Greg Egan’s construction has been shown to be the best possible under certain conditions.
I think it’s reasonably likely – though definitely not certain – that we will have a complete solution within weeks.
I played around with this one I found on Reddit's "daily programmer" subreddit a few months back, never found a great approach other than brute force (along with trying to identify unique/expensive sequences).
Do you see it as a variation on the one in the article?
"Given an input set of strings, produce an output string. Every string in the input must be an anagram of some slice of the output. A slice in this context is a series of characters from the string separated by a fixed amount (i.e. anything that can be formed using Python's s[a:b:c] syntax). It's different from a substring in that you're allowed to skip characters, as long as you skip the same number of characters on each step."
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.
In the article they say "The factorial rule predicts that to watch six episodes in every possible order should require 873 episodes, but Houston found a way to do it in 872. And since there is a simple way to convert a short superpermutation on n symbols into a short superpermutation on n + 1 symbols, Houston’s example meant that the factorial rule fails for every value of n above 6 too."
I don't quite get this. Is there an inductive proof you can use as a construction to reduce the length for subsequent N? Would love to see a birds-eye view of the intuition of this.
Yes, there’s a recursive construction that converts a superpermutation of length l on n symbols to a superpermutation of length l + (n+1)! on (n+1) symbols.
If you have the smallest superpermutation for N digits, then you can construct a bigger one by adding the extra digit with a simple rule but it won't be the shortest possible.
It just turned out that the conjecture was easily disproved by that simple rule construction.
We’re making progress pretty rapidly at the moment. The lower bound has recently been improved (by one), and Greg Egan’s construction has been shown to be the best possible under certain conditions.
I think it’s reasonably likely – though definitely not certain – that we will have a complete solution within weeks.
0. https://groups.google.com/forum/?nomobile=true#!forum/superp...