324:, the problem was presented on the imageboard as "The Haruhi Problem": if you wanted to watch the 14 episodes of the first season of the series in every possible order, what would be the shortest string of episodes you would need to watch? The proof for this lower bound came to the general public interest in October 2018, after mathematician and computer scientist Robin Houston tweeted about it. On 25 October 2018, Robin Houston, Jay Pantone, and Vince Vatter posted a refined version of this proof in the
20:
126:
186:
For example, a superpermutation of order 3 can be created from one with 2 symbols; starting with the superpermutation 121 and splitting it up into the permutations 12 and 21, the permutations are copied and placed as 12312 and 21321. They are placed together to create 1231221321, and the identical
210:
associated with it; the weight is calculated by seeing how many characters can be added to the end of one permutation (dropping the same number of characters from the start) to result in the other permutation. For instance, the edge from 123 to 312 has weight 2 because 123 + 12 = 12312 = 312. Any
332:). For "The Haruhi Problem" specifically (the case for 14 symbols), the current lower and upper bound are 93,884,313,611 and 93,924,230,411, respectively. This means that watching the series in every possible order would require about 4.3 million years.
99:= 5, there are several smallest superpermutations having the length 153. One such superpermutation is shown below, while another of the same length can be obtained by switching all of the fours and fives in the second half of the string (after the bold
179:
is split into its individual permutations in the order of how they appeared in the superpermutation. Each of those permutation are then placed next to a copy of themselves with an
187:
adjacent 2s in the middle are merged to create 123121321, which is indeed a superpermutation of order 3. This algorithm results in the shortest possible superpermutation for all
95:). The first four smallest superpermutations have respective lengths 1, 3, 9, and 33, forming the strings 1, 121, 123121321, and 123412314231243121342132413214321. However, for
264:
781:
726:
492:
177:
151:
62:
superpermutations can simply be made up of every permutation concatenated together, superpermutations can also be shorter (except for the trivial case of
183:
th symbol added in between the two copies. Finally, each resulting structure is placed next to each other and all adjacent identical symbols are merged.
873:
670:
477:
325:
92:
117:> 5, a smallest superpermutation has not yet been proved nor a pattern to find them, but lower and upper bounds for them have been found.
70:= 2, the superpermutation 1221 contains all possible permutations (12 and 21), but the shorter string 121 also contains both permutations.
897:
400:− 3) − 1, which was a new record. On 27 February 2019, using ideas developed by Robin Houston, Egan produced a superpermutation for
215:
through the created graph is a superpermutation, and the problem of finding the path with the smallest weight becomes a form of the
110:
1345213425134215342135421324513241532413524132541321453214352143251432154321
106:
1234512341523412534123541231452314253142351423154231245312435124315243125431
805:
Aaron, Williams (2013). "Hamiltonicity of the Cayley
Digraph on the Symmetric Group Generated by σ = (1 2 ... n) and τ = (1 2)".
892:
448:
Ashlock, Daniel A.; Tillotson, Jenett (1993), "Construction of small superpermutations and minimal injective superstrings",
380:≥ 7. However, on 1 February 2019, Bogdan Coanda announced that he had found a superpermutation for n=7 of length 5907, or (
328:(OEIS). A published version of this proof, credited to "Anonymous 4chan poster", appears in Engen and Vatter (
742:
207:
199:
629:
515:
216:
43:
59:
598:
902:
829:
486:
203:
222:
537:
129:
A diagram of the creation of a superpermutation with 3 symbols from a superpermutation with 2 symbols
429:
321:
806:
751:
553:
527:
434:
19:
867:
720:
761:
561:
545:
457:
341:
212:
877:
675:
565:
461:
349:
316:
279:
156:
697:
Anonymous 4chan poster; Houston, Robin; Pantone, Jay; Vatter, Vince (October 25, 2018).
541:
468:
Anonymous 4chan Poster; Houston, Robin; Pantone, Jay; Vatter, Vince (October 25, 2018).
404:= 7 of length 5906. Whether similar shorter superpermutations also exist for values of
191:
less than or equal to 5, but becomes increasingly longer than the shortest possible as
136:
408:> 7 remains an open question. The current best lower bound (see section above) for
886:
28:
557:
421:
345:
861:
766:
648:
340:
On 20 October 2018, by adapting a construction by Aaron
Williams for constructing
847:
125:
47:
31:
549:
836:
671:"Sci-Fi Writer Greg Egan and Anonymous Math Whiz Advance Permutation Problem"
353:
55:
133:
One of the most common algorithms for creating a superpermutation of order
740:
Engen, Michael; Vatter, Vincent (2021), "Containing all permutations",
698:
469:
630:"An anonymous 4chan post could help solve a 25-year-old math mystery"
376:− 3. Up to 2018, these were the smallest superpermutations known for
811:
266:
was found using a computer search on this method by Robin
Houston.
756:
274:
In
September 2011, an anonymous poster on the Science & Math ("
532:
311:
283:
124:
18:
830:
The
Minimal Superpermutation Problem - Nathaniel Johnston's blog
219:. The first instance of a superpermutation smaller than length
206:
and every permutation is connected by an edge. Each edge has a
153:
is a recursive algorithm. First, the superpermutation of order
23:
The distribution of permutations in a 3-symbol superpermutation
320:, particularly the fact that it was originally broadcast as a
66:= 1) because overlap is allowed. For instance, in the case of
356:
devised an algorithm to produce superpermutations of length
198:
Another way of finding superpermutations lies in creating a
870:
by Robin
Houston, which brought attention to the 4chan post
87:
699:"A lower bound on the length of the shortest superpattern"
470:"A lower bound on the length of the shortest superpattern"
876:
about the problem of finding short superpermutations in
782:"4chan Just Solved A Decades-Old Mathematical Mystery"
225:
159:
139:
424:, a permutation that contains each permutation of
258:
171:
145:
516:"Non-uniqueness of minimal superpermutations"
286:proved that the smallest superpermutation on
8:
352:, science fiction author and mathematician
725:: CS1 maint: numeric names: authors list (
592:
590:
588:
586:
584:
582:
491:: CS1 maint: numeric names: authors list (
329:
810:
765:
755:
531:
478:On-Line Encyclopedia of Integer Sequences
437:, a similar problem with cyclic sequences
326:On-Line Encyclopedia of Integer Sequences
224:
158:
138:
275:
506:
718:
484:
77:≤ 5, the smallest superpermutation on
669:Klarreich, Erica (November 5, 2018).
514:Johnston, Nathaniel (July 28, 2013).
7:
664:
662:
623:
621:
619:
270:Lower bounds, or the Haruhi problem
647:Anon, - San (September 17, 2011).
310:− 3. In reference to the Japanese
14:
837:"Superpermutations - Numberphile"
317:The Melancholy of Haruhi Suzumiya
81:symbols has length 1! + 2! + … +
862:The original 4chan post on /sci/
259:{\displaystyle 1!+2!+\ldots +n!}
73:It has been shown that for 1 ≤
780:Spalding, Katie (2018-10-30).
597:Egan, Greg (20 October 2018).
1:
767:10.1080/00029890.2021.1835384
743:American Mathematical Monthly
649:"Permutations Thread III ニア愛"
202:where each permutation is a
16:String in combinatorial math
919:
550:10.1016/j.disc.2013.03.024
217:traveling salesman problem
898:Enumerative combinatorics
294:≥ 2) has at least length
121:Finding superpermutations
864:, archived on warosu.org
893:Combinatorics on words
450:Congressus Numerantium
260:
195:increase beyond that.
173:
147:
130:
24:
261:
174:
148:
128:
22:
520:Discrete Mathematics
223:
157:
137:
628:Griggs, Mary Beth.
599:"Superpermutations"
542:2013arXiv1303.4150J
430:permutation pattern
412:= 7 is still 5884.
322:nonlinear narrative
172:{\displaystyle n-1}
46:that contains each
435:De Bruijn sequence
256:
169:
143:
131:
25:
526:(14): 1553–1557.
342:Hamiltonian paths
146:{\displaystyle n}
113:For the cases of
910:
858:
856:
854:
841:
817:
816:
814:
802:
796:
795:
793:
792:
777:
771:
770:
769:
759:
737:
731:
730:
724:
716:
714:
712:
703:
694:
688:
687:
685:
683:
666:
657:
656:
644:
638:
637:
625:
614:
613:
611:
609:
594:
577:
576:
574:
572:
535:
511:
496:
490:
482:
474:
464:
265:
263:
262:
257:
213:hamiltonian path
178:
176:
175:
170:
152:
150:
149:
144:
90:
36:superpermutation
918:
917:
913:
912:
911:
909:
908:
907:
883:
882:
878:Quanta Magazine
852:
850:
839:
834:
826:
821:
820:
804:
803:
799:
790:
788:
779:
778:
774:
739:
738:
734:
717:
710:
708:
701:
696:
695:
691:
681:
679:
676:Quanta Magazine
668:
667:
660:
646:
645:
641:
627:
626:
617:
607:
605:
596:
595:
580:
570:
568:
513:
512:
508:
503:
483:
472:
467:
447:
444:
442:Further reading
418:
350:symmetric group
338:
272:
221:
220:
155:
154:
135:
134:
123:
86:
17:
12:
11:
5:
916:
914:
906:
905:
900:
895:
885:
884:
881:
880:
871:
865:
859:
835:Grime, James.
832:
825:
824:External links
822:
819:
818:
797:
772:
732:
689:
658:
639:
615:
578:
505:
504:
502:
499:
498:
497:
465:
443:
440:
439:
438:
432:
417:
414:
337:
334:
271:
268:
255:
252:
249:
246:
243:
240:
237:
234:
231:
228:
168:
165:
162:
142:
122:
119:
15:
13:
10:
9:
6:
4:
3:
2:
915:
904:
901:
899:
896:
894:
891:
890:
888:
879:
875:
872:
869:
866:
863:
860:
849:
845:
838:
833:
831:
828:
827:
823:
813:
808:
801:
798:
787:
783:
776:
773:
768:
763:
758:
753:
749:
745:
744:
736:
733:
728:
722:
707:
700:
693:
690:
678:
677:
672:
665:
663:
659:
654:
650:
643:
640:
635:
631:
624:
622:
620:
616:
604:
600:
593:
591:
589:
587:
585:
583:
579:
567:
563:
559:
555:
551:
547:
543:
539:
534:
529:
525:
521:
517:
510:
507:
500:
494:
488:
480:
479:
471:
466:
463:
459:
455:
451:
446:
445:
441:
436:
433:
431:
428:symbols as a
427:
423:
420:
419:
415:
413:
411:
407:
403:
399:
395:
391:
387:
383:
379:
375:
371:
367:
363:
359:
355:
351:
347:
343:
335:
333:
331:
327:
323:
319:
318:
313:
309:
305:
301:
297:
293:
289:
285:
281:
277:
269:
267:
253:
250:
247:
244:
241:
238:
235:
232:
229:
226:
218:
214:
209:
205:
201:
196:
194:
190:
184:
182:
166:
163:
160:
140:
127:
120:
118:
116:
111:
109:
104:
102:
98:
94:
89:
84:
80:
76:
71:
69:
65:
61:
57:
54:symbols as a
53:
49:
45:
42:symbols is a
41:
37:
33:
30:
29:combinatorial
21:
903:Permutations
851:. Retrieved
843:
800:
789:. Retrieved
785:
775:
747:
741:
735:
709:. Retrieved
705:
692:
680:. Retrieved
674:
652:
642:
633:
606:. Retrieved
603:gregegan.net
602:
569:. Retrieved
523:
519:
509:
487:cite journal
476:
453:
449:
425:
422:Superpattern
409:
405:
401:
397:
393:
389:
385:
381:
377:
373:
369:
365:
361:
357:
346:Cayley graph
344:through the
339:
336:Upper bounds
315:
307:
303:
299:
295:
291:
287:
273:
197:
192:
188:
185:
180:
132:
114:
112:
107:
105:
100:
96:
85:! (sequence
82:
78:
74:
72:
67:
63:
51:
39:
35:
26:
848:Brady Haran
812:1307.2549v3
750:(1): 4–24,
48:permutation
32:mathematics
887:Categories
853:1 February
791:2023-10-05
786:IFLScience
757:1810.08252
711:27 October
608:15 January
566:1368.05004
501:References
462:0801.05004
634:The Verge
571:March 16,
533:1303.4150
456:: 91–98,
354:Greg Egan
290:symbols (
245:…
164:−
56:substring
721:cite web
682:June 21,
558:12018639
416:See also
392:−2)! + (
388:−1)! + (
368:−2)! + (
364:−1)! + (
302:−1)! + (
58:. While
874:Article
844:YouTube
840:(video)
538:Bibcode
396:−3)! +
372:−3)! +
348:of the
314:series
306:−2)! +
91:in the
88:A180632
60:trivial
653:Warosu
564:
556:
460:
208:weight
204:vertex
44:string
868:Tweet
807:arXiv
752:arXiv
702:(PDF)
554:S2CID
528:arXiv
473:(PDF)
384:! + (
360:! + (
312:anime
298:! + (
284:4chan
280:board
276:/sci/
200:graph
855:2018
727:link
713:2018
706:OEIS
684:2020
610:2020
573:2014
493:link
330:2021
93:OEIS
34:, a
762:doi
748:128
562:Zbl
546:doi
524:313
458:Zbl
282:of
278:")
103:):
50:of
38:on
27:In
889::
846:.
842:.
784:.
760:,
746:,
723:}}
719:{{
704:.
673:.
661:^
651:.
632:.
618:^
601:.
581:^
560:.
552:.
544:.
536:.
522:.
518:.
489:}}
485:{{
475:.
454:93
452:,
857:.
815:.
809::
794:.
764::
754::
729:)
715:.
686:.
655:.
636:.
612:.
575:.
548::
540::
530::
495:)
481:.
426:n
410:n
406:n
402:n
398:n
394:n
390:n
386:n
382:n
378:n
374:n
370:n
366:n
362:n
358:n
308:n
304:n
300:n
296:n
292:n
288:n
254:!
251:n
248:+
242:+
239:!
236:2
233:+
230:!
227:1
193:n
189:n
181:n
167:1
161:n
141:n
115:n
108:2
101:2
97:n
83:n
79:n
75:n
68:n
64:n
52:n
40:n
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
