Superpermutations

The generalized case that include sequences with repeated elements[1] are De Bruijn sequences[2]. These are cyclic sequences that contain each possible n-length string using k symbols, each appearing exactly once.

   B(k=3, n=2) = 112132233
   B(k=4, n=2) = 1121314223243344
   B(k=3, n=3) = 111211312212313213322232333

[1] i.e. "111", which isn't a permutation of the set {1, 2, 3}, but can be made from the elements of that set

[2] https://en.wikipedia.org/wiki/De_Bruijn_sequence

I was introduced to this idea on the comp.risks forum, where it was presented as an attack on an answering machine with a 5-digit passcode, which, naively, would require an average of 50,000 guesses of 5 digits each, or 250,000 key presses. But this particular device not only didn't lock out after some number of incorrect guesses, it didn't require a separator character between guesses. It just listened for the correct five digits consecutively, regardless of what you had entered before. So a superpermutation just 153 digits long was sufficient to crack every device.

Greg Egan has some great sci-fi books. Some of the concepts are a little beyond me as he dips into advanced mathematics and physics, but he does a pretty good job of keeping it accessible.

Permutation City, Diaspora, and his various collections of short stories (e.g. Axiomatic, Luminous) are worth reading.

He takes ideas, like what's linked in the OP, and builds worlds and stories around them in terms of their implications and impacts on society and individuals.

In case you just came to read the comments (as I often do) - this page links to discussions by Egan on a ton of other interesting topics like some special cases of general and special relativity, unusual orbits, and higher-dimensional geometry. Pretty cool stuff!

Yesterday I came across this interesting result dealing with shortest number with the digits 1 through 7 arranged in all possible orders, thanks to John Baez on twitter [1]. Great to discover this here.

De Brujin sequences as mentioned in one of the comments deals with the generalized case involving repetition as well. There is an interesting mnemonic for remembering the composition of different "ganas" (syllabic units) in Sanskrit poetry that is an example of De Brujin sequence - Ya-Maa-Taa-Raa-Ja-Bhaa-Na-Sa-La-Gam . In Sanskrit metre, syllables can be either long (Maa for example) or short (Ma). The basic units are composed of 3 syllables and thus 2x2x2 = 8 possible types - long-short-long for example. These basis units are called ganas and have a name attached to them. The mnemonic helps one decode the composition of a gana. If you want to know the composition of "Ja Gana" for example, go to the part that starts with Ja and get the substring with three syllables starting with Ja i.e Ja-Bhaa-Na. Since these syllables are short, long and short, Ja Gana corresponds to short, long and short.

[1] https://twitter.com/johncarlosbaez/status/105338502434972057...

Edit: Formatting and correction

Not sure how much it could add to the conversation, but I implemented a library to find almost minimal superpermutations in go a while back. Uses a technique I didn't see anywhere else.

https://github.com/g-harel/superpermutations

The original link is inaccessible to me; alternate link: http://members.iinet.net.au/~gregegan@netspace.net.au/SCIENC...