The Haruhi problem
In: Mathematics
what is the shortest string that contains all permutations of n objects? so suppose n is 3, the possible permutations are
abc, acb, bac, bca,cab,cba so a string with all permutations would be abcacbbacbcacabbca, but thats not the shortest, abcabacba also contains all, but is much shorter (the shortest I belive).
the problem is to find a general solution that gives the min for any number of letters
It’s a problem of finding the minimum length required for a so-called superpermutation on a number of symbols.
A permutation is the mathematical term for a rearrangement. E.g. the permutations of abc, as a sequence of letters, are abc, acb, bac, bca, cab, cba. In general for n (different) symbols, there are n! (read as, n factorial, n! = 1 x 2 x … x n) of them.
A superpermutation on n symbols is a string (sequence of symbols) that contains all possible permutations of them. You can check that abcabacba contains all 6 of the permutations earlier. The length of this string (the number of symbols) is 9, and this is known to be the minimum needed to form a superpermutation.
The superpermutation problem then is to determine in general what this minimum length is, and if possible to find these superpermutations. It remains an open problem for 6 symbols and above.
There has been work in finding lower and upper bounds for this minimum length, so while we still don’t know what the exact minimum lengths are, we know that they are in a certain range. And this is where the reference to Haruhi comes in.
The superpermutatation problem, in the context of trying to watch 14 episodes of Haruhi, was posted on 4chan, and someone posted a proof of the current best-known lower bound. It only came into prominence some 7 years later, after which it was verified and written into papers.
First we have to understand permutations.
Let’s say you have three letters, A, B, and C. How many different ways can you arrange those three letters?
ABC obviously. CBA is another. ACB, BAC, BCA, and CAB are the remaining four. With three items you can arrange or permute them in 6 ways. Add a fourth unique item (say the letter D) and it increases to 24. Add a fifth and it increases to 120. Permutations grow quickly!
Ok so let’s talk about the Haruhi problem. The name comes from an anime series called The Melancholy of Haruhi Suzumiya. The 14 episode first season was aired in a non-linear order (which has some relevance to the nature of the show and its characters). That meant there were at least two ways viewers could later watch the show. They could watch it in the broadcast order or they could watch it in chronological order. But what about other orders? Such as reverse chronological (last episode first, first episode last, etc)? Or reverse broadcast? With 14 episodes there were a LOT of possible orders you could watch the series in. How many? Over 87 billion.
That’s a lot. Watching 87 billion permutations of 14 episodes is obviously impossible. But one anonymous poster on a 4chan message board asked an interesting question:
What is the least number of episodes you would have to watch to have watched in all possible orders?
You COULD (well you really couldn’t but let’s say you lived for a really REALLY long time) watch each 14 episode permutation, but that’s 14 times 87 billion. Surely we can do better!
To see how let’s drop back down to A B C again. Just three items. In fact let’s go even simpler. Just two. A and B. A and B have two permutations: AB and BA. To watch a two episode series in every order you could watch AB then BA right? That’s ABBA (no not the Swedish pop band). But surely you can already see how we can do better. With just ABA (no not the American Bar Association) we cover both AB and BA but only need to watch episode B once.
This minimum set of items that includes every possible permutation as a sub set is called a superpermutation.
For two items the minimum length is 3 (ABA is one, BAB is another)
For three items the minimum length is 9 (ABCABACBA is an example). If you had just jammed all the permutations together you’d have a string of length 18, twice as long!
So what is the answer for 14 items? Aka the Haruhi problem? Well, sadly we don’t know. At least not yet.
It turns out for list of up to 5 items we can easily answer this question. There is a proven formula. But for 6 or more items that formula no longer works, and no one has been able to come up with a different one.
The best that mathematicians have done is come up with limits for some values. By limits they mean “the number is at least this big, but it might be bigger” or “the number is at most this big but it might be smaller”.
What’s interesting is in response to the Haruhi episode question posed above, members of the board where it was posted where able to come up with a formula that sets the lower bound for ANY permutation set size 2 or more.
A formula has also been found that sets an upper bound for superpermutation length for sets with more than 7 items.
As a result we know the upper and lower number for the Haruhi problem. Unfortunately it’s still pretty big. The number of episodes you’d have to watch to cover all permutations is between 93,884,313,611 and 93,924,230,411. Or just under 94 billion episodes. Still that’s better than the non optimized list which is 1,220,496,076,800 episodes long, ie. Over 1.2 trillion.
Better break out the popcorn, this could take awhile.
Latest Answers