Superpermutation (original) (raw)
組合せ数学におけるn記号の超置換（ちょうちかん、英: superpermutation）とは、n個の記号の全ての置換を部分文字列として含む文字列である。 1≤ n ≤5に対しては、最小のn記号の超置換の長さは 1! + 2! + … + n! である（オンライン整数列大辞典の数列 A180632）。最初の5つの超置換の長さはそれぞれ 1,3,9,33,153 であり、文字列は具体的には 1 , 121 , 123121321 , 123412314231243121342132413214321 及び以下のものとなる : 123451234152341253412354123145231425314235142315423124531243512431524312543121345213425134215342135421324513241532413524132541321453214352143251432154321
| Property | Value |
|---|---|
| dbo:abstract | Eine Superpermutation von Zeichen ist in der Kombinatorik eine Zeichenkette, die jede mögliche Permutation, also Kombination, dieser Zeichen als Zeichenkette beinhaltet. Es wurde gezeigt, dass für 1≤ die kleinste Superpermutation die Länge , also , hat.So gibt es beispielsweise 6 Permutationen für die drei Elemente , nämlich , , , , und ; und eine kleinste Superpermutation, welche alle diese Permutationen beinhaltet, hat eine Länge von 9 Zeichen: . Die ersten fünf Superpermutationen haben die Längen 1, 3, 9, 33 und 153. Die Zeichenketten dieser Permutationen sehen beispielsweise so aus: * 1 * 121 * 123121321 * 123412314231243121342132413214321 * 123451234152341253412354123145231425314235142315423124531243512431524312543121345213425134215342135421324513241532413524132541321453214352143251432154321. Für eine Zeichenmenge von wurde 2014 eine kürzere Superpermutation als gefunden. Anstelle einer Länge von 873 Zeichen wurden für nur 872 Zeichen benötigt. Es wird daher erwartet, dass für gilt, dass maximal eine Länge von für die kürzeste Superpermutation benötigt wird: “The minimal length is still unknown for , but we can show that for all it is strictly less than the conjectured length […]”. Auf dem Imageboard 4chan wurde am 27. September 2011 von einem anonymen Nutzer nachgewiesen, dass die kürzeste Superpermutation für eine Länge von mindestens hat. Robin Houston, Jay Pantone und Vince Vatter haben am 25. Oktober 2018 einen vollständigen Beweis dessen in der Datenbank OEIS veröffentlicht. (de) En mathématiques, et plus précisément en combinatoire, une superpermutation de n caractères est une chaîne qui contient chaque permutation de n caractères comme sous-chaîne. Il a été démontré que pour 1 ≤ n ≤ 5, la plus petite superpermutation de n caractères a pour longueur 1! + 2! + … + n! (suite de l'OEIS). Les cinq premières superpermutations ont pour longueurs respectives 1, 3, 9, 33 et 153, formant les chaînes 1, 121, 123121321, 123412314231243121342132413214321 et la chaîne : 123451234152341253412354123145231425314235142315423124531243512431524312543121345213425134215342135421324513241532413524132541321453214352143251432154321 (fr) In combinatorial mathematics, a superpermutation on n symbols is a string that contains each permutation of n symbols as a substring. While trivial superpermutations can simply be made up of every permutation listed together, superpermutations can also be shorter (except for the trivial case of n = 1) because overlap is allowed. For instance, in the case of n = 2, the superpermutation 1221 contains all possible permutations (12 and 21), but the shorter string 121 also contains both permutations. It has been shown that for 1 ≤ n ≤ 5, the smallest superpermutation on n symbols has length 1! + 2! + … + n! (sequence in the OEIS). The first four smallest superpermutations have respective lengths 1, 3, 9, and 33, forming the strings 1, 121, 123121321, and 123412314231243121342132413214321. However, for n = 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 2): 123451234152341253412354123145231425314235142315423124531243512431524312543121345213425134215342135421324513241532413524132541321453214352143251432154321 For the cases of n > 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. (en) 組合せ数学におけるn記号の超置換（ちょうちかん、英: superpermutation）とは、n個の記号の全ての置換を部分文字列として含む文字列である。 1≤ n ≤5に対しては、最小のn記号の超置換の長さは 1! + 2! + … + n! である（オンライン整数列大辞典の数列 A180632）。最初の5つの超置換の長さはそれぞれ 1,3,9,33,153 であり、文字列は具体的には 1 , 121 , 123121321 , 123412314231243121342132413214321 及び以下のものとなる : 123451234152341253412354123145231425314235142315423124531243512431524312543121345213425134215342135421324513241532413524132541321453214352143251432154321 (ja) In matematica combinatoria, una superpermutazione di n simboli è una stringa che contiene tutte le permutazioni dei suoi simboli come sottostringa. Si sa che per 1 ≤ n ≤ 5 le superpermutazioni minimali di n simboli, cioè quelle di lunghezza minore possibile, hanno lunghezza 1! + 2! + … + n! . Le prime cinque superpermutazioni minimali hanno pertanto lunghezza rispettiva 1, 3, 9, 33, e 153, e sono date dalle stringhe 1, 121, 123121321, 123412314231243121342132413214321, e: 123451234152341253412354123145231425314235142315423124531243512431524312543121345213425134215342135421324513241532413524132541321453214352143251432154321 Per n ≥ 6 non è nota qual è la lunghezza minima: è possibile scendere sotto il valore dato dalla formula suindicata, come mostrato per la prima volta nel 2014 da Robin Houston. (it) 在组合数学中，n 个符号的超排列（Superpermutation）是一个字符串，使得n 个符号的所有排列均为它的子串。这些子串可以互相重叠。对于任意一个指定的 n，超排列的长度存在一个最小值，最短的超排列称为最小超排列。 在 1≤ n ≤5 时，n 个符号的最小超排列的长度是1! +2! +...+ n!，分别是1、3、9、33和153（OEIS數列），与之对应的字符串分别是1、121、123121321、123412314231243121342132413214321，以及： 123451234152341253412354123145231425314235142315423124531243512431524312543121345213425134215342135421324513241532413524132541321453214352143251432154321 (zh) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Superpermutation_distribution.png?width=300 |
| dbo:wikiPageExternalLink | http://www.njohnston.ca/2013/04/the-minimal-superpermutation-problem/ https://oeis.org/A180632/a180632.pdf%7Cjournal= https://twitter.com/robinhouston/status/1054637891085918209 https://www.youtube.com/watch%3Fv=wJGE4aEWc28%7Cwebsite=YouTube%7Cpublisher= https://warosu.org/sci/thread/S3751105%23p3751197 |
| dbo:wikiPageID | 42223508 (xsd:integer) |
| dbo:wikiPageLength | 10502 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1118538700 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Brady_Haran dbc:Combinatorics_on_words dbc:Enumerative_combinatorics dbr:Permutation dbr:Upper_and_lower_bounds dbr:De_Bruijn_sequence dbc:Permutations dbr:Mathematics dbr:Graph_(discrete_mathematics) dbr:Anime dbr:Combinatorics dbr:String_(computer_science) dbr:4chan dbr:Cayley_graph dbr:Greg_Egan dbr:Hamiltonian_path dbr:Haruhi_Suzumiya dbr:Triviality_(mathematics) dbr:On-Line_Encyclopedia_of_Integer_Sequences dbr:Vertex_(graph_theory) dbr:Weight dbr:Symmetric_group dbr:Permutation_pattern dbr:Internet_forums dbr:Superpattern dbr:Substring dbr:Traveling_salesman_problem dbr:File:Superpermutation_distribution.png dbr:File:Superpermutations.jpg |
| dbp:wikiPageUsesTemplate | dbt:Citation dbt:Cite_journal dbt:Cite_web dbt:OEIS dbt:Reflist dbt:Short_description dbt:Harvs |
| dct:subject | dbc:Combinatorics_on_words dbc:Enumerative_combinatorics dbc:Permutations |
| gold:hypernym | dbr:String |
| rdf:type | dbo:Island |
| rdfs:comment | 組合せ数学におけるn記号の超置換（ちょうちかん、英: superpermutation）とは、n個の記号の全ての置換を部分文字列として含む文字列である。 1≤ n ≤5に対しては、最小のn記号の超置換の長さは 1! + 2! + … + n! である（オンライン整数列大辞典の数列 A180632）。最初の5つの超置換の長さはそれぞれ 1,3,9,33,153 であり、文字列は具体的には 1 , 121 , 123121321 , 123412314231243121342132413214321 及び以下のものとなる : 123451234152341253412354123145231425314235142315423124531243512431524312543121345213425134215342135421324513241532413524132541321453214352143251432154321 (ja) 在组合数学中，n 个符号的超排列（Superpermutation）是一个字符串，使得n 个符号的所有排列均为它的子串。这些子串可以互相重叠。对于任意一个指定的 n，超排列的长度存在一个最小值，最短的超排列称为最小超排列。 在 1≤ n ≤5 时，n 个符号的最小超排列的长度是1! +2! +...+ n!，分别是1、3、9、33和153（OEIS數列），与之对应的字符串分别是1、121、123121321、123412314231243121342132413214321，以及： 123451234152341253412354123145231425314235142315423124531243512431524312543121345213425134215342135421324513241532413524132541321453214352143251432154321 (zh) Eine Superpermutation von Zeichen ist in der Kombinatorik eine Zeichenkette, die jede mögliche Permutation, also Kombination, dieser Zeichen als Zeichenkette beinhaltet. Es wurde gezeigt, dass für 1≤ die kleinste Superpermutation die Länge , also , hat.So gibt es beispielsweise 6 Permutationen für die drei Elemente , nämlich , , , , und ; und eine kleinste Superpermutation, welche alle diese Permutationen beinhaltet, hat eine Länge von 9 Zeichen: . Die ersten fünf Superpermutationen haben die Längen 1, 3, 9, 33 und 153. Die Zeichenketten dieser Permutationen sehen beispielsweise so aus: (de) En mathématiques, et plus précisément en combinatoire, une superpermutation de n caractères est une chaîne qui contient chaque permutation de n caractères comme sous-chaîne. Il a été démontré que pour 1 ≤ n ≤ 5, la plus petite superpermutation de n caractères a pour longueur 1! + 2! + … + n! (suite de l'OEIS). Les cinq premières superpermutations ont pour longueurs respectives 1, 3, 9, 33 et 153, formant les chaînes 1, 121, 123121321, 123412314231243121342132413214321 et la chaîne : (fr) In combinatorial mathematics, a superpermutation on n symbols is a string that contains each permutation of n symbols as a substring. While trivial superpermutations can simply be made up of every permutation listed together, superpermutations can also be shorter (except for the trivial case of n = 1) because overlap is allowed. For instance, in the case of n = 2, the superpermutation 1221 contains all possible permutations (12 and 21), but the shorter string 121 also contains both permutations. (en) In matematica combinatoria, una superpermutazione di n simboli è una stringa che contiene tutte le permutazioni dei suoi simboli come sottostringa. Si sa che per 1 ≤ n ≤ 5 le superpermutazioni minimali di n simboli, cioè quelle di lunghezza minore possibile, hanno lunghezza 1! + 2! + … + n! . Le prime cinque superpermutazioni minimali hanno pertanto lunghezza rispettiva 1, 3, 9, 33, e 153, e sono date dalle stringhe 1, 121, 123121321, 123412314231243121342132413214321, e: (it) |
| rdfs:label | Superpermutation (de) Superpermutation (fr) Superpermutazione (it) 超置換 (ja) Superpermutation (en) 超排列 (zh) |
| owl:sameAs | freebase:Superpermutation yago-res:Superpermutation wikidata:Superpermutation dbpedia-de:Superpermutation dbpedia-fr:Superpermutation dbpedia-it:Superpermutation dbpedia-ja:Superpermutation dbpedia-lmo:Superpermutation dbpedia-simple:Superpermutation dbpedia-vi:Superpermutation dbpedia-zh:Superpermutation https://global.dbpedia.org/id/ffAT |
| prov:wasDerivedFrom | wikipedia-en:Superpermutation?oldid=1118538700&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Superpermutation_distribution.png wiki-commons:Special:FilePath/Superpermutations.jpg |
| foaf:isPrimaryTopicOf | wikipedia-en:Superpermutation |
| is dbo:wikiPageRedirects of | dbr:Haruhi_problem dbr:The_Haruhi_problem dbr:Superpermutations |
| is dbo:wikiPageWikiLink of | dbr:Permutation dbr:De_Bruijn_sequence dbr:4chan dbr:Greg_Egan dbr:Haruhi_Suzumiya dbr:Haruhi_problem dbr:Superpattern dbr:Substring dbr:The_Haruhi_problem dbr:Superpermutations |
| is foaf:primaryTopic of | wikipedia-en:Superpermutation |
