Superpermutations

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

Xanthir
My HERO!!!
Posts: 5426
Joined: Tue Feb 20, 2007 12:49 am UTC
Contact:

Superpermutations

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. ^_^
Last edited by Xanthir on Tue Jan 29, 2019 9:09 pm UTC, edited 3 times in total.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

doogly
Dr. The Juggernaut of Touching Himself
Posts: 5538
Joined: Mon Oct 23, 2006 2:31 am UTC
Location: Lexington, MA
Contact:

Re: Superpermutations

If text is more your thang than videos there's a nice writeup here too:
https://www.quantamagazine.org/sci-fi-w ... -20181105/
LE4dGOLEM: What's a Doug?
Noc: A larval Doogly. They grow the tail and stinger upon reaching adulthood.

Keep waggling your butt brows Brothers.
Or; Is that your eye butthairs?

Soupspoon
You have done something you shouldn't. Or are about to.
Posts: 4060
Joined: Thu Jan 28, 2016 7:00 pm UTC
Location: 53-1

Re: Superpermutations

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:

Xanthir
My HERO!!!
Posts: 5426
Joined: Tue Feb 20, 2007 12:49 am UTC
Contact:

Re: Superpermutations

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.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

Who is online

Users browsing this forum: No registered users and 7 guests