Steinhaus–Johnson–Trotter algorithm (original) (raw)
El algoritmo Steinhaus–Johnson–Trotter o algoritmo Johnson–Trotter, también llamado cambios simples, es un algoritmo que lleva el nombre de Hugo Steinhaus Selmer M. Johnson y Hale F. Trotter que genera todas las permutaciones de n elementos. Cada permutación en la secuencia que genera difiere de la permutación anterior al intercambiar dos elementos adyacentes de la secuencia. De manera equivalente, este algoritmo encuentra un ciclo hamiltoniano en el permutoedro. El algoritmo Johnson-Trotter ofrece una forma eficaz de generar directamente permutaciones de la longitud requerida sin calcular permutaciones más cortas.
;_Steinhaus%E2%80%93Johnson%E2%80%93Trotter.svg?width=300)
| Property | Value |
|---|---|
| dbo:abstract | Der Steinhaus-Johnson-Trotter-Algorithmus oder der Johnson-Trotter-Algorithmus, auch einfache Änderungen genannt, ist ein Algorithmus, der nach Hugo Steinhaus, Selmer M. Johnson und Hale Trotter benannt ist und alle Permutationen von Elementen erzeugt. Jede Permutation in der von ihr erzeugten Sequenz unterscheidet sich von der vorherigen Permutation durch Vertauschen zweier benachbarter Elemente der Sequenz. Entsprechend findet dieser Algorithmus einen Hamiltonweg im Permutaeder. Diese Methode war bereits den englischen Change-Ringern des 17. Jahrhunderts bekannt und Robert Sedgewick nennt sie 1977 „den vielleicht bekanntesten Permutations-Aufzählungsalgorithmus“. Er ist nicht nur einfach und rechnerisch effizient, sondern hat auch den Vorteil, dass nachfolgende Berechnungen der von ihm erzeugten Permutationen beschleunigt werden können, da diese Permutationen einander so ähnlich sind. (de) El algoritmo Steinhaus–Johnson–Trotter o algoritmo Johnson–Trotter, también llamado cambios simples, es un algoritmo que lleva el nombre de Hugo Steinhaus Selmer M. Johnson y Hale F. Trotter que genera todas las permutaciones de n elementos. Cada permutación en la secuencia que genera difiere de la permutación anterior al intercambiar dos elementos adyacentes de la secuencia. De manera equivalente, este algoritmo encuentra un ciclo hamiltoniano en el permutoedro. El algoritmo Johnson-Trotter ofrece una forma eficaz de generar directamente permutaciones de la longitud requerida sin calcular permutaciones más cortas. (es) The Steinhaus–Johnson–Trotter algorithm or Johnson–Trotter algorithm, also called plain changes, is an algorithm named after Hugo Steinhaus, Selmer M. Johnson and Hale F. Trotter that generates all of the permutations of elements. Each permutation in the sequence that it generates differs from the previous permutation by swapping two adjacent elements of the sequence. Equivalently, this algorithm finds a Hamiltonian cycle in the permutohedron. This method was known already to 17th-century English change ringers, and calls it "perhaps the most prominent permutation enumeration algorithm". A version of the algorithm can be implemented in such a way that the average time per permutation is constant. As well as being simple and computationally efficient, this algorithm has the advantage that subsequent computations on the permutations that it generates may be sped up because of the similarity between consecutive permutations that it generates. (en) 스테인하우스-존슨-트로터 알고리즘(Steinhaus–Johnson–Trotter algorithm) 또는 존슨-트로터 알고리즘(Johnson–Trotter algorithm)은 플레인 변경(plain changes)으로도 불리는 순열(permutohedron) 알고리즘으로 n 개 요소의 모든 순열을 생성하는 후고 스테인하우스(Hugo Steinhaus), (Selmer M. Johnson) 및 (Hale F. Trotter)의 이름을 따서 명명된 알고리즘이다. 생성하는 시퀀스의 각 순열들은 시퀀스의 인접한 두 요소를 교체하며 이전 순열과 다르다. 마찬가지로 이 알고리즘은 또한 순열(permutohedron)에서 해밀턴 경로(Hamiltonian path)주기를 찾는다. (ko) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Symmetric_group_4;_Ca...einhaus–Johnson–Trotter.svg?width=300 |
| dbo:wikiPageExternalLink | http://www.cs.utexas.edu/users/EWD/ewd05xx/EWD553.PDF http://www.cs.utexas.edu/users/EWD/transcriptions/EWD05xx/EWD502.html https://ageconsearch.umn.edu/record/272202/files/erasmus129.pdf http://www-cs-faculty.stanford.edu/~uno/fasc2b.ps.gz |
| dbo:wikiPageID | 2568963 (xsd:integer) |
| dbo:wikiPageLength | 20305 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1116241633 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Algorithm dbr:Hugo_Steinhaus dbr:Permutation dbr:Permutohedron dbr:Inversion_(discrete_mathematics) dbc:Permutations dbr:Gray_code dbr:Convex_hull dbr:Parity_of_a_permutation dbc:Combinatorial_algorithms dbr:Truncated_octahedron dbr:Heap's_algorithm dbr:ALGOL_60 dbr:Cayley_graph dbr:Iterative_method dbr:Radix dbr:Hamiltonian_path dbr:Inverse_element dbr:Mixed_radix dbr:Change_ringing dbr:Shimon_Even dbr:Loopless_algorithm dbr:Fabian_Stedman dbr:Factorial_number_system dbr:Symmetric_group dbr:Fisher–Yates_shuffle dbr:Selmer_M._Johnson dbr:Polytope dbr:SIAM_Review dbr:Hale_F._Trotter dbr:Hamiltonian_cycle dbr:Recursive_algorithm dbr:File:Symmetric_group_4;_Cayley_graph_1,2,6_(3D);_Steinhaus–Johnson–Trotter.svg dbr:File:Symmetric_group_4;_permutation_list;_Steinhaus–Johnson–Trotter.svg dbr:File:Wheel_diagram_of_Steinhaus-Johnson-Trotter_algorithm_for_n=4.svg |
| dbp:wikiPageUsesTemplate | dbt:Citation dbt:Harvtxt dbt:Refbegin dbt:Refend dbt:Reflist dbt:Sfnp dbt:OEIS2C dbt:Bi |
| dcterms:subject | dbc:Permutations dbc:Combinatorial_algorithms |
| gold:hypernym | dbr:Algorithm |
| rdf:type | dbo:Software yago:WikicatCombinatorialAlgorithms yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Change107296428 yago:Event100029378 yago:Happening107283608 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:YagoPermanentlyLocatedEntity yago:Rule105846932 yago:Substitution107443761 yago:Variation107337390 yago:WikicatPermutations |
| rdfs:comment | El algoritmo Steinhaus–Johnson–Trotter o algoritmo Johnson–Trotter, también llamado cambios simples, es un algoritmo que lleva el nombre de Hugo Steinhaus Selmer M. Johnson y Hale F. Trotter que genera todas las permutaciones de n elementos. Cada permutación en la secuencia que genera difiere de la permutación anterior al intercambiar dos elementos adyacentes de la secuencia. De manera equivalente, este algoritmo encuentra un ciclo hamiltoniano en el permutoedro. El algoritmo Johnson-Trotter ofrece una forma eficaz de generar directamente permutaciones de la longitud requerida sin calcular permutaciones más cortas. (es) 스테인하우스-존슨-트로터 알고리즘(Steinhaus–Johnson–Trotter algorithm) 또는 존슨-트로터 알고리즘(Johnson–Trotter algorithm)은 플레인 변경(plain changes)으로도 불리는 순열(permutohedron) 알고리즘으로 n 개 요소의 모든 순열을 생성하는 후고 스테인하우스(Hugo Steinhaus), (Selmer M. Johnson) 및 (Hale F. Trotter)의 이름을 따서 명명된 알고리즘이다. 생성하는 시퀀스의 각 순열들은 시퀀스의 인접한 두 요소를 교체하며 이전 순열과 다르다. 마찬가지로 이 알고리즘은 또한 순열(permutohedron)에서 해밀턴 경로(Hamiltonian path)주기를 찾는다. (ko) Der Steinhaus-Johnson-Trotter-Algorithmus oder der Johnson-Trotter-Algorithmus, auch einfache Änderungen genannt, ist ein Algorithmus, der nach Hugo Steinhaus, Selmer M. Johnson und Hale Trotter benannt ist und alle Permutationen von Elementen erzeugt. Jede Permutation in der von ihr erzeugten Sequenz unterscheidet sich von der vorherigen Permutation durch Vertauschen zweier benachbarter Elemente der Sequenz. Entsprechend findet dieser Algorithmus einen Hamiltonweg im Permutaeder. (de) The Steinhaus–Johnson–Trotter algorithm or Johnson–Trotter algorithm, also called plain changes, is an algorithm named after Hugo Steinhaus, Selmer M. Johnson and Hale F. Trotter that generates all of the permutations of elements. Each permutation in the sequence that it generates differs from the previous permutation by swapping two adjacent elements of the sequence. Equivalently, this algorithm finds a Hamiltonian cycle in the permutohedron. (en) |
| rdfs:label | Steinhaus-Johnson-Trotter-Algorithmus (de) Algoritmo de Steinhaus–Johnson–Trotter (es) 스테인하우스-존슨-트로터 알고리즘 (ko) Steinhaus–Johnson–Trotter algorithm (en) |
| owl:sameAs | freebase:Steinhaus–Johnson–Trotter algorithm wikidata:Steinhaus–Johnson–Trotter algorithm dbpedia-de:Steinhaus–Johnson–Trotter algorithm dbpedia-es:Steinhaus–Johnson–Trotter algorithm dbpedia-fa:Steinhaus–Johnson–Trotter algorithm http://hy.dbpedia.org/resource/Շտայնհաուզ-Ջոնսոն-Թրոթթեր_ալգորիթմ dbpedia-ko:Steinhaus–Johnson–Trotter algorithm dbpedia-sr:Steinhaus–Johnson–Trotter algorithm dbpedia-th:Steinhaus–Johnson–Trotter algorithm https://global.dbpedia.org/id/4ZxhG |
| prov:wasDerivedFrom | wikipedia-en:Steinhaus–Johnson–Trotter_algorithm?oldid=1116241633&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Symmetric_group_4;_permutation_list.svg wiki-commons:Special:FilePath/4.svg wiki-commons:Special:FilePath/Symmetric_group_4;_Ca...6_(3D);_Steinhaus–Johnson–Trotter.svg wiki-commons:Special:FilePath/Symmetric_group_4;_pe...n_list;_Steinhaus–Johnson–Trotter.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Steinhaus–Johnson–Trotter_algorithm |
| is dbo:knownFor of | dbr:Hale_Trotter |
| is dbo:wikiPageRedirects of | dbr:Steinhaus-Johnson-Trotter_algorithm dbr:Johnson–Trotter_algorithm dbr:Steinhaus-Johnson-Trotter dbr:Johnson-Trotter dbr:Johnson-Trotter_algorithm dbr:Johnson–Trotter dbr:Plain_changes |
| is dbo:wikiPageWikiLink of | dbr:Campanology dbr:List_of_algorithms dbr:Permutation dbr:Permutohedron dbr:List_of_permutation_topics dbr:Gray_code dbr:Heap's_algorithm dbr:Hale_Trotter dbr:Hamiltonian_path dbr:Steinhaus-Johnson-Trotter_algorithm dbr:Change_ringing dbr:Johnson–Trotter_algorithm dbr:Factorial_number_system dbr:List_of_terms_relating_to_algorithms_and_data_structures dbr:Lovász_conjecture dbr:Selmer_M._Johnson dbr:Steinhaus-Johnson-Trotter dbr:Johnson-Trotter dbr:Johnson-Trotter_algorithm dbr:Johnson–Trotter dbr:Plain_changes |
| is dbp:knownFor of | dbr:Hale_Trotter |
| is foaf:primaryTopic of | wikipedia-en:Steinhaus–Johnson–Trotter_algorithm |
