If a television series has three episodes, there are six possible orders in which to view them: 123, 132, 213, 231, 312 and 321. You could put these sequences together to give a list of 18 episodes for every ordering, but there’s a much more efficient way to do it: 123121321. If you want to watch all possible rearrangement of sequences of a 7-part tv series, how many total episode viewings are required? What if the tv show has an infinite number of episodes? A sequence that contains every possible rearrangement (or permutation) of a collection of n symbols is a “superpermutation.”
Progress on this interesting, and easily-understandable 25-year-old combinatorial problem in mathematics has upper- and lower-bound proofs discovered recently by a pair of unexpected authors: an anonymous contributor to 4chan and a science fiction author in Perth Australia.
Some University of Florida math professors, citing "unknown 4chan poster" have verified, clarified, and reformulated a proof for the lower bound to the length of any superpattern. And Greg Egan, the famous SF author, has published a proof for the upper-bound along with C and JavaScript source code implementations of his algorithm.
No comments:
Post a Comment