3 ms·
Cool! 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
by aidos 8y ago
Cool!
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.
- superpermutat0r 8y agoIf 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.
- robinhouston 8y agoYes, 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. The construction is described in various places online. I like Greg Egan’s description here: http://www.gregegan.net/SCIENCE/Superpermutations/Superpermutations.html#ALG1 http://www.gregegan.net/SCIENCE/Superpermutations/Superpermu... Sorry for the delayed reply. I was stymied by my aggressive noprocrast setting.
- aidos 8y agoThat's my lunch time reading sorted, thanks!