Page 1 of 1

Superpermutations

Posted: Tue Jan 29, 2019 5:10 pm UTC
by Xanthir
https://www.youtube.com/watch?v=OZzIvl1tbPo

In this video, Matt Parker talks about superpermutations; that is, a string of symbols from an alphabet, containing as substrings every permutation of the alphabet. That is, given A, B, and C, the smallest superpermutation is ABCABACBA - you can find all six permutations of A, B, and C as substrings in it, and there is no smaller string with this property.

There's a ton we don't know about superpermutations. We have an algorithm that can generate them quickly, and it finds the shortest string for 3 (length 9), 4 (length 33), and 5 (length 153) letters. (Interestingly, while the 2, 3, and 4-letter alphabets have unique shortest superpermutations, 5 letters has *8* equally-shortest superperms. One is a letter-swap of the one the algorithm finds, but the other six appear to have no relation to the algo-generated one; they were found by exhaustive computer search instead.)

At 6 letters, tho, the algorithm generates a length 873 superpermutation, but it turns out there's an unrelated length 872 one, found by computer search. (The guy interviewed in the video, Robin Houston, was the first to discover it.)

The even more interesting part, tho, is that recently we've gotten novel upper and lower bounds for the length of shortest superpermutation for a given alphabet: the lower bound was proven in 2011 by an anonymous 4-chan poster in a thread about anime, and just "discovered" by the wider mathematical world in the last few months (Houston ended up writing up the anon's result in an official paper; anon has first credit in the author bylines. It was generally accepted as a valid proof just last week or so.); the new upper bound was also proven just a few weeks ago by Greg Egan (famed sci-fi author, and amateur mathematician). Egan actually discovered a new, more efficient algorithm for constructing superpermutations, and it happens that the length it generates is lower than the previously-believed upper bound. We know this still isn't optimal, because it finds a length 873 superpermutation for 6 letters, but as previously stated Houston found a length 872 one. Houston believes they can improve Egan's algorithm by 1, so it will generate the 872 and be the current best at all lengths.

This was just real cool and I thought I should share. ^_^

Re: Superpermutations

Posted: Tue Jan 29, 2019 7:40 pm UTC
by doogly
If text is more your thang than videos there's a nice writeup here too:
https://www.quantamagazine.org/sci-fi-w ... -20181105/

Re: Superpermutations

Posted: Tue Jan 29, 2019 11:52 pm UTC
by Soupspoon
PTW, and to later remember to watch/read the resources in here, but I'm wondering if some 'gray code'ish list of single-swap permutations* can be farmed by a pattern of picks to generate superpermutations, taking elements 2…last of one roving pointer's permutation and handing over to the next pointer that's handily matching with the permutation with elements 1…penultimate.

Off the top of my head. There's probably more effort needed to find the generalised case (if it exists) than is saved by deriving from it.


* Or this:
Image

Re: Superpermutations

Posted: Wed Jan 30, 2019 5:19 pm UTC
by Xanthir
Yeah, that's the basis of Houston's translation of the problem to the TSP, which let him discover the 6-letter length-872 example. He constructs a complete directed graph of all the permutations, assigning each edge a weight according to how many letters you need to add to the growing superpermutation to add the next item (so ABC -> BCA is weight 1, ABC -> CAB is weight 2, ABC -> BAC is weight 3), then finds a minimum-weight Hamiltonian path (aka the Traveling Salesman Problem).

So most of the algorithm is just chasing down the weight-1 edges around subgraphs, and occasionally using a higher-weight edge to jump to a new subgraph.

This basic concept is also what's used by Egan and Anon for both of their bounds proofs; doogly's link talks about it a little more.