superperm

A related interesting problem is superpermutations [1]. This is the same problem that an anonymous 4chan poster helped bring some light to lower bounds on shortest superpatterns [2]. The Google group is worth a shout for their efforts [3]. Surprisingly, we only have optimal superpermutations for really low values on N [4]. I tried my hand at auto-generating symmetric patterns (which turn out to not be optimal after some value of N (6?)), but the problem is quite tough. Currently the best approaches appear to be achieved by using a TSP solver. [1] https://www.gregegan.net/SCIENCE/Superpermutations/Superperm... [2] https://oeis.org/A180632/a180632.pdf [3] https://groups.google.com/g/superpermutators [4] https://github.com/superpermutators/superperm/tree/master/su...

The technique may be different, but the results seem to be identical to what you get from the standard method e.g. described in Section 2 of http://www.njohnston.ca/wp-content/uploads/2013/03/minimal_s...; or section 1 of https://arxiv.org/pdf/1408.5108.pdf; or as implemented by https://github.com/superpermutators/superperm/blob/master/bi... This method produces superpermutations of length 1! + 2! + ... + n!, which was believed for a long time to be the best possible. But Greg Egan’s new result shows it’s possible to do a lot better than that.