Slashdot Mirror
Mystery Math Whiz and Novelist Advance Permutation Problem (quantamagazine.org)
A new proof from the Australian science fiction writer Greg Egan and a 2011 proof anonymously posted online are now being hailed as significant advances on a puzzle mathematicians have been studying for at least 25 years. Erica Klarreich, writing for Quanta Magazine: On September 16, 2011, an anime fan posted a math question to the online bulletin board 4chan about the cult classic television series The Melancholy of Haruhi Suzumiya . Season one of the show, which involves time travel, had originally aired in nonchronological order, and a re-broadcast and a DVD version had each further rearranged the episodes. Fans were arguing online about the best order to watch the episodes, and the 4chan poster wondered: If viewers wanted to see the series in every possible order, what is the shortest list of episodes they'd have to watch? In less than an hour, an anonymous person offered an answer -- not a complete solution, but a lower bound on the number of episodes required. The argument, which covered series with any number of episodes, showed that for the 14-episode first season of Haruhi, viewers would have to watch at least 93,884,313,611 episodes to see all possible orderings. "Please look over [the proof] for any loopholes I might have missed," the anonymous poster wrote.
The proof slipped under the radar of the mathematics community for seven years -- apparently only one professional mathematician spotted it at the time, and he didn't check it carefully. But in a plot twist last month, the Australian science fiction novelist Greg Egan proved a new upper bound on the number of episodes required. Egan's discovery renewed interest in the problem and drew attention to the lower bound posted anonymously in 2011. Both proofs are now being hailed as significant advances on a puzzle mathematicians have been studying for at least 25 years. Mathematicians quickly verified Egan's upper bound, which, like the lower bound, applies to series of any length. Then Robin Houston, a mathematician at the data visualization firm Kiln, and Jay Pantone of Marquette University in Milwaukee independently verified the work of the anonymous 4chan poster. Now, Houston and Pantone, joined by Vince Vatter of the University of Florida in Gainesville, have written up the formal argument. In their paper, they list the first author as "Anonymous 4chan Poster."
The proof slipped under the radar of the mathematics community for seven years -- apparently only one professional mathematician spotted it at the time, and he didn't check it carefully. But in a plot twist last month, the Australian science fiction novelist Greg Egan proved a new upper bound on the number of episodes required. Egan's discovery renewed interest in the problem and drew attention to the lower bound posted anonymously in 2011. Both proofs are now being hailed as significant advances on a puzzle mathematicians have been studying for at least 25 years. Mathematicians quickly verified Egan's upper bound, which, like the lower bound, applies to series of any length. Then Robin Houston, a mathematician at the data visualization firm Kiln, and Jay Pantone of Marquette University in Milwaukee independently verified the work of the anonymous 4chan poster. Now, Houston and Pantone, joined by Vince Vatter of the University of Florida in Gainesville, have written up the formal argument. In their paper, they list the first author as "Anonymous 4chan Poster."
By concatenating the series, additional ones are created, so it's less than 14!. E.g. first watching 1..14, then 1..12,14,13 (the last two switched), you would actually also see 2..14,1, and 3..14,1,2 and 4..15,1..3. So it's definitely less than 14! due to new combinations being creating when concatenating the single series.
Imagine there are 3 episodes. Possible orders are 123, 132, 213, 231, 312, 321. As you say, 3! = 6 orders. But if I watch the episodes 1231321312 I've covered all six in an overlapping way. Is this the shortest way? I don't know. I'd probably check it exhaustively. That'll work up to some fairly short length where the number of combinations get crazy.
Strange women lying in ponds distributing swords is no basis for a system of government.
You already fail at n=2: just watch 1,2,1.
Imagine there are 3 episodes. Possible orders are 123, 132, 213, 231, 312, 321. As you say, 3! = 6 orders. But if I watch the episodes 1231321312 I've covered all six in an overlapping way.
If memory serves (it's been 30 years) these are called tuples, and can be handy as hell. I had a friend who forgot her answering machines login, took me 5-10 minutes to break into it (3 digits).
They are called permutations and the shortened sequence is a superpermutation. The superpermutations are constructed via an asymmetric version of the Traveling Salesman Problem. Basically the tails of some permutation can do double duty by serving also as the head of the next permutation. Tuples are simply typed lists of data e.g. a database row. A fixed size list of integers is a tuple but so is 121 which isn't a permutation.
"Those that start by burning books, will end by burning men."
Excellent explanation. To answer the question you only sort of asked, it's not the shortest way. No matter which of the 6 possible orders you start with, the best you can get is a list 9 elements long. Optimal would be 8 elements (the initial 3 you decide to start with, then 1 more from each of the other 5) but no matter which order you start with it wants to repeat that initial order on the 3rd addition.
For example 123 should be followed by 231 resulting in 1231. Follow that with 312 for 12312. Next should be 123, but you started with that, so next-best-thing would be 213 for 1231213. Then 132 followed by 321 to get 123121321, one of the 9 element solutions.
Sorta related, but not the same. De Bruijn sequences contain all possible strings of length n using an alphabet of size k, whereas this is about the shortest string that contains all possible permutations of the string 123...n
E.g., if n = 2 and the alphabet contains "1" and "2" (k = 2), a De Bruijn sequence would be 1122, which contains 11, 12, 22, and 21 (it wraps around. 11221 if you want to make it explicit.).
But for this problem, if n = 2, the shortest sequence is 121, which contains 12 and 21. It doesn't need to contain 11 or 22, because those aren't permutations of 12.
Or, altenatively, you're an idiot.
Not because you misunderstood, but because you didn't even consider that you might have misunderstood.
14! is the total number of permutations, but each permutation contains 14 items, so you should be comparing the new lower bound - 93,884,313,611 - with 14 * 14!, which is 1,220,496,076,800.
systemd is Roko's Basilisk.