The Haruhi problem
In: Mathematics
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